Shor’s algorithm: factoring with phase estimation

The quantum part of period finding is phase estimation. Extract the period from the measured phase with continued fractions, and learn where Shor’s algorithm stands today and what it means for encryption.

The period hides in a phase

Shor’s algorithm builds a gate U that does “multiply y by a, divide by N, keep the remainder”. Applying this gate r times brings you back to the start, because aʳ mod N = 1. The eigenstates of such a gate have phases of the form s/r; in other words, the period is written straight into the phase.

Phase estimation, which you met in the intermediate course, reads exactly this phase as a binary number in the counting qubits. The counter gets H gates first, then controlled powers of U, and finally the inverse quantum Fourier transform. If the measured number is m, the phase is approximately m / 2ⁿ.

From phase to period: continued fractions

For 15 and a = 7, 3 counting qubits are enough. The measurement gives 0, 2, 4 and 6 with equal probability; the phases are 0, 1/4, 1/2 and 3/4. After simplifying the fraction its denominator is a candidate for the period: 1/4 and 3/4 directly give r = 4. The 2 from 1/2 is a divisor of the period and 0 gives no information; in that case the algorithm is simply run again.

With large numbers the measured fraction does not arrive in simplified form; a classical method called continued fractions is used to find the right denominator. Python’s Fraction class does this with limit_denominator.

from fractions import Fraction

# 3 counting qubits: if the measured number is m, the phase is about m / 8
for m in [0, 2, 4, 6]:
    phase = Fraction(m, 8)
    print(m, phase, 'r candidate:', phase.denominator)
# 0 0 r candidate: 1
# 2 1/4 r candidate: 4
# 4 1/2 r candidate: 2
# 6 3/4 r candidate: 4

Where are we today?

In 2001, 15 = 3 × 5 was factored with Shor’s algorithm on a seven-qubit quantum computer. The examples shown since then are still very small numbers, because breaking a real RSA key needs thousands of error-free logical qubits and billions of gates.

According to Craig Gidney’s 2025 estimate, fewer than a million noisy physical qubits could be enough to break a 2048-bit RSA key in less than a week. That today’s largest devices are far below this number shows that the threat is distant but real.

What about encryption?

Attackers can collect encrypted data today and wait to decrypt it years later with a quantum computer (“harvest now, decrypt later”). That is why the transition has already begun: in 2024 NIST, the US standards body, published the first encryption standards designed to resist quantum computers (ML-KEM, ML-DSA and SLH-DSA).

These new methods run on classical computers and rest on mathematics that Shor’s algorithm cannot solve, such as lattice problems. Quantum cryptography and post-quantum encryption are the subject of one of the school’s later courses.

Try it yourself

This phase estimation circuit reads the phase of the S gate as 01 / 4 = ¼ turn. Shor’s algorithm uses the same skeleton; the only difference is that a “multiply by a, divide by N” gate takes the place of S, and the denominator of the fraction s/r that is read gives the period.

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

Shor’s algorithm finds the period of aˣ mod N with phase estimation: the phases have the form s/r.
The denominator of the measured phase is found with continued fractions and gives a period candidate.
Breaking real RSA keys needs error-corrected computers far larger than today’s devices.
Post-quantum encryption standards (ML-KEM, ML-DSA, SLH-DSA) have already been published against this threat.

Test yourself

If the phase measured in the counter is 3/4, what is the period candidate?

Show the answer

4. The phase has the form s/r; the denominator of the simplified fraction is the period candidate: r = 4 for 3/4.

← Period finding: the heart of Shor’s algorithm · VQE: finding the lowest energy of a molecule →