Korva is a scroll of the internet’s best ideas.
Factoring becomes period finding
The repeating loop
Pick any number a from 2 up to n minus 1, then compute a to the power of r, mod n, for r equal to 1, 2, 3, and onward. The results wander through various numbers and eventually return to 1. The number of steps in that loop is the period.
Take n equal to 15 and a equal to 2. The powers run 1, 2, 4, 8, and then 2 to the 4 is 16, which wraps around to 1 mod 15. The cycle repeats from there, so the period r is 4.
From period to factors
A period hands over the factors. Because a to the r comes back to 1 mod n, a to the r minus 1 is an exact multiple of n, call it k times n. That splits by the difference of squares into (a to the r over 2, minus 1) times (a to the r over 2, plus 1), and the product equals k times p times q. It is then very likely that a to the r over 2, plus 1, shares a prime factor with n, so the greatest common divisor of the two pulls out p or q. In the example, 2 squared plus 1 is 5, the greatest common divisor of 5 and 15 is 5, and the other factor is 3.
Where quantum comes in
Some picks of a fail, most simply when r is odd and r over 2 becomes a fraction. A new a and another run fixes that. At real sizes, a is a 2,000-bit number, so working out a to the 1, a to the 2, and onward by brute force on a classical computer is far too slow. Finding the period is the job that goes to a quantum computer.
Why was Shor's algorithm such a big deal?
Peter Shor published the algorithm in 1994 while working at Bell Labs. The best known classical methods, such as the general number field sieve, need time that grows faster than any polynomial in the number of digits. Shor's method needs only polynomial time on a quantum computer. That gap turned quantum computing from a curiosity into a topic for cryptographers and governments.
How does a greatest common divisor avoid factoring?
Euclid's algorithm finds the greatest common divisor of two numbers by repeatedly replacing the larger number with its remainder after division by the smaller one. The number of steps grows only with the number of digits, so it stays fast even for numbers hundreds of digits long. It appears in Euclid's Elements, written around 300 BC. Computing it never requires knowing the prime factors of either number.
How often does a random pick of a fail?
In the standard analysis of Shor's algorithm, a number made from two distinct odd primes gives a usable result for at least half of the possible choices of a. A usable result means the period is even and the shortcut does not land on a trivial factor. A failed pick just means choosing a new a and running again. The chance of failing k picks in a row is therefore at most one in two to the power k.
More from Computerphile
