How Does Shor's Algorithm Factor Integers Effectively?

[ptabor]

I'm playing around with the algorithm and I'm having some confusion:

the algorithm is as follows: to factorize some integer N pick some integer a such that a < N.
then compute the function f(x) = a^x mod N
f(x) will be periodic with period r, then to find the factors you find the greatest common divisor of N and a^(r/2) +\- 1

For example, suppose that N = 12. Then let us say that a = 5, then we have f(x) = 5^x mod 12. Plugging in some values for x, we see that
f(1) = 5 mod 12 = 5
f(2) = 25 mod 12 = 1
f(3) = 125 mod 12 = 5
f(4) = 625 mod 12 = 1

so here the period is 2, hence we must find the gcd of 5^(2/2) +\- 1 and N
=> gcd of 12 and 4 is 2; gcd of 12 and 6 is 6
hence 12 = 6*2

But suppose I start over and let a = 4
f(1) = 4 mod 12 = 4
f(2) = 16 mod 12 = 4
f(3) = 64 mod 12 = 4
and so on.

So the period here is 1, and we must find the gcd of 4^(1/2) +\- 1
and 12.

gcd of 3 and 12 is 3, gcd of 1 and 12 is 1. So does this imply that a is also a factor of N? It seems to me that it must, in all cases, but I don't want to make a hasty generalization.

 

[shmoe]

You would compute the gcd of N and the 'a' you picked before proceeding with the algorithm. If it's >1 you've found a factor, if it's 1 then you go on. Also if the period is odd, you have to pick a new 'a'.

 

[topsquark]

I'm playing around with the algorithm and I'm having some confusion:

the algorithm is as follows: to factorize some integer N pick some integer a such that a < N.
then compute the function f(x) = a^x mod N
f(x) will be periodic with period r, then to find the factors you find the greatest common divisor of N and a^(r/2) +\- 1

For example, suppose that N = 12. Then let us say that a = 5, then we have f(x) = 5^x mod 12. Plugging in some values for x, we see that
f(1) = 5 mod 12 = 5
f(2) = 25 mod 12 = 1
f(3) = 125 mod 12 = 5
f(4) = 625 mod 12 = 1

so here the period is 2, hence we must find the gcd of 5^(2/2) +\- 1 and N
=> gcd of 12 and 4 is 2; gcd of 12 and 6 is 6
hence 12 = 6*2

But suppose I start over and let a = 4
f(1) = 4 mod 12 = 4
f(2) = 16 mod 12 = 4
f(3) = 64 mod 12 = 4
and so on.

So the period here is 1, and we must find the gcd of 4^(1/2) +\- 1
and 12.

gcd of 3 and 12 is 3, gcd of 1 and 12 is 1. So does this imply that a is also a factor of N? It seems to me that it must, in all cases, but I don't want to make a hasty generalization.

I've never heard of this method. It sounds neat.

I do want to make a quick point, though:

so here the period is 2, hence we must find the gcd of 5^(2/2) +\- 1 and N
=> gcd of 12 and 4 is 2; gcd of 12 and 6 is 6
hence 12 = 6*2

(12,4)=4, not 2. Sorry to be so picky!

-Dan

 

[ptabor]

thanks for the correct, tops. I noticed the simple math error but didn't bother to fix it in the post =/

In any event, is this algorithm supposed to find all factors of N? I've performed it many times, and have only been able to come up with 6 and 4, not 2 and 3.

for instance, if a = 7 then we get 7 +/- 1 = 8, 6 - yielding 6 and 4 again.
if a = 11 then we get 11 +/- 1 = 12, 10 yielding 12 and 2 - where 12 is a trivial factor.
I can't let a = 2, 3, 4, 6, 8, 9, 10 because the gcd of these numbers with 12 is != 1.

Apparently I'm missing something here.