Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer1995 · Peter W. Shor
Original factoring and discrete-logarithm algorithm based on quantum period finding.
arxiv.org/abs/quant-ph/9508027 ↗Strong empiricalAlgorithmsHidden-period / factoring
Shor period finding
The cryptography-facing quantum algorithm record, with the assumptions that make its security relevance precise.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Shor's algorithm reduces factoring and discrete logarithms to period finding. It is industry-relevant primarily as a migration and risk-planning reference today, not as a near-term production attack.
Circuit & simulation
work register
U_fQPE
phase register
QPEQFT†
classical post-processing
Period r50%
What this takes and returns
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Where this sits
This record is named by the layer graph at:
- Period finding in a finite cyclic group Method
Takes A circuit evaluating f on a superposition of inputs, the promise that f is periodic, the kind of object its period is (an integer in a finite cyclic group, an irrational real, a lattice of rank r), and — where the period is not an integer — the precision wanted. Returns The period: an exact integer where the group is finite, or an approximation to the requested precision together with the classical post-processing that turned the measured samples into it.
How it works
Shor's algorithm reduces factoring to finding the period of for a random coprime to : once is known, yields a nontrivial factor with good probability (when is even and ). The quantum step estimates via phase estimation: preparing a superposition over the exponent register, applying controlled modular exponentiation , and reading out with an inverse QFT gives a phase close to for random integer ; a classical continued-fraction expansion then recovers . This record documents that circuit motif — controlled- powers feeding an inverse QFT — and keeps the quantum (period-extraction) and classical (continued-fraction) halves visible as separate steps, consistent with its own status: a reviewable reference, not a resource-estimated fault-tolerant implementation, since a cryptographically relevant instance needs thousands of logical qubits and deep modular-arithmetic circuits.
Implementation
Native
shor_period_finding.py
from qiskit import QuantumCircuit
# Reference skeleton: modular multiplication is problem-specific.
qc = QuantumCircuit(6)
qc.h(range(3))
# controlled-U^(2^j) blocks feed inverse QFT.
qc.barrier()
FINAL_CIRCUIT = qcThis is a conceptual skeleton, not a production factoring implementation or security benchmark.
Quantum vs classical
| Metric | Classical | Quantum |
|---|---|---|
| Time complexity | sub-exponential | polynomial in log N |
| Scaling (b = log₂N) | exp(Õ(b^⅓)) | Õ(b³) |
| Logical qubits (2048-bit) | — | ~few thousand |
| Impact | RSA / ECC assumed hard | breaks RSA / ECC |
Classical baseline
General number-field sieve for factoring and classical discrete-logarithm algorithms under the same security parameter.
Quantum claim
Polynomial-time asymptotic factoring and discrete logarithms in the fault-tolerant query/gate model.
How to compare
Compare logical qubits, T gates, error-correction overhead, runtime, and key sizes; never collapse a mathematical threat into a current hardware claim.
Declared gaps
Nobody has reviewed this record for gaps yet.