Shor Algorithm

Shor’s algorithm factors integers by finding the period of modular exponentiation. A quantum Fourier measurement reveals information about that period; classical continued fractions and greatest common divisors turn it into factors. The algorithm runs in expected time polynomial in the number of input bits. It also solves discrete logarithms in efficiently represented finite cyclic groups.

The quantum computer does not read out a list of trial divisors. Its advantage comes from coherent arithmetic followed by interference. Preparing that arithmetic is usually more costly than the Fourier transform itself. Below, the factoring reduction is developed first, followed by the discrete-logarithm construction and the distinction between a logical algorithm and a physical implementation.

Helpful background. Quantum phase estimation supplies the eigenphase distribution and confidence bounds; the quantum Fourier transform explains how periodic amplitudes interfere.

Factoring through a multiplicative order

Assume classical preprocessing has removed factors of two, identified primes and detected perfect powers. For a perfect power $N=b^e$, it suffices to factor the smaller integer $b$. We may therefore take $N$ odd, composite and not a perfect power. Primality testing, perfect-power detection, modular exponentiation and greatest common divisors have polynomial-time classical algorithms. The input length is $n=\lfloor\log_2N\rfloor+1$.

Choose an integer $a$ uniformly from

$$2\leq a\leq N-1$$

and compute

$$d=\gcd(a,N).$$

If $d>1$, then $d$ is already a nontrivial factor. Otherwise $a$ is invertible modulo $N$, and its multiplicative order modulo $N$ is

$$\begin{aligned} r &= \operatorname{ord}_N(a) \\ &= \min\left\{ r\geq1: a^r\equiv1\pmod N \right\}. \end{aligned}$$

Suppose order finding returns an even $r$. Set

$$x=a^{r/2}\bmod N.$$

Then

$$x^2 \equiv a^r \equiv1 \pmod N,$$

so

$$(x-1)(x+1) \equiv0 \pmod N.$$

Minimality of $r$ implies $x\not\equiv1\pmod N$. If also

$$x\not\equiv-1\pmod N,$$

then neither factor $x-1$ nor $x+1$ is divisible by all of $N$. The classical computations

$$\gcd(x-1,N), \qquad \gcd(x+1,N)$$

therefore reveal nontrivial factors.

If $r$ is odd or $x\equiv-1\pmod N$, the run has supplied no factor. This is not an undetected error: discard that base and try another.

Why a useful base occurs often enough

Write the preprocessed odd integer as a product involving $k\geq2$ distinct odd primes. Let $G$ be the event

$$\begin{gathered} r\text{ is even}, \\ a^{r/2}\not\equiv-1\pmod N. \end{gathered}$$

For a uniformly chosen invertible residue, finite-group counting gives

$$\Pr(G) \geq 1-\frac1{2^{k-1}} \geq \frac12.$$

One way to see the bound is to use the Chinese remainder theorem. On each odd prime-power factor, write the local order as an odd number times $2^{t_i}$. A useful square root fails precisely when all $t_i$ coincide, including the all-zero case. These exponents are independent for a uniform invertible residue, and each value in any one local distribution has probability at most $1/2$. Conditioning on the first exponent therefore bounds the failure probability by $2^{-(k-1)}$.

Excluding the base $a=1$ removes only an unsuccessful choice, so the same lower bound applies to the sampling range above. A non-coprime base helps through the initial gcd. Exact order finding thus gives a constant chance of progress; recovering the full order from finite Fourier samples has an additional success factor discussed below.

Worked example: factoring 15

Take $N=15$ and choose $a=2$. Since

$$\gcd(2,15)=1,$$

find the powers

$$\begin{aligned} 2^1&\equiv2, & 2^2&\equiv4, \\ 2^3&\equiv8, & 2^4&\equiv1\pmod{15}. \end{aligned}$$

The order is $r=4$. Therefore

$$x=2^{r/2}=2^2=4$$

and

$$\begin{aligned} \gcd(4-1,15)&=3, \\ \gcd(4+1,15)&=5. \end{aligned}$$

This verifies the arithmetic reduction. A general factoring circuit must obtain the period without having it or the factors supplied during circuit construction.

Quantum order finding

The function

$$f(x)=a^x\bmod N$$

is periodic with least positive period $r$ because

$$f(x+r) = a^xa^r \equiv a^x = f(x) \pmod N.$$

The quantum circuit makes many values of $x$ interfere coherently so that this period appears as a reciprocal spacing in Fourier space.

Periodic-state formulation

Choose a power of two

$$Q=2^t$$

and prepare two registers as

$$\frac1{\sqrt Q} \sum_{x=0}^{Q-1} \lvert x\rangle\lvert1\rangle.$$

