Quantum Mathematics Learning Guide 65: Shor’s Algorithm, Order Finding, Period Finding, Modular Exponentiation and Integer Factoring

Shor’s algorithm does not factor an integer by trying divisors faster. It converts factoring into an order-finding problem in modular arithmetic, then uses coherent quantum interference to estimate that order. Classical number theory finishes the job with greatest common divisors.

The algorithm is one of the central examples of a genuine polynomial-time quantum speedup for a problem whose best known general classical algorithms are superpolynomial in the input bit length. Peter Shor’s result also includes discrete logarithms. The factoring pipeline is especially instructive because every stage has a different mathematical owner: modular arithmetic, reversible computation, phase estimation, continued fractions and gcd extraction.

Guide 9 owns the Quantum Fourier Transform. Guide 10 owns generic phase estimation. Computational Number Theory on BTT owns classical factorisation algorithms. This guide owns the complete quantum order-finding reduction to integer factoring.

Choose a coprime base → find its multiplicative order modulo N → require an even useful order → compute two gcds → recover nontrivial factors.

1. The input size is log N, not N

Let N be the composite integer to factor. If N has n binary digits, then

n=⌈log₂N⌉.

Complexity claims for factoring are measured as functions of n, the bit length of the input.

A procedure taking O(√N) arithmetic steps is exponential in n because √N≈2^n/2. Shor’s importance is that the full ideal algorithm can be implemented using a number of elementary logical operations polynomial in n, with the exact exponent depending on arithmetic architecture and precision.

2. Classical preprocessing

Before invoking the quantum subroutine:

• if N is even, return factor 2;
• if N is a prime power p^k, classical perfect-power detection can recover p;
• if N is prime, there is nothing to factor;
• otherwise choose a random integer a with 1<a<N.

Compute d=gcd(a,N) classically.

If d>1, the random choice has already revealed a nontrivial factor and no quantum work is needed.

If gcd(a,N)=1, then a belongs to the multiplicative group of units modulo N, and order finding is well defined.

3. Multiplicative order

The order r of a modulo N is the smallest positive integer satisfying

a^r≡1 (mod N).

Because a is a unit modulo N, Euler’s theorem guarantees some positive exponent returns to 1.

The sequence

1,a,a²,a³,… (mod N)

therefore repeats with period r.

4. Why an even order can reveal factors

If r is even, then

a^r−1=(a^{r/2}−1)(a^{r/2}+1).

Since a^r≡1 mod N, N divides the product

(a^{r/2}−1)(a^{r/2}+1).

If additionally

a^{r/2}≢−1 (mod N),

then neither factor is a trivial multiple of N, and the gcds

gcd(a^{r/2}−1,N), gcd(a^{r/2}+1,N)

have a good chance of producing nontrivial factors.

5. Complete classical reduction example: N=15, a=2

Compute powers modulo 15:

• 2⁰≡1;
• 2¹≡2;
• 2²≡4;
• 2³≡8;
• 2⁴≡16≡1.

The order is r=4.

It is even, and

2^{r/2}=2²=4≢−1≡14 (mod 15).

Now

• gcd(4−1,15)=gcd(3,15)=3;
• gcd(4+1,15)=gcd(5,15)=5.

Thus 15=3×5.

The quantum computer’s job is only the hard middle step: recover r=4 efficiently without classically evaluating enough powers to discover the cycle by brute force.

6. Period-finding function

Define

f(x)=a^x mod N.

Because a has order r,

f(x+r)=f(x).

The goal is to determine the hidden period r using coherent evaluation of f.

Shor’s order-finding subroutine is therefore a structured hidden-period problem over the integers, closely related to the Abelian hidden-subgroup viewpoint developed in Guide 66.

7. Two quantum registers

Use a first register large enough to represent integers x from 0 to Q−1, where Q is typically a power of two satisfying

N²≤Q<2N².

A second register stores residues modulo N.

Prepare

(1/√Q)Σ_{x=0}^{Q−1}|x⟩|1⟩.

The large first register provides enough phase resolution for continued-fraction recovery of r.

