This algorithm was written by Peter W. Shor (AT&T Bell Labs) in 1994, intending its use for quantum computers. This algorithm doesn't work very well on "normal" computers, and is only here for illustrative purposes.
Not exactly sure. I do know that calculating the size of a multiplicative group (mod N) requires knowing the Euler totient function, and that is equivalent to knowing the prime factorization of N. More later, as soon as I find out.
  1. Choose a number, N, you wish to factor
  2. Choose a number, a, say a = 2
  3. Use division algorithm to see if a is a factor of N
  4. Calculate the order, r, of the group <a> mod N
  5. Let t = a^(r/2) mod N
  6. Check to see if either t+1 or t-1 are factors of N

Right now, I have no idea why this works, but I do know that it is equally as slow as the primitive method: The runtime grows exponentialy with the number of digits in N. Why bother with this algortihm? It apparently runs very quickly on Quantum Computers, a theoretical model of a new type of processing.
Theoretical Runtime:
O( exp( # of digits in N) )


Back to the factoring theory page
Back to the factoring page
Back to my home page
Back to the pslc home page

Paul Herman

Last Updated: May 23, 1997