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

Shor’s algorithm does not “try factors in superposition.” It reduces integer factoring to a periodicity problem, encodes that period as an eigenphase of modular multiplication, estimates the phase coherently, and then uses ordinary number theory to recover a nontrivial factor.

Guide 9 owns the Quantum Fourier Transform and Guide 10 owns quantum phase estimation. This guide owns the complete factoring pipeline: the classical reduction from factoring to order finding, the modular-multiplication unitary, eigenphase structure, continued-fraction post-processing, modular exponentiation, success conditions and realistic resource boundaries.

The theoretical importance is fundamental. Peter Shor showed that both integer factoring and discrete logarithms admit polynomial-time quantum algorithms in the standard circuit model. The practical difficulty is equally important: fault-tolerant modular arithmetic at cryptographically relevant sizes requires very large logical circuits.

Choose a coprime base → find its multiplicative order → recover the order from an eigenphase → use a square-root-of-one congruence → compute gcds → obtain factors.

1. The factoring problem

Given a composite integer N, find nontrivial integers p,q with

N=pq

or more generally recover its prime factorisation.

Classically, no polynomial-time factoring algorithm in log N is known. The best known general classical algorithms are subexponential, such as the general number field sieve.

Shor’s algorithm changes the computational primitive: it performs coherent period/order finding using quantum phase estimation.

2. Multiplicative order

Choose an integer a with

1<a<N

and compute gcd(a,N).

If gcd(a,N)>1, a factor has already been found.

Otherwise a belongs to the multiplicative group modulo N. Its order r is the smallest positive integer satisfying

a^r≡1 (mod N).

The quantum subroutine is devoted to finding r efficiently.

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

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

then neither factor is automatically divisible by all of N, and

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

and

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

have a good chance of exposing nontrivial factors.

4. Complete classical reduction for N=15

Choose a=2.

• 2^1≡2 mod15
• 2^2≡4 mod15
• 2^3≡8 mod15
• 2^4≡16≡1 mod15

Therefore r=4.

r is even and

2^{r/2}=2²=4≠−1≡14 mod15.

Now

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

The factorisation 15=3×5 is recovered.

5. Failure conditions are normal

A randomly chosen coprime a can fail to yield factors if:

• the order r is odd;
• a^{r/2}≡−1 modN;
• phase-estimation/post-processing returns insufficient information about r.

The algorithm simply chooses another a or repeats the quantum subroutine.

For odd composite N that is not a prime power, number-theoretic analysis gives constant-bounded success probability over random a, so a constant expected number of trials suffices up to amplification details.

6. Period-finding viewpoint

Consider the modular function

f(x)=a^x modN.

Because a^r≡1,

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

Finding multiplicative order is therefore finding the period of modular exponentiation.

The original descriptions of Shor’s algorithm can be phrased through a Fourier transform over sampled function values. Modern circuit explanations often phrase the same structure as phase estimation on modular multiplication.

7. Modular multiplication unitary

For gcd(a,N)=1, multiplication by a permutes the residue classes coprime to N.

Define

U_a|y⟩=|ay modN⟩

on the relevant modular register, extended unitarily to the full computational basis.

Repeated application gives

U_a^k|1⟩=|a^k modN⟩.

Because the orbit returns after r steps, U_a has r-th-root eigenphases on the orbit subspace.

8. Order-orbit eigenstates

Define orbit states

|a^k⟩=|a^k modN⟩, k=0,…,r−1.

For s=0,…,r−1 define

|u_s⟩=(1/√r)Σ_{k=0}^{r−1}e^{-2πisk/r}|a^k⟩.

Then

U_a|u_s⟩=e^{2πis/r}|u_s⟩.

The unknown denominator r is encoded in the eigenphase s/r.

9. Why starting from |1⟩ works

Preparing an exact eigenstate |u_s⟩ would require knowing r already.

Instead observe that

|1⟩=(1/√r)Σ_{s=0}^{r−1}|u_s⟩.

Phase estimation on |1⟩ therefore projects onto one random eigenstate and returns an estimate of s/r.

Different runs produce different numerators s. The common hidden denominator r can be reconstructed from sufficiently accurate samples and classical number theory.

10. Quantum phase estimation stage

Use a control register of t qubits and the work register containing |1⟩.

Phase estimation applies controlled powers

U_a^{2^0}, U_a^{2^1}, …, U_a^{2^{t−1}}

then an inverse QFT to the control register.

The measured integer c approximates

c/2^t≈s/r.

Choosing t around twice the bit length of N gives sufficient resolution for continued-fraction recovery with high constant probability under the standard analysis.

11. Continued fractions recover the denominator

If

|c/2^t−s/r|<1/(2r²),

then s/r appears as a convergent of the continued-fraction expansion of c/2^t.

Generate convergents p/q and test candidate denominators q by checking

a^q≡1 modN.

If gcd(s,r)>1, the reduced fraction may reveal only a divisor of r. Multiple samples or multiples of candidate denominators can recover the full order.

12. Worked rational reconstruction

Suppose the true order is r=4 and phase estimation samples s=1, so the phase is 1/4.

With t=8 control qubits, the ideal measured value is

c=2^8/4=64.

Then

c/256=64/256=1/4.

The continued fraction terminates immediately with denominator 4, and testing 2⁴ mod15 confirms the order.

13. Modular exponentiation is the expensive quantum arithmetic

The controlled powers required by phase estimation are implemented using repeated squaring classically and controlled modular multiplication quantumly.

Precompute classical constants

a^{2^j} modN.

The j-th phase-estimation control qubit conditionally multiplies the work register by that constant modulo N.

