1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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




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...