8. Reversible modular exponentiation

Apply a reversible circuit implementing

|x⟩|1⟩→|x⟩|a^x mod N⟩.

The state becomes

(1/√Q)Σ_x |x⟩|f(x)⟩.

Efficient modular exponentiation uses repeated squaring:

a^x mod N = ∏_j (a^{2^j} mod N)^{x_j} mod N.

Each bit x_j controls a modular multiplication by a known constant a^{2^j} mod N.

9. Arithmetic is a major resource cost

The QFT is mathematically prominent, but fault-tolerant implementations of Shor’s algorithm are often dominated by reversible modular arithmetic.

Required components include:

• addition and subtraction;
• comparison;
• modular reduction;
• controlled modular multiplication;
• uncomputation of workspace;
• fault-tolerant synthesis of non-Clifford gates.

Improved adders and multiplication architectures therefore materially change practical resource estimates even though the asymptotic algorithm is unchanged.

10. Measuring the second register is optional conceptually

If the second register is measured and returns some residue f(x₀), the first register collapses approximately to a periodic comb

|x₀⟩+|x₀+r⟩+|x₀+2r⟩+…

within the allowed range.

One does not need to physically perform this intermediate measurement in an optimised circuit. It is a useful derivation device explaining why periodicity appears in the first register.

11. Fourier transform turns period into frequency peaks

Apply the QFT over Q points:

|x⟩→(1/√Q)Σ_{y=0}^{Q−1}e^{2πixy/Q}|y⟩.

For an exactly periodic comb with period r dividing Q, constructive interference occurs at

y=kQ/r

for integer k.

When r does not divide Q, peaks occur near these rational locations.

12. Equivalent phase-estimation view

Define modular multiplication unitary

U_a|z⟩=|az mod N⟩

on the unit subspace modulo N.

Along the orbit

|1⟩,|a⟩,…,|a^{r−1}⟩,

U_a acts as a cyclic shift.

Its eigenstates have eigenvalues

e^{2πik/r}, k=0,…,r−1.

Quantum phase estimation on U_a therefore returns an approximation to k/r.

13. Orbit eigenstates

One convenient convention is

|u_k⟩=(1/√r)Σ_{j=0}^{r−1}e^{-2πikj/r}|a^j mod N⟩.

Then

U_a|u_k⟩=e^{2πik/r}|u_k⟩.

The easy computational state |1⟩ is an equal superposition of all these eigenstates:

|1⟩=(1/√r)Σ_k|u_k⟩.

Thus phase estimation samples a random k/r phase without needing to prepare a particular eigenstate explicitly.

14. Measurement gives a rational approximation

After QFT/phase estimation, measurement gives integer y such that

y/Q≈k/r.

The quantum part does not usually print r directly.

Classical post-processing must infer the denominator r from the measured rational approximation.

15. Continued fractions

A classical theorem says that if a rational k/r in lowest terms satisfies

|y/Q−k/r|<1/(2r²),

then k/r appears as a convergent in the continued-fraction expansion of y/Q.

Choosing Q≥N² and knowing r<N makes the phase resolution fine enough for this criterion when the QFT sample lands near kQ/r.

Generate continued-fraction convergents and test candidate denominators r’ by checking