Reversible modular addition, multiplication and uncomputation dominate logical gate counts in practical Shor circuits—not the QFT itself.

14. Reversible arithmetic

Ordinary arithmetic circuits discard carries and intermediate values. A unitary quantum circuit cannot erase information irreversibly.

Therefore arithmetic is built from reversible primitives, often:

• Toffoli/CNOT networks;
• reversible adders;
• comparison and conditional subtraction;
• modular reduction;
• ancilla uncomputation.

Ancilla count, Toffoli/T-count and circuit depth depend strongly on the arithmetic architecture.

15. Semiclassical QFT can reduce qubit count

The inverse QFT in phase estimation can be performed semiclassically: measure one control qubit, feed the classical result forward to phases on later qubits, then reuse hardware.

This trades quantum width for low-latency classical control.

It does not remove the need for long coherent controlled modular exponentiation.

16. Complexity statement

Let n=⌈log₂N⌉ be the input bit length.

Shor’s factoring algorithm runs in time polynomial in n under the fault-tolerant circuit model, with exact polynomial exponents depending on arithmetic design and gate-cost model.

That is exponentially better in asymptotic input-size dependence than known general classical factoring algorithms.

Asymptotic polynomial time does not imply near-term practicality. Constant factors and error-correction overhead are enormous at cryptographic scales.

17. Cryptographic consequence

RSA security relies on the practical hardness of factoring a product of large primes for classical attackers.

A sufficiently large fault-tolerant quantum computer running Shor would break that hardness assumption.

Elliptic-curve and finite-field discrete-log cryptography is also vulnerable because Shor gave polynomial-time quantum algorithms for discrete logarithms.

This motivates post-quantum cryptography based on problems for which no analogous efficient quantum attack is known.

18. Factoring is not believed NP-complete

Shor’s speedup is sometimes described as “quantum computers solve NP-complete problems.” That is incorrect.

Factoring lies in NP and coNP, and no proof shows it NP-complete. Its exact relationship with BQP and classical complexity classes is subtler.

Guide 28 owns the broader BQP/QMA/complexity framework.

19. Noise destroys coherent period information

Order finding needs coherent modular arithmetic over a depth that grows polynomially with input size.

Small gate errors accumulate and distort the phase distribution. Near-term error mitigation is not enough to scale arbitrarily deep Shor circuits.

Large-number factoring therefore belongs to the fault-tolerant regime of Guides 25–27.

20. Resource estimation

Serious resource estimates report at least:

• logical qubits;
• Toffoli or T count;
• logical depth;
• physical error rate;
• error-correcting code distance;
• magic-state factory cost where applicable;
• runtime assumptions;
• classical feed-forward latency.

A headline physical-qubit number without these assumptions is not portable across architectures.

21. Common misconception: the QFT is the whole of Shor’s algorithm

The QFT is the phase-readout layer. The modular-exponentiation unitary that encodes the arithmetic period is the larger circuit resource.

22. Common misconception: phase estimation returns the order directly

It returns an approximation to a random eigenphase s/r. Continued fractions and modular tests recover r from that rational approximation.

23. Common misconception: every random base factors N on the first attempt

Odd orders and the case a^r/2≡−1 modN fail. Repetition is part of the algorithm.

24. Worked synthesis problem

Factor N=21 using base a=2, assuming the quantum subroutine returns the correct order.

Step 1: Coprime test. gcd(2,21)=1.

Step 2: Order. Powers modulo 21 are 2,4,8,16,11,1, so r=6.

Step 3: Even-order test. r is even.

Step 4: Half-order power. 2^3=8, and 8≠−1≡20 mod21.

Step 5: GCDs. gcd(8−1,21)=gcd(7,21)=7 and gcd(8+1,21)=gcd(9,21)=3.

Hence 21=3×7.

25. Practice set

1. Define the multiplicative order of a modulo N.
2. Why check gcd(a,N) before the quantum subroutine?
3. What two conditions on r and a^r/2 are needed for the standard factor-recovery step?
4. Write the modular multiplication unitary U_a.
5. What are its eigenphases on the order-r orbit?
6. Why can phase estimation start from |1⟩ instead of an eigenstate?
7. What rational number does the measured control register approximate?
8. What classical algorithm reconstructs candidate s/r?
9. Why can the recovered denominator be only a divisor of r?
10. Which part of practical Shor circuits dominates arithmetic resources?
11. What is the asymptotic input size?
12. Why does Shor threaten RSA but not imply efficient solutions to all NP-complete problems?

Answers

1. The least r>0 satisfying a^r≡1 modN.
2. A nontrivial gcd already gives a factor, so no quantum work is needed.
3. r must be even and a^{r/2}≠−1 modN.
4. U_a|y⟩=|ay modN⟩ on the modular orbit/register, extended unitarily.
5. e^{2πis/r} for s=0,…,r−1.
6. |1⟩ is an equal superposition of the orbit eigenstates.
7. s/r.
8. Continued fractions.
9. If s and r share a gcd, the rational fraction reduces before reconstruction.
10. Controlled reversible modular multiplication/exponentiation and its fault-tolerant arithmetic.
11. n=⌈log₂N⌉ bits.
12. RSA relies on factoring hardness, while factoring is not known to be NP-complete and Shor does not solve arbitrary NP-complete problems.

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

[2] Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press. Standard exposition of order finding, phase estimation and Shor’s algorithm.

[3] Stéphane Beauregard, Circuit for Shor’s Algorithm Using 2n+3 Qubits. A compact circuit architecture illustrating width–depth arithmetic 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 study under explicit architectural assumptions.

Continue through Quantum Mathematics

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

Return to the BTT Mathematics Learning Hub.