Algorithms · Hidden-period / factoring
Shor period finding
The cryptography-facing quantum algorithm record, with the assumptions that make its security relevance precise.
Strong empiricalUpdated
Open on the mapView frozen graph
A small worked example, computed in your browser. It is not a result from this record's papers.
Order-finding for 7 mod 15
3 counting qubits, 4 work qubits, finding the order of 7 modulo 15 (the order is 4: 7⁴ mod 15 = 1).
Step 1 of 5 · X
Probability of each outcome after this step
- 0001000100%
Prepares the work register as |0001⟩ = 1.
The whole state moves from 0000000 to 0001000 — one certain outcome before, one certain outcome after, no superposition either side.
Spreads the 3 counting qubits into an equal superposition of all 8 values.
Probability spreads from 1 outcome to 8. All 8 are equally likely.
Multiplies the work register by 7 mod 15, controlled by the first counting qubit: the k=0 controlled power of the order-finding unitary.
Probability moves: 4 outcomes appear that had none, 4 drop to zero, 8 carry probability now. Down: 0001001 12.5% → 0.0%, 0001011 12.5% → 0.0%. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
Multiplies the work register by 4 mod 15 (7 squared, mod 15), controlled by the second counting qubit: the k=1 controlled power. The k=2 power would multiply by 7⁴ mod 15 = 1, so it is the identity and is left out entirely.
Probability moves: 4 outcomes appear that had none, 4 drop to zero, 8 carry probability now. Up: 0100010 0.0% → 12.5%. Down: 0001010 12.5% → 0.0%, 0001110 12.5% → 0.0%.
An inverse QFT on the counting register reads the phase found by the controlled multiplications into a 3-bit estimate.
Probability moves: 12 outcomes appear that had none, 4 drop to zero, 16 carry probability now. Down: 0111001 12.5% → 0.0%, 0111101 12.5% → 0.0%.
Readout The counting register reads 000, 010, 100 or 110, each equally likely, corresponding to the four powers k = 0, 1, 2, 3 of the order r = 4; the work register ends entangled with the counting outcome, holding one of 1, 7, 4 or 13. Repeating this and applying the continued-fractions step of the full algorithm to a nonzero outcome recovers the order r = 4 exactly.
Open in Studio- Steps3
- Wires3
- Quantum coreOrder finding
- Classical postContinued fractions
- ReadinessFTQC required
- Papers1
A part this method uses, worked through
This page says Quantum phase estimation
— here is a concrete, runnable instance of it.
Phase estimation of P(3*pi/4)
3 counting qubits estimating the phase of P(3π/4), which is 2π·3/8 exactly: a phase 3-bit QPE can represent exactly.
Where it ends up
- 1011100%
The counting register reads 011 = 3 with probability 1: angle/(2π) = 3/8, recovered exactly.
One of its steps changes only phase: the outcome probabilities stay put while the state does not.
Open this part in StudioShor'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.
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 →
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.
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 →
- Quantum core
- Order finding
- Classical post
- Continued fractions
- Readiness
- FTQC required
- Threatened
- RSA / finite-field DLP
- Quantum output
- Period samples
- Deployment
- Migration planning
U_fon work registerQPEon work register, phase registerQFT†on phase register
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.
Nobody has reviewed this record for gaps yet.
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.
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.
Related entries
- Quantum phase estimation
Algorithms
- QFT resource screen
Algorithms
- Shor nine-qubit error-correction code
Operators
References
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Peter W. Shor · 1995
Original factoring and discrete-logarithm algorithm based on quantum period finding.