a^{r'} mod N=1.

16. Worked continued-fraction example

For N=15, a=2, true order r=4. Choose Q=256.

Ideal Fourier peaks occur at

• y=0;
• y=64;
• y=128;
• y=192.

If y=64,

y/Q=64/256=1/4.

The continued fraction is exactly [0;4], immediately revealing denominator 4.

If y=128, the fraction is 1/2. Its reduced denominator is 2, not 4. Testing a² mod 15 gives 4 rather than 1, so denominator 2 is rejected. Another quantum sample may be needed.

17. Why gcd(k,r) matters

Phase estimation samples k approximately uniformly from {0,…,r−1}.

If k/r is not in lowest terms, continued fractions first reveal denominator

r/gcd(k,r).

When gcd(k,r)=1, the true order appears directly.

Otherwise one can gather another sample, combine denominator information using least common multiples in advanced post-processing, or test multiples of the candidate denominator.

18. Failure case: odd order

If r is odd, r/2 is not an integer and the difference-of-squares factorisation cannot be used.

Example: if an allowed base happens to have order 3, then a³≡1 but no integer a^r/2 exists.

The remedy is simple: choose another random a and rerun order finding.

19. Failure case: a^(r/2)≡−1 mod N

Even order alone is not sufficient.

If

a^{r/2}≡−1 (mod N),

then

• gcd(a^{r/2}−1,N) may be 1;
• gcd(a^{r/2}+1,N)=N.

No nontrivial factor is obtained.

Again choose another random a.

20. Success probability from random bases

For composite N that is not a prime power, a substantial fraction of random coprime bases produce an even order with a^r/2≠−1 mod N.

The factoring procedure is therefore probabilistic but has constant-order success probability after accounting for order-recovery sampling.

Repeating independently drives failure probability down exponentially in the number of attempts.

“Probabilistic” does not mean heuristic here: the algorithm has rigorous success guarantees under ideal quantum operations.

21. Semiclassical inverse QFT

The phase-estimation control register need not always be stored in many qubits simultaneously.

Semiclassical/iterative phase estimation can reuse one control qubit, measure phase bits sequentially and feed classical outcomes forward into later rotations.

This trades qubit width for repeated coherent controlled modular multiplications and classical feed-forward.

Resource estimates must therefore distinguish logical qubit count, circuit depth and non-Clifford gate count.

22. Approximate QFT

Small controlled rotations in the exact QFT can be omitted when their contribution is below the phase-precision budget.

An approximate QFT reduces gate count from the exact dense pattern while preserving enough phase resolution for order finding.

The acceptable cutoff depends on n and desired success probability; it is not valid to discard arbitrary rotations without bounding the accumulated error.

23. Shor and discrete logarithms

Shor’s original result also solves discrete logarithms in suitable finite cyclic groups in polynomial quantum time.

The discrete-log algorithm uses a two-dimensional periodic/Fourier structure rather than exactly the same one-dimensional order-finding post-processing.

This has cryptographic importance because classical public-key systems based on integer factorisation and discrete logarithms—including finite-field and elliptic-curve variants—would not remain secure against a sufficiently large fault-tolerant quantum computer running the appropriate Shor-type algorithms.

24. Shor does not instantly break modern cryptography today

The mathematical algorithm assumes large coherent fault-tolerant quantum computation.

Factoring cryptographic key sizes requires many logical operations protected by quantum error correction, plus substantial physical-qubit overhead.

Current security planning therefore distinguishes the existence of Shor’s polynomial algorithm from the engineering timeline for machines capable of executing it at cryptographic scale.

Post-quantum cryptography addresses this future threat using mathematical problems not known to admit comparable quantum attacks.

25. Factoring complexity compared with classical algorithms

The general number field sieve has subexponential but superpolynomial asymptotic complexity in log N.

Shor’s ideal quantum algorithm has polynomial complexity in log N.

The asymptotic separation is therefore stronger than a quadratic Grover-type speedup.

However, asymptotic complexity does not determine the crossover size on real hardware. Constants and fault-tolerance overhead dominate practical feasibility.

26. Order finding as an Abelian hidden subgroup problem

The function f(x)=a^x mod N satisfies

f(x)=f(y) iff x−y∈rℤ.

The hidden subgroup of ℤ is rℤ.

Fourier sampling reveals characters orthogonal to that subgroup, which encode multiples of 1/r.

This unifies Shor with Simon and other hidden-period algorithms developed in Guide 66.

27. Verification is easy

Once candidate factors p and q are returned, checking them is classical and cheap:

pq=N.

Likewise a candidate order r can be verified by modular exponentiation:

a^r mod N=1.

To verify that r is the minimal order, factor r or test prime divisors q of r and check whether a^r/q≠1. Exact minimality is often unnecessary for factor extraction if a suitable multiple of the order still yields the correct gcd structure.

28. Common misconception: the QFT factors N

The QFT reveals periodic frequency structure. Modular arithmetic encodes the period. Continued fractions infer the order. GCD arithmetic turns that order into factors. No single component is “the factoring step” by itself.

29. Common misconception: Shor searches all divisors in superposition

The algorithm does not evaluate divisibility of all candidate factors and select one. It exploits the periodicity of modular exponentiation and interference in Fourier/phase space.

30. Common misconception: one run always gives the factor

A phase sample may reveal a reduced denominator, a chosen base may have odd order, or a^r/2 may equal −1 mod N. The algorithm explicitly allows repetition and retains polynomial expected complexity.

31. Worked synthesis: factor 15 from start to finish

Step 1: Choose base. a=2. gcd(2,15)=1.

Step 2: Quantum order finding. Prepare modular exponentiation f(x)=2^x mod 15 and Fourier sample. A useful sample gives phase 1/4.

Step 3: Continued fractions. Denominator candidate is r=4.

Step 4: Verify order. 2⁴ mod 15=1, while 2² mod 15=4≠1.

Step 5: Check parity. r is even.

Step 6: Check nontrivial square root. 2²=4≠−1 mod 15.

Step 7: Extract factors. gcd(4−1,15)=3 and gcd(4+1,15)=5.

Step 8: Verify. 3×5=15.

32. Practice set

1. What is the relevant input size for factoring N?
2. Why compute gcd(a,N) before using the quantum computer?
3. Define the multiplicative order of a modulo N.
4. Why must r usually be even for Shor’s factor extraction?
5. Why is a^r/2≠−1 mod N required?
6. What periodic function is evaluated quantumly?
7. How is modular exponentiation implemented efficiently from the bits of x?
8. What information does QFT/phase estimation return?
9. Why are continued fractions used?
10. Why can k/r reveal a denominator smaller than r?
11. What are the two final gcds?
12. Why is Shor best understood as an order-finding algorithm rather than a divisor-search algorithm?

Answers

1. n=⌈log₂N⌉ bits.
2. If gcd(a,N)>1, it already gives a nontrivial factor; if it equals 1, multiplicative order exists in the unit group.
3. The smallest positive r with a^r≡1 mod N.
4. The factorisation a^r−1=(a^r/2−1)(a^r/2+1) requires integer r/2.
5. If it equals −1, one gcd becomes trivial and the other can equal N.
6. f(x)=a^x mod N.
7. Repeated squaring computes constants a^{2^j} mod N, controlled by bits x_j.
8. An approximation to a rational k/r encoded in Fourier/eigenphase frequency.
9. They recover a small denominator from a sufficiently accurate rational approximation.
10. If gcd(k,r)>1, k/r reduces before the denominator is observed classically.
11. gcd(a^{r/2}−1,N) and gcd(a^{r/2}+1,N).
12. The quantum advantage comes from estimating the modular period/order; classical gcd arithmetic then yields factors.

Sources and further study

[1] Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing 26, 1484–1509 (1997). The foundational factoring and discrete-logarithm algorithm.

[2] Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press. Standard derivation of order finding, phase estimation and continued-fraction post-processing.

[3] Stéphane Beauregard, Circuit for Shor’s algorithm using 2n+3 qubits. A compact circuit architecture illustrating arithmetic/width trade-offs.

[4] Craig Gidney and Martin Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. A concrete fault-tolerant resource-estimation study illustrating the gap between polynomial algorithms and engineering cost.

Continue through Quantum Mathematics

Guide 66: Hidden Subgroup Problems, Simon’s Algorithm, Fourier Sampling and Abelian Quantum Algorithms places order finding inside the larger hidden-subgroup framework. Guide 67: Quantum Gibbs-State Preparation, Thermal Sampling, Partition Functions and Quantum Metropolis Methods develops thermal-state algorithms. Guide 68: Quantum Semidefinite Programming, Matrix Multiplicative Weights, Convex Optimisation and Quantum SDP Solvers develops quantum convex optimisation.

Return to the BTT Mathematics Learning Hub.