Reversible modular exponentiation computes

$$\frac1{\sqrt Q} \sum_{x=0}^{Q-1} \lvert x\rangle \lvert a^x\bmod N\rangle.$$

If the second register is measured with result $a^{x_0}\bmod N$, the first register is left in a truncated periodic progression,

$$\frac1{\sqrt L} \sum_j \lvert x_0+jr\rangle,$$

Here choose $0\leq x_0<r$, let $j=0,\ldots,L-1$, and set $L=1+\lfloor(Q-1-x_0)/r\rfloor$. The progression is exact; it is truncated by the finite register boundary. Measuring the second register is optional: ignoring it produces the same first-register statistics.

Applying the inverse QFT over $\mathbb Z_Q$, with the same convention as phase estimation, gives constructive interference near

$$y \approx \frac{sQ}{r}, \qquad s\in\{0,1,\ldots,r-1\}.$$

The measured ratio $y/Q$ therefore approximates $s/r$. When $r$ divides $Q$, these are exact Fourier bins. In general the peaks have finite width, and continued fractions recover the nearby rational.

Phase-estimation formulation

The same computation can be expressed as eigenphase estimation. On the orbit generated by $a$, define modular multiplication

$$M_a\lvert y\rangle = \lvert ay\bmod N\rangle.$$

Because $\gcd(a,N)=1$, multiplication by $a$ permutes all residues $0\leq y<N$, not only the invertible ones. On an $n$-qubit register, define it as the identity on $N\leq y<2^n$. This specifies a permutation unitary on the entire encoded space. Reversible arithmetic must also restore any workspace used to implement it. The orbit

$$\lvert1\rangle, \lvert a\rangle, \ldots, \lvert a^{r-1}\bmod N\rangle$$

has length $r$. Its Fourier eigenstates are

$$\lvert u_s\rangle = \frac1{\sqrt r} \sum_{k=0}^{r-1} e^{-2\pi isk/r} \lvert a^k\bmod N\rangle,$$

and direct index shifting gives

$$M_a\lvert u_s\rangle = e^{2\pi is/r} \lvert u_s\rangle.$$

The easy input $\lvert1\rangle$ is an equal superposition of these eigenstates:

$$\lvert1\rangle = \frac1{\sqrt r} \sum_{s=0}^{r-1} \lvert u_s\rangle.$$

Consequently the exact output distribution is an equal-weight mixture of the finite-resolution QPE distributions for $s/r$. The latent eigenphase labels have exactly uniform weights; the measured binary bins need not be equally likely. It is unnecessary to prepare an unknown eigenstate. A finite-resolution outcome can leave several orbit eigenstates coherently present in the target.

Controlled powers are efficient arithmetic

QPE calls controlled powers

$$M_a,\, M_a^2,\, M_a^4,\, \ldots,\, M_a^{2^{t-1}}.$$

The crucial identity is

$$M_a^{2^j}\lvert y\rangle = \left\lvert a^{2^j}y\bmod N \right\rangle.$$

Each constant $a^{2^j}\bmod N$ is computed efficiently by classical repeated squaring. The quantum circuit then performs controlled reversible multiplication by that known constant. It does not repeat a base circuit $2^j$ times. This arithmetic structure is what keeps order finding polynomial.

Continued fractions and verified factors

Let $y$ be the measured Fourier outcome. Take

$$t=2n, \qquad Q=2^t.$$

Since $Q>N^2$ and $r<N$, a nearest-bin outcome obeys

$$\left\lvert \frac yQ-\frac sr \right\rvert \leq \frac1{2Q} < \frac1{2r^2}.$$

Legendre’s continued-fraction theorem says that if $s/r$ is in lowest terms and a rational approximation satisfies this bound, then $s/r$ appears among the continued-fraction convergents of $y/Q$. Test the candidate denominator by modular exponentiation:

$$a^{r_{\mathrm{cand}}} \stackrel{?}{\equiv} 1 \pmod N.$$

This test proves that the candidate is a multiple of the true order, not necessarily the least order. For example, $2^8\equiv1\pmod{15}$, but $\operatorname{ord}_{15}(2)=4$.

For factoring, a verified even multiple $q$ can still be tried: compute $x=a^{q/2}\bmod N$ and accept only if $x\not\equiv\pm1\pmod N$. Then $\gcd(x\pm1,N)$ gives nontrivial factors. Unlike the case of the least even order, $x=1$ is now possible and must be checked. A returned factor is always confirmed by division, so an inaccurate Fourier sample need not become an incorrect factorization.

