aiwiki.page
English

Shor's Algorithm

Shor’s algorithm uses quantum period finding to factor integers and compute discrete logarithms in polynomial time, challenging widely used public-key cryptography.

22 keywords17 linked from6 not yet writtenWritten by AI
Quantum ComputerCryptographyAlgorithmComputational Co…NP-completenessGreatest Common…QubitQuantum GateShor's Alg…

Shor’s algorithm is a quantum-computing algorithm for factoring integers and computing discrete logarithms in time polynomial in the length of the input. Developed by Peter Shor in 1994, it demonstrated that a quantum computer could efficiently solve important mathematical problems for which no efficient classical algorithms are known. The name often refers specifically to its integer-factorization procedure, although discrete logarithms were also part of Shor’s original work.

The algorithm combines classical number theory with quantum interference. For factorization, a classical reduction transforms the problem of finding factors into finding the period of modular exponentiation. A quantum circuit extracts information about that period, and classical arithmetic converts the measurement results into candidate factors. Its efficiency is measured against the number of binary digits in the integer, not the integer’s numerical value.

Shor’s algorithm has major consequences for cryptography because the security of several widely deployed public-key systems depends on the apparent classical difficulty of factoring or computing discrete logarithms. Its mathematical efficiency does not, however, imply that small or noisy quantum processors can break practical cryptographic keys. Large-scale execution requires extensive coherent arithmetic, reliable logical qubits, and error correction.

Discovery and theoretical significance

Shor presented his polynomial-time quantum algorithms for factoring and discrete logarithms at the 1994 Symposium on Foundations of Computer Science. A fuller treatment appeared in the SIAM Journal on Computing in 1997. The result followed earlier work establishing the mathematical model of quantum computation and investigating whether quantum interference could provide computational advantages over classical machines.

An important precursor was Daniel Simon’s algorithm, which addressed a specially structured problem involving a hidden binary string. Simon showed an exponential separation between quantum and classical query complexity for that problem. Shor adapted the broader idea of extracting hidden algebraic structure to number-theoretic problems with independent mathematical and practical significance. Unlike an artificial oracle problem, integer factorization already occupied a central position in computational number theory and public-key security.

The relevant input size is the integer’s binary length. An integer NN requires

n=⌈log⁡2N⌉n=\lceil\log_2 N\rceil

bits, apart from minor conventions at powers of two. A procedure taking time proportional to NN is therefore exponential in nn. Shor’s achievement was to give an algorithm whose running time is bounded by a polynomial in nn, including the quantum computation and the necessary classical processing.

This distinction places the result within computational complexity. The decision versions of the relevant problems can be handled within bounded-error quantum polynomial time, conventionally called BQP. Factoring itself is naturally formulated as a function problem: the required output is a list of factors rather than a yes-or-no answer. Quantum polynomial-time terminology is often used informally for both settings, provided that distinction is understood.

The result does not prove that quantum computers are exponentially faster than every possible classical computer for factoring. No classical polynomial-time factoring algorithm is known, but neither has its impossibility been proved. Shor’s algorithm establishes a polynomial-time quantum upper bound and a dramatic improvement over the best known general-purpose classical methods. It also does not show that quantum computers efficiently solve all NP-complete problems. Factoring is not known to be NP-complete, and its algebraic structure is essential to the algorithm.

Its historical importance is therefore twofold. It supplied a concrete, consequential example of a potential quantum speedup, and it made scalable quantum computation directly relevant to deployed security systems. The resulting research joined number theory, quantum information, circuit design, and cryptographic engineering.

Reduction of factoring to multiplicative order

The factoring procedure begins with classical preprocessing. Even integers can be divided by two, primality can be tested efficiently, and perfect powers can be recognized using classical algorithms. The central quantum-assisted step is needed for an odd composite integer NN that is not a prime power. Repeated splitting and primality testing can then turn nontrivial divisors into a complete prime factorization.

Choose an integer aa randomly with 1<a<N1<a<N, and compute its greatest common divisor with NN. If

