Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Shor's Algorithm

  1. Mar 10, 2006 #1
    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.
     
    Last edited: Mar 10, 2006
  2. jcsd
  3. Mar 10, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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'.
     
  4. Mar 10, 2006 #3

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

    I do want to make a quick point, though:
    (12,4)=4, not 2. Sorry to be so picky! :rolleyes:

    -Dan
     
  5. Mar 12, 2006 #4
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Shor's Algorithm
  1. No fastest algorithm (Replies: 10)

  2. Search algorithm (Replies: 14)

  3. Math algorithm (Replies: 5)

  4. Nesting Algorithm (Replies: 1)

Loading...