One simple implementation scans the continued-fraction convergents with denominator below $N$, tests them and repeats when none gives a useful factor. Successful nearest-bin samples with $\gcd(s,r)=1$ include the true order among these candidates. This is enough for the polynomial expected-runtime guarantee.

When the sampled fraction is not reduced

If

$$g=\gcd(s,r)>1,$$

then

$$\frac sr = \frac{s/g}{r/g}$$

and continued fractions reveal only the divisor $r/g$. The probability that one uniformly sampled $s$ is coprime to $r$ is

$$\frac{\varphi(r)}r,$$

where $\varphi$ is Euler’s totient function. It is not bounded below by a positive constant for all $r$, but its inverse grows at most on the order of $\log\log r$ asymptotically. A nearest-bin event has probability at least $4/\pi^2$ for every $s$, so useful rational reconstruction remains efficient in expectation.

Several valid reduced denominators can reveal the order together. For $N=21$ and $a=2$, the true order is six. With $Q=1024$, a result $y=341$ can reveal $1/3$ while $y=512$ reveals $1/2$. Neither denominator passes the modular test alone: $2^3\equiv8$ and $2^2\equiv4\pmod{21}$. Their least common multiple is six, which passes. It gives $x=2^3=8$ and factors $\gcd(7,21)=7$, $\gcd(9,21)=3$.

Two incomplete denominator estimates can complement one another. The figure follows particular outcomes for $N=21$, $a=2$ and $Q=1024$. Each rational approximation and the combined modular result are checked classically; arbitrary noisy denominators cannot simply be assumed to divide the true order.

The end-to-end success probability therefore combines three events:

1. the random base has a useful even order;
2. Fourier sampling lands close enough to a rational $s/r$;
3. the sampled numerator exposes enough of the denominator.

The individual reasons for failure are not all observable from one output: the sampled $s$ and its approximation error are unknown. What can be checked is whether the proposed arithmetic gives a nontrivial divisor. A complete runtime includes repeats, and complete prime factorization recursively factors the divisors obtained.

Discrete logarithms as hidden subgroups

The Fourier idea also appears in Simon’s algorithm, where one solves binary equations. Discrete logarithms instead produce modular equations over a cyclic group.

Let $G=\langle g\rangle$ be a cyclic group of known order $r$, and suppose

$$h=g^x.$$

Assume group elements have efficient encodings and coherent reversible group operations. The discrete-logarithm problem asks for $x\bmod r$. Define

$$F(a,b) = g^a h^{-b} = g^{a-bx}, \qquad (a,b)\in\mathbb Z_r^2.$$

Two pairs have the same function value exactly when their difference lies in the subgroup

$$H = \left\{ (tx,t): t\in\mathbb Z_r \right\} = \langle(x,1)\rangle.$$

Thus $F$ hides a cyclic subgroup of order $r$ in the product group $\mathbb Z_r^2$. A coherent evaluation of $F$, followed by a two-register QFT, samples characters orthogonal to $H$. An observed pair $(u,v)$ satisfies

$$ux+v \equiv0 \pmod r.$$

When $u$ is invertible modulo $r$,

$$x \equiv -vu^{-1} \pmod r.$$

If $u$ is not invertible, the sample determines only a congruence modulo $r/\gcd(u,r)$. Several samples suffice once $\gcd(u_1,\ldots,u_t,r)=1$: an extended-gcd calculation finds coefficients $c_i$ with $\sum_i c_i u_i\equiv1\pmod r$, and then $x\equiv-\sum_i c_i v_i\pmod r$. Verify the result by checking $g^x=h$.

For example, modulo six the equations $2x\equiv4$ and $3x\equiv0$ determine $x\equiv2\pmod3$ and $x\equiv0\pmod2$, respectively. Together they give $x=2\pmod6$, although neither coefficient is invertible modulo six.

The relation $ux+v=0$ follows by summing a character over $(tx,t)$; choosing $h^b$ instead of $h^{-b}$ changes the subgroup and the relative sign. Reversing both Fourier signs leaves the same zero relation. For non-power-of-two $r$, the group QFT must be synthesized to a sufficient approximation; its error belongs in the success probability.

This construction applies to multiplicative groups of finite fields and, in additive notation, to elliptic-curve groups. For points $P$ and $Q=xP$, the coherent group operation evaluates $aP-bQ$. Efficient reversible point addition replaces modular multiplication, but the Fourier and classical linear-algebra logic is the same.

Logical complexity and physical cost

For an $n$-bit modulus, order finding uses $O(n)$ register qubits and $O(n)$ controlled modular multiplications by classically computed constants. A typical schoolbook reversible multiplication uses $O(n^2)$ gates, leading to roughly cubic arithmetic cost. The QFT on $O(n)$ controls contributes $O(n^2)$ gates before rotation synthesis; it is not the dominant step in these constructions.