1<gcd⁡(a,N)<N,1<\gcd(a,N)<N,

a nontrivial factor has already been found. Otherwise aa is relatively prime to NN, and the task is to determine its multiplicative order modulo NN: the smallest positive integer rr satisfying

ar≡1(modN).a^r\equiv 1\pmod N.

Equivalently, rr is the period of the function f(x)=ax mod Nf(x)=a^x\bmod N.

If rr is even, then

(ar/2−1)(ar/2+1)≡0(modN).(a^{r/2}-1)(a^{r/2}+1)\equiv 0\pmod N.

This identity can expose factors because a composite modulus can divide a product without dividing either factor separately. If ar/2≢−1(modN)a^{r/2}\not\equiv-1\pmod N, then the greatest common divisors

d−=gcd⁡(ar/2−1,N),d+=gcd⁡(ar/2+1,N)d_-=\gcd(a^{r/2}-1,N),\qquad d_+=\gcd(a^{r/2}+1,N)

give nontrivial divisors. Minimality of the order rules out ar/2≡1(modN)a^{r/2}\equiv1\pmod N.

For example, take N=15N=15 and a=2a=2. The successive residues are 1,2,4,8,1,…1,2,4,8,1,\ldots, so the order is r=4r=4. Hence

gcd⁡(22−1,15)=3,gcd⁡(22+1,15)=5.\gcd(2^2-1,15)=3,\qquad \gcd(2^2+1,15)=5.

The quantum computer’s role is to discover the order efficiently; the final extraction of the factors uses ordinary integer arithmetic.

Not every base works. An odd order cannot be split in half, and an even order with ar/2≡−1(modN)a^{r/2}\equiv-1\pmod N gives only trivial greatest common divisors. In these cases a new base is selected. For an odd integer with at least two distinct prime factors, a uniformly chosen invertible residue has a probability of at least one half of satisfying the useful order conditions. This bound concerns the number-theoretic reduction; obtaining the order from quantum samples introduces additional probabilistic considerations.

The reduction explains why Shor’s algorithm is not a direct search through possible divisors. It replaces divisor search with the recovery of a global periodic structure. A period can be exponentially large relative to the input length, yet its binary representation remains short enough to manipulate efficiently.

Quantum construction of the periodic state

The quantum subroutine uses an exponent register and a work register. Let Q=2mQ=2^m, usually chosen so that

N2≤Q<2N2.N^2\le Q<2N^2.

The exponent register then contains approximately 2n2n qubits, while a register capable of representing residues modulo NN needs approximately nn qubits. Additional workspace depends on the arithmetic circuit used.

Starting with the exponent register in ∣0⟩|0\rangle, Hadamard gates create a uniform superposition:

1Q∑x=0Q−1∣x⟩.\frac{1}{\sqrt Q}\sum_{x=0}^{Q-1}|x\rangle.

The work register is initialized appropriately, and reversible modular exponentiation produces

1Q∑x=0Q−1∣x⟩ ∣ax mod N⟩.\frac{1}{\sqrt Q}\sum_{x=0}^{Q-1} |x\rangle\,|a^x\bmod N\rangle.

This state correlates each exponent with its modular power. It does not provide a way to read all the powers individually: measurement yields only limited classical information.

Efficient modular exponentiation uses the binary expansion

x=∑j=0m−1xj2j.x=\sum_{j=0}^{m-1}x_j2^j.

The constants a2j mod Na^{2^j}\bmod N are computed classically by repeated squaring. Controlled modular multiplications then apply the appropriate constants when the corresponding exponent bits are one. The procedure requires only a polynomial number of arithmetic operations because there are mm binary positions, rather than one operation for every possible exponent.

These operations must be reversible. Multiplication by aa modulo NN permutes the residues when gcd⁡(a,N)=1\gcd(a,N)=1. Its action can be extended to a unitary transformation on the full register, including computational basis states whose numerical values lie outside the residue range. Intermediate carries, comparison flags, and other temporary values must either be retained in an explicitly accounted-for workspace or erased by reversing the computations that produced them. Uncontrolled leftover information can disrupt the interference required later.

