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

---

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

---

METHOD

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
   • YES? - You found a factor, you are done
   • NO? - Continue to step 4
4. Calculate the order, r, of the group <a> mod N
   • You can do this by looking at the sequence:
     • [1, a, a^2, a^3, ...] mod N
   • This sequence will repeat.
   • The order, r, is the length of one repitition.
5. Let t = a^(r/2) mod N
6. Check to see if either t+1 or t-1 are factors of N
   • YES? - You found a factor, you are done
   • NO? - Choose the next a, and go back to step 3

---

TECHNICAL ANALYSIS 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) )

---

LINKS

• Time Analysis: Too bad to even publish.
• Source Code: Check out the code
• Alternate Description

---

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

Paul Herman
pherman@frenchfries.net

Last Updated: May 23, 1997