Space, depth and gate count can be traded against one another. Beauregard’s compact construction uses $2n+3$ logical qubits, $O(n^3\log n)$ elementary gates and depth $O(n^3)$. These are circuit resources, not physical-qubit counts. Actual counts also depend on the elementary gate alphabet and accuracy of small rotations.

The general number field sieve provides a classical comparison with heuristic asymptotic running time

$$\begin{aligned} L_N[1/3,c]&=\exp\!\left[(c+o(1))(\ln N)^{1/3} (\ln\ln N)^{2/3}\right],\\ c&=(64/9)^{1/3}. \end{aligned}$$

This is subexponential in $n$ but superpolynomial. Shor’s polynomial algorithm improves on that scaling; it does not prove that every classical factoring algorithm must be superpolynomial. Factoring is not known to be NP-complete, and the result does not make arbitrary NP-complete problems easy. Quantum complexity classes explains these distinctions.

Physical error correction adds another layer. If $G$ logical operation locations each have failure probability bounded by $p_L$, a union bound gives total failure probability at most $Gp_L$, without requiring independence. Keeping this below $\eta$ requires $p_L\leq\eta/G$ in this uniform allocation. Code distance, memory duration, routing, non-Clifford-state production and classical feedforward then determine physical space and elapsed time. A logical qubit count alone supplies none of those quantities.

The derivation of these costs is developed in resource estimation; changing architectural proposals are compared in resource-estimation frontiers. Numerical projections are conditional models, not dates by which a machine will exist.

Cryptographic consequences and small demonstrations

At a sufficient fault-tolerant scale, the algorithms attack these underlying mathematical problems:

Problem	Examples affected
Factoring an RSA modulus	RSA encryption and signatures
Finite-field discrete logarithm	Diffie–Hellman, ElGamal and DSA
Elliptic-curve discrete logarithm	ECDH and ECDSA

For RSA, factors of $N=pq$ allow reconstruction of the private exponent. For an elliptic curve, solving $Q=xP$ reveals the private scalar. Efficient reversible group arithmetic is needed in each case. Shor’s algorithm does not directly solve generic symmetric-key search; Grover search addresses that different task.

Post-quantum cryptography uses classical algorithms designed to resist known quantum attacks. It is distinct from quantum key distribution and does not require quantum communication. See cryptography case studies for the systems context.

A small experiment can test phase kickback, modular arithmetic or Fourier decoding without demonstrating a scalable factoring computation. Optimizations based on the known input $N$ and $a$ are legitimate if they can themselves be computed efficiently. Supplying the unknown period or factors to the compiler removes the hard part. Smolin, Smith and Vargo’s analysis of oversimplified factoring demonstrations makes this distinction concrete. A general implementation must retain the coherent arithmetic and the cost of finding and verifying the answer.

Exercises

1. Factor 15 from an order

For $N=15$ and $a=2$, determine the order $r$ and use it to recover both prime factors.

Solution

The powers modulo $15$ are

$$2,4,8,1,$$

so $r=4$. Since $r$ is even,

$$x=2^{r/2}=2^2=4.$$

Then

$$\gcd(x-1,15)=\gcd(3,15)=3$$

and

$$\gcd(x+1,15)=\gcd(5,15)=5.$$

Both gcds are nontrivial, giving $15=3\times5$.

2. Diagnose an unhelpful base

For $N=15$, choose $a=14$. Find its order and explain why the gcd step after order finding fails.

Solution

Since

$$14\equiv-1\pmod{15},$$

we have $14^2\equiv1\pmod{15}$ and therefore $r=2$. The order is even, but

$$x=14^{r/2}=14\equiv-1\pmod{15}.$$

Consequently

$$\gcd(x-1,15)=\gcd(13,15)=1$$

and

$$\gcd(x+1,15)=\gcd(15,15)=15.$$

Neither is a nontrivial factor. The run is recognized as unhelpful and a new base is chosen.

3. Verify the modular-multiplication eigenstate

Starting from

$$\lvert u_s\rangle = \frac1{\sqrt r} \sum_{k=0}^{r-1} e^{-2\pi isk/r} \lvert a^k\bmod N\rangle,$$

prove that $M_a\lvert u_s\rangle=e^{2\pi is/r}\lvert u_s\rangle$.

Solution

Apply $M_a$ and shift the summation index to $j=k+1$ modulo $r$:

$$\begin{aligned} M_a\lvert u_s\rangle &= \frac1{\sqrt r} \sum_{k=0}^{r-1} e^{-2\pi isk/r} \times \lvert a^{k+1}\bmod N\rangle\\ &= \frac1{\sqrt r} \sum_{j=0}^{r-1} e^{-2\pi is(j-1)/r} \times \lvert a^j\bmod N\rangle\\ &= e^{2\pi is/r} \lvert u_s\rangle. \end{aligned}$$

The wraparound term is valid because $a^r\equiv1\pmod N$.

4. Recover a denominator by continued fractions

Suppose order finding uses $Q=256$ and measures $y=73$. Show that $2/7$ is a convergent of $73/256$ and verify the rational-reconstruction error bound for denominator $7$.

Solution

The Euclidean algorithm gives

$$\frac{73}{256} = [0;3,1,1,36].$$

Its convergents include

$$0,\quad \frac13,\quad \frac14,\quad \frac27,\quad \frac{73}{256}.$$

The approximation error is

$$\left\lvert \frac{73}{256}-\frac27 \right\rvert = \frac1{1792} \approx5.58\times10^{-4}.$$

Since

$$\frac1{1792} < \frac1{2\cdot7^2} = \frac1{98},$$

Legendre’s sufficient condition holds. A candidate order $7$ must still be checked by testing $a^7\bmod N$.

5. Why use about twice the input bit length?

Let $r<N<2^n$ and choose $Q=2^{2n}$. Show that a nearest Fourier bin $y$ satisfies the continued-fraction accuracy condition for $s/r$.

Solution

A nearest integer to $Qs/r$ obeys

$$\left\lvert y-\frac{Qs}{r} \right\rvert \leq\frac12.$$

Dividing by $Q$ gives

$$\left\lvert \frac yQ-\frac sr \right\rvert \leq \frac1{2Q}.$$

Because $Q=2^{2n}$ and $N<2^n$,

$$Q>N^2>r^2.$$

Therefore

$$\left\lvert \frac yQ-\frac sr \right\rvert < \frac1{2r^2},$$

which is the desired sufficient condition.

6. A discrete-logarithm Fourier relation

In the group $\mathbb Z_7^\times$, let $g=3$ and $h=2$. First find $x$ such that $h=g^x$. Then check that the Fourier sample $(u,v)=(1,4)$ satisfies the hidden-subgroup relation $ux+v\equiv0\pmod6$.

Solution

The powers of $3$ modulo $7$ begin

$$3^1\equiv3, \qquad 3^2\equiv2.$$

Thus $x=2$ in the cyclic group of order $6$. For the sample $(1,4)$,

$$ux+v = 1\cdot2+4 = 6 \equiv0 \pmod6.$$

Because $u=1$ is invertible,

$$x \equiv -vu^{-1} \equiv -4 \equiv2 \pmod6.$$

7. A candidate multiple and a logical error budget

For $N=15$ and $a=2$, show why candidate $q=8$ passes $a^q\equiv1$ but fails the factor-recovery step. Separately, if a circuit has $10^8$ logical operation locations and allocates failure probability $0.01$ to them, give a sufficient uniform per-location bound. Does it determine the physical-qubit count?

Solution

The least order is four, so eight is a multiple and $2^8\equiv1\pmod{15}$. But $x=2^{8/2}\equiv1\pmod{15}$, giving gcds $15$ and $1$. This is why an unproven candidate multiple requires checking both roots $x=\pm1$, even though the least even order cannot give $x=1$.

The union bound requires $10^8p_L\leq0.01$, or $p_L\leq10^{-10}$. It is a sufficient logical error allocation. Converting it to physical qubits requires a code and a noise model, plus the storage, routing and non-Clifford-operation costs. No physical-qubit number follows from this inequality alone.

References

• S. Beauregard, “Circuit for Shor’s algorithm using $2n+3$ qubits,” Quantum Information and Computation 3, 175–185, 2003, doi:10.26421/QIC3.2-8.
• J. P. Buhler, H. W. Lenstra Jr., and C. Pomerance, “Factoring integers with the number field sieve,” in The Development of the Number Field Sieve, 50–94, 1993, doi:10.1007/BFb0091539.
• A. Ekert and R. Jozsa, “Quantum computation and Shor’s factoring algorithm,” Reviews of Modern Physics 68, 733–753, 1996, doi:10.1103/RevModPhys.68.733.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press, 2010, doi:10.1017/CBO9780511976667.
• P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing 26, 1484–1509, 1997, doi:10.1137/S0097539795293172.
• J. A. Smolin, G. Smith, and A. Vargo, “Oversimplifying quantum factoring,” Nature 499, 163–165, 2013, doi:10.1038/nature12290.