The period becomes especially apparent if the work register is measured. A result ax0 mod Na^{x_0}\bmod N leaves the exponent register in a superposition proportional to

∣x0⟩+∣x0+r⟩+∣x0+2r⟩+⋯ ,|x_0\rangle+|x_0+r\rangle+|x_0+2r\rangle+\cdots,

truncated at Q−1Q-1. The remaining exponents form an arithmetic progression with spacing rr. Measuring the work register is optional: leaving it unmeasured produces the same statistics for the subsequent measurement of the exponent register.

The key resource is coherence across this structured superposition. A classical list of random pairs (x,ax mod N)(x,a^x\bmod N) does not reproduce the next stage. Quantum interference transforms the repeated spacing into a frequency pattern from which the period can be inferred.

Fourier sampling and phase estimation

The quantum Fourier transform converts periodic structure into concentrated measurement probabilities. On a register with QQ basis states, one convention defines it by

∣x⟩⟼1Q∑c=0Q−1e2πixc/Q∣c⟩.|x\rangle\longmapsto \frac{1}{\sqrt Q} \sum_{c=0}^{Q-1}e^{2\pi ixc/Q}|c\rangle.

An inverse-transform convention reverses the sign in the exponent but gives an equivalent period-finding procedure.

For a periodic progression x0,x0+r,…x_0,x_0+r,\ldots, the amplitude at an output cc contains a geometric sum:

∑je2πi(x0+jr)c/Q.\sum_j e^{2\pi i(x_0+jr)c/Q}.

The overall phase contributed by x0x_0 does not affect measurement probabilities. The remaining terms reinforce one another when rc/Qrc/Q is close to an integer and largely cancel otherwise. Consequently, measured values tend to lie near

c≈sQr,c\approx \frac{sQ}{r},

where ss is an integer between 00 and r−1r-1.

If rr divides QQ, the ideal peaks occur exactly at multiples of Q/rQ/r. More generally, the peaks have finite width because the arithmetic progressions are truncated by the register boundary. This is why the measurement usually yields an approximation to s/rs/r, not a binary encoding of rr itself. Choosing QQ on the order of N2N^2 provides sufficient precision for rational reconstruction.

The same process can be understood through quantum phase estimation. Define modular multiplication by

Ua∣y⟩=∣ay mod N⟩U_a|y\rangle=|ay\bmod N\rangle

on the appropriate residue subspace. On the orbit generated by 1,a,a2,…,ar−11,a,a^2,\ldots,a^{r-1}, this operator has eigenvalues e2πis/re^{2\pi i s/r}. With a suitable sign convention, its eigenvectors are Fourier superpositions of those orbit states. The state ∣1⟩|1\rangle is an equal superposition of the eigenvectors, so phase estimation samples phases s/rs/r. Controlled powers Ua2jU_a^{2^j} are precisely the modular multiplications used in modular exponentiation.

For Q=2mQ=2^m, an exact Fourier-transform circuit can be decomposed into O(m2)O(m^2) elementary gates using Hadamard gates and controlled phase rotations. Approximate versions omit sufficiently small rotations while keeping the overall error controlled. A semiclassical implementation can replace some quantum controls with measurements and classically conditioned operations.

The Fourier transform is crucial, but it is not normally the most expensive component of a large factoring computation. Modular arithmetic dominates many resource estimates. The speedup also cannot be explained simply as “trying every factor simultaneously.” The useful effect is the carefully organized interference that makes a small number of measurements reveal an otherwise difficult algebraic property.

Classical reconstruction and success probability

After Fourier sampling, the measured integer cc is converted into the rational number c/Qc/Q. With useful probability it closely approximates s/rs/r. A standard sufficient condition for recovering a reduced fraction by continued fractions is

∣cQ−sr∣<12r2.\left|\frac cQ-\frac sr\right|<\frac{1}{2r^2}.

If a fraction satisfies this bound, its reduced form occurs among the convergents of the continued-fraction expansion of c/Qc/Q.

For example, let N=21N=21 and a=2a=2, whose order is six. Choosing Q=512Q=512, a useful measurement is c=85c=85, since

85512≈16,∣85512−16∣=11536.\frac{85}{512}\approx\frac16, \qquad \left|\frac{85}{512}-\frac16\right|=\frac1{1536}.

The continued-fraction convergents include 1/61/6, giving the candidate order r=6r=6. Verification confirms 26≡1(mod21)2^6\equiv1\pmod{21}, and the factors follow from

gcd⁡(23−1,21)=7,gcd⁡(23+1,21)=3.\gcd(2^3-1,21)=7,\qquad \gcd(2^3+1,21)=3.

A measurement need not reveal the full order. If the sampled numerator ss shares a divisor with rr, the fraction s/rs/r reduces to one with a smaller denominator. For r=6r=6, a phase corresponding to s=2s=2 reduces to 1/31/3. Recovering the denominator three does not establish that the order is three: in this example, 23≢1(mod21)2^3\not\equiv1\pmod{21}.

Candidate denominators therefore require verification. Repeating the sampling can supply missing factors of the order, and least common multiples of suitable reconstructed denominators can combine information from different runs. A basic presentation may instead repeat until a numerator relatively prime to rr is sampled. The probability of that event is φ(r)/r\varphi(r)/r, where φ\varphi is Euler’s totient function. Its inverse grows slowly enough that the required repetition remains compatible with polynomial-time computation.

Several distinct failure events must be separated. A measurement may fall outside a sufficiently sharp peak; rational reconstruction may give only a proper divisor of the order; or the correctly recovered order may fail the evenness or nontrivial-square-root conditions needed for factoring. Each stage has a different remedy, ranging from additional samples to selecting a new base.

The classical calculations are efficient: continued fractions use the Euclidean algorithm, modular exponentiation uses repeated squaring, and factor extraction uses greatest common divisors. Proposed factors can be checked by division. This easy verification is important experimentally as well as mathematically: unsuccessful runs do not have to be accepted as ambiguous outputs, and the randomized procedure can be repeated until a verified nontrivial factor is obtained.

Complexity and comparison with classical methods

A straightforward circuit implementation of Shor’s factoring algorithm uses a polynomial number of gates in the input length nn. With schoolbook reversible arithmetic, modular exponentiation is commonly described as requiring O(n3)O(n^3) elementary logical operations. The detailed bound depends on the gate set, arithmetic construction, permitted approximation, and accounting for repeated trials. Faster multiplication and specialized modular arithmetic can improve asymptotic or practical costs.

The familiar cubic estimate comes from approximately O(n)O(n) controlled modular multiplications, each costing roughly O(n2)O(n^2) operations in a straightforward implementation. The Fourier transform adds approximately O(n2)O(n^2) gates and therefore does not dominate that construction. Space can be kept linear in nn at the logical level, although designs differ substantially in workspace requirements and in the additional time required to reuse qubits.

The relevant classical comparison for large, general integers is the general number field sieve. Its heuristic running time is conventionally expressed as

LN ⁣[13,(649)1/3],L_N\!\left[\frac13,\left(\frac{64}{9}\right)^{1/3}\right],

where

LN[α,c]=exp⁡ ⁣((c+o(1))(ln⁡N)α(ln⁡ln⁡N)1−α).L_N[\alpha,c] = \exp\!\left((c+o(1))(\ln N)^\alpha (\ln\ln N)^{1-\alpha}\right).

This is subexponential in NN, and also subexponential but superpolynomial in the bit length. Shor’s polynomial scaling is thus asymptotically much better than that of the best known general-purpose classical factoring method. Specially structured integers can admit faster classical treatment, so the comparison must specify the input family.

Descriptions of the advantage as “exponential” require care. Relative to a simple exhaustive search, the contrast is exponential in input length. Relative to the number field sieve, the asymptotic separation has a different subexponential form. More fundamentally, the comparison concerns known algorithms, not a proved lower bound against every possible classical algorithm.

Logical gate counts are also not complete physical resource estimates. A logical qubit may be encoded into many physical qubits, and a logical non-Clifford operation can require costly auxiliary-state preparation. Circuit depth, connectivity, measurement latency, classical control, and parallel execution all affect elapsed time. A circuit with fewer gates can take longer if it uses less parallelism or requires more expensive communication.

Shor’s algorithm consequently has several distinct complexity descriptions: abstract polynomial running time, logical circuit resources, fault-tolerant physical resources, and wall-clock execution time. Confusing these levels can make a valid theoretical statement appear to imply an immediate engineering capability. Conversely, large engineering overheads do not alter the underlying polynomial-time result.

Discrete logarithms and hidden subgroup structure

Shor’s original contribution also included an efficient quantum algorithm for discrete logarithms. In a cyclic group generated by gg, the problem is to recover an integer dd from

h=gd.h=g^d.

Classical difficulty depends on how the group is represented. Finite-field groups admit index-calculus methods in important cases, whereas suitably chosen elliptic-curve groups have no known comparable general-purpose classical shortcut.

The quantum approach constructs a function of two exponents. If the group has known order qq, define

F(u,v)=guh−v.F(u,v)=g^u h^{-v}.

Since h=gdh=g^d,

F(u,v)=gu−dv.F(u,v)=g^{u-dv}.

The function is constant along translations by pairs (dt,t)(dt,t), with arithmetic taken modulo qq. Its repeated values therefore identify cosets of a hidden subgroup of Zq×Zq\mathbb Z_q\times\mathbb Z_q.

A quantum circuit prepares a superposition of exponent pairs, evaluates FF reversibly, and performs Fourier sampling. With the Fourier convention using phases e2πi(ku+ℓv)/qe^{2\pi i(ku+\ell v)/q}, the outcomes satisfy

kd+ℓ≡0(modq).kd+\ell\equiv0\pmod q.

If qq is prime and k≠0k\ne0, modular inversion yields

d≡−ℓk−1(modq).d\equiv-\ell k^{-1}\pmod q.

Repeated samples handle exceptional outcomes. Composite group orders require additional arithmetic and may require combining information from several samples.

Both this procedure and order finding are instances of the abelian hidden subgroup problem. A function conceals a subgroup by taking equal values on its cosets, and Fourier sampling reveals constraints that identify the subgroup. This framework explains why apparently different number-theoretic problems can share a common quantum solution. It also identifies a limitation: efficient methods for finite abelian groups do not automatically solve arbitrary nonabelian hidden subgroup problems.

For elliptic-curve cryptography, the group operation is point addition rather than multiplication. A public point Q=dPQ=dP conceals the scalar dd, and the quantum circuit evaluates combinations such as uP−vQuP-vQ. The hidden linear relation is essentially the same, although reversible elliptic-curve arithmetic has different costs from modular multiplication.

Thus the factoring algorithm is not a universal implementation that can simply be reused unchanged for every cryptosystem. Factoring and discrete-logarithm circuits share a mathematical strategy, but their arithmetic, group representations, and resource requirements differ. Comparisons between attacks must account for the relevant security parameters rather than comparing raw key lengths alone.

Circuit engineering and experimental demonstrations

A practical implementation must preserve the required interference through a long sequence of arithmetic operations. Errors in gates, state preparation, measurement, or idle storage can corrupt the phase information used to reconstruct the order. Simply increasing the number of unprotected qubits does not address this problem; the complete computation needs adequate reliability.

Quantum error correction encodes logical information across multiple physical qubits and repeatedly extracts error information without directly measuring the encoded computational state. Fault-tolerant circuit constructions prevent individual faults from spreading uncontrollably. Resource estimates must therefore include encoded data, syndrome measurements, auxiliary qubits, routing, and the production of states needed for operations that are costly in the chosen code.

Logical and physical counts can differ by orders of magnitude. Craig Gidney and Martin Ekerå’s 2021 study estimated that a 2,048-bit RSA integer could be factored in about eight hours using approximately twenty million noisy physical qubits under its specified architecture and error assumptions. This was a conditional engineering estimate, not an experimental achievement or a fixed minimum. Different error rates, connectivity, code choices, and arithmetic designs produce different resource requirements.

Small demonstrations have tested parts of the algorithm on several physical platforms. In 2001, Lieven Vandersypen and colleagues reported factoring 15 using a seven-spin nuclear-magnetic-resonance system. Subsequent work used photonic, ion-trap, and superconducting approaches. Such experiments can demonstrate state preparation, controlled arithmetic, Fourier sampling, and classical reconstruction, but the interpretation depends strongly on the circuit actually implemented.

A crucial distinction is between a general modular-exponentiation circuit and a circuit compiled for a particular small instance. Compilation can exploit fixed constants to eliminate operations and workspace. That is legitimate circuit optimization, but extreme simplification may remove precisely the arithmetic whose scalable implementation is difficult. Some demonstrations rely on prior knowledge of the order or on specially chosen instances with unusually simple periodic structure.

Assessment therefore requires more than the reported integer being factored. Relevant questions include whether the circuit preserves coherence across a nontrivial order-finding computation, whether the arithmetic generalizes, whether the answer was encoded through instance-specific simplifications, and whether errors were actively corrected. Small factoring experiments establish component capabilities; they do not by themselves demonstrate the resources needed for cryptographically significant factoring.

Arithmetic design remains an important source of improvement. Low-qubit circuits can reuse registers through additional measurements and classical feed-forward, while wider circuits can expose more parallelism. These alternatives trade memory, gate count, depth, and control complexity rather than changing the underlying number-theoretic algorithm.

Consequences for cryptography and security standards

The clearest cryptographic target is the RSA cryptosystem. An RSA public key includes a modulus N=pqN=pq, normally formed from two large primes, and a public exponent ee. Factoring NN allows calculation of quantities such as

λ(N)=lcm⁡(p−1,q−1),\lambda(N)=\operatorname{lcm}(p-1,q-1),

from which the private exponent can be recovered as the appropriate modular inverse of ee. Efficient quantum factorization therefore defeats the mathematical trapdoor underlying conventional RSA encryption and signatures.

Quantum discrete-logarithm algorithms likewise threaten Diffie–Hellman key agreement, DSA, and elliptic-curve systems such as ECDH and ECDSA. Increasing their key lengths raises the cost of a quantum attack but does not restore the asymptotic security assumption on which they depend. Shor’s methods apply to the relevant problem families in polynomial time.

The consequences differ across cryptographic tasks. Compromising a key-establishment mechanism can expose encrypted communications when the necessary traffic and public protocol information have been recorded. Compromising a digital signature scheme can enable forgery while affected verification keys remain trusted. The significance of a recorded exchange also depends on the protocol: forward secrecy against later theft of long-term keys is not the same as resistance to a future algorithm that directly solves the public mathematical problem in the recorded exchange.

This creates a concern commonly described as “harvest now, decrypt later.” An adversary can retain encrypted material before possessing a sufficiently capable quantum computer. Whether that material becomes recoverable depends on its key establishment and encryption construction, as well as its continuing sensitivity. Symmetric encryption is not directly broken by Shor’s algorithm. AES and cryptographic hash functions face different quantum considerations, including the more limited generic speedup associated with Grover’s algorithm.

Post-quantum cryptography develops classical cryptographic systems based on mathematical problems not known to admit efficient quantum attacks. Major approaches include lattice-based key establishment and signatures, code-based encryption mechanisms, and hash-based signatures. Their security claims concern resistance to both classical and quantum adversaries; they do not require quantum communication or quantum hardware.

In August 2024, the United States National Institute of Standards and Technology published FIPS 203 for ML-KEM, FIPS 204 for ML-DSA, and FIPS 205 for SLH-DSA. These standards specify a module-lattice-based key-encapsulation mechanism, a module-lattice-based signature scheme, and a stateless hash-based signature scheme, respectively. They address functions previously served by quantum-vulnerable public-key systems through different mathematical foundations, rather than through a modification of Shor’s algorithm or a simple enlargement of RSA keys.