Period finding: the heart of Shor’s algorithm

Why does factoring a number come down to finding how long a sequence takes to repeat itself? See the classical skeleton of Shor’s algorithm step by step with the number 15.

Factoring and encryption

We can split small numbers like 15 = 3 × 5 in our heads. But splitting a number with hundreds of digits into its two prime factors is practically impossible even for today’s most powerful computers. The security of RSA, the encryption widely used on the internet, rests on exactly this difficulty.

In 1994 Peter Shor showed that a quantum computer could do this much faster: the running time of classical methods grows almost exponentially with the number of digits, while that of Shor’s algorithm grows only polynomially. The trick is to turn factoring into a period-finding problem.

A sequence that repeats itself

Take N = 15 and a random a = 7. Divide the powers of 7 by 15 and look at the remainders: 1, 7, 4, 13, 1, 7, 4, 13… The sequence repeats every 4 steps. This number 4 is called the period and is written r.

Once the period is known, the factors follow from a simple calculation: take the greatest common divisor (gcd) of a^(r/2) − 1 and a^(r/2) + 1 with N. In our example 7² = 49; gcd(48, 15) = 3 and gcd(50, 15) = 5. And there it is: 15 = 3 × 5.

from math import gcd

N, a = 15, 7
print([pow(a, x, N) for x in range(8)])   # [1, 7, 4, 13, 1, 7, 4, 13]

r = next(x for x in range(1, N) if pow(a, x, N) == 1)
print(r)                                   # 4
print(gcd(a**(r // 2) - 1, N), gcd(a**(r // 2) + 1, N))   # 3 5

The hard part is finding the period

The code above found the period by trying the powers one by one. That is easy for small numbers, but for a large N the period can be astronomically large and trying one by one would take longer than the age of the universe. In Shor’s algorithm only this step is quantum; everything else, such as the gcd, runs on an ordinary computer.

Sometimes an unlucky a is chosen: the period is odd, or a^(r/2) leaves a remainder of −1 when divided by N. For example, for a = 14 the period is r = 2, but since 14 ≡ −1 (mod 15) no factor comes out. Then another a is tried; most randomly chosen values of a work.

Period and the Fourier transform

Finding a period is exactly what the quantum Fourier transform, which you met in the intermediate course, does. When a periodic state goes through the Fourier transform, the measurement results gather in peaks that reveal the period. In the next lesson we put these two pieces together and see Shor’s algorithm as a whole.

Try it yourself

The first H gate prepares a state with period 2. After the Fourier transform only 00 and 10 appear: the peaks reveal the period. Remove the first H: the periodic pattern disappears and each of the four outcomes gets 25%.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

The security of RSA encryption rests on the difficulty of factoring large numbers.
Shor’s algorithm reduces factoring to finding the period of the sequence aˣ mod N.
Once the period r is known, the factors come from gcd(a^(r/2) ± 1, N): 3 and 5 for 15.
Only the period-finding step is quantum; the rest is classical computation.

Test yourself

For N = 15 and a = 7, what is the period of the sequence 7ˣ mod 15?

Show the answer

4. The remainders are 1, 7, 4, 13 and then 1 again; the sequence repeats every 4 steps.

Shor’s algorithm: factoring with phase estimation →