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 requires
bits, apart from minor conventions at powers of two. A procedure taking time proportional to is therefore exponential in . Shor’s achievement was to give an algorithm whose running time is bounded by a polynomial in , 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 that is not a prime power. Repeated splitting and primality testing can then turn nontrivial divisors into a complete prime factorization.
Choose an integer randomly with , and compute its greatest common divisor with . If
a nontrivial factor has already been found. Otherwise is relatively prime to , and the task is to determine its multiplicative order modulo : the smallest positive integer satisfying
Equivalently, is the period of the function .
If is even, then
This identity can expose factors because a composite modulus can divide a product without dividing either factor separately. If , then the greatest common divisors
give nontrivial divisors. Minimality of the order rules out .
For example, take and . The successive residues are , so the order is . Hence
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 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 , usually chosen so that
The exponent register then contains approximately qubits, while a register capable of representing residues modulo needs approximately qubits. Additional workspace depends on the arithmetic circuit used.
Starting with the exponent register in , Hadamard gates create a uniform superposition:
The work register is initialized appropriately, and reversible modular exponentiation produces
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
The constants 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 binary positions, rather than one operation for every possible exponent.
These operations must be reversible. Multiplication by modulo permutes the residues when . 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 leaves the exponent register in a superposition proportional to
truncated at . The remaining exponents form an arithmetic progression with spacing . 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 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 basis states, one convention defines it by
An inverse-transform convention reverses the sign in the exponent but gives an equivalent period-finding procedure.
For a periodic progression , the amplitude at an output contains a geometric sum:
The overall phase contributed by does not affect measurement probabilities. The remaining terms reinforce one another when is close to an integer and largely cancel otherwise. Consequently, measured values tend to lie near
where is an integer between and .
If divides , the ideal peaks occur exactly at multiples of . 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 , not a binary encoding of itself. Choosing on the order of provides sufficient precision for rational reconstruction.
The same process can be understood through quantum phase estimation. Define modular multiplication by
on the appropriate residue subspace. On the orbit generated by , this operator has eigenvalues . With a suitable sign convention, its eigenvectors are Fourier superpositions of those orbit states. The state is an equal superposition of the eigenvectors, so phase estimation samples phases . Controlled powers are precisely the modular multiplications used in modular exponentiation.
For , an exact Fourier-transform circuit can be decomposed into 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 is converted into the rational number . With useful probability it closely approximates . A standard sufficient condition for recovering a reduced fraction by continued fractions is
If a fraction satisfies this bound, its reduced form occurs among the convergents of the continued-fraction expansion of .
For example, let and , whose order is six. Choosing , a useful measurement is , since
The continued-fraction convergents include , giving the candidate order . Verification confirms , and the factors follow from
A measurement need not reveal the full order. If the sampled numerator shares a divisor with , the fraction reduces to one with a smaller denominator. For , a phase corresponding to reduces to . Recovering the denominator three does not establish that the order is three: in this example, .
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 is sampled. The probability of that event is , where 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 . With schoolbook reversible arithmetic, modular exponentiation is commonly described as requiring 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 controlled modular multiplications, each costing roughly operations in a straightforward implementation. The Fourier transform adds approximately gates and therefore does not dominate that construction. Space can be kept linear in 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
where
This is subexponential in , 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 , the problem is to recover an integer from
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 , define
Since ,
The function is constant along translations by pairs , with arithmetic taken modulo . Its repeated values therefore identify cosets of a hidden subgroup of .
A quantum circuit prepares a superposition of exponent pairs, evaluates reversibly, and performs Fourier sampling. With the Fourier convention using phases , the outcomes satisfy
If is prime and , modular inversion yields
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 conceals the scalar , and the quantum circuit evaluates combinations such as . 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 , normally formed from two large primes, and a public exponent . Factoring allows calculation of quantities such as
from which the private exponent can be recovered as the appropriate modular inverse of . 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.