I'm playing around with the algorithm and I'm having some confusion:(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Shor's Algorithm

**Physics Forums | Science Articles, Homework Help, Discussion**