Algorithms · Hidden-period / factoring
Discrete logarithm on a quantum computer
Given three n-bit numbers a, b and N with the promise that b = a^s mod N for some s, recover the exponent s.
Attested & literatureUpdated
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- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costPolynomial in the input size: the Zoo states that s can be found in poly(n) time for n-bit inputs while the fastest known classical algorithm takes time superpolynomial in n, and neither source quotes an exponent or constant. For the elliptic-curve variant over an n-bit prime field, Roetteler et al. estimate at most 9n + 2⌈log₂(n)⌉ + 10 **logical** qubits and a circuit of at most 448 n³ log₂(n) + 4090 n³ Toffoli gates. Their abstract states that qubit figure without the qualifier; section 5 is where they call it logical, and the paper states no error-correction assumption at all, so it supports no physical-qubit reading.
- Papers2
Given three n-bit numbers a, b and N with the promise that b = a^s mod N for some s, recover the exponent s. Shor's paper gives efficient randomized quantum algorithms for two problems believed hard classically, integer factoring and discrete logarithms, and both take a number of steps polynomial in the input size. The Zoo entry points the reader to the abelian hidden subgroup problem, and it states that by similar techniques quantum computers can solve the discrete logarithm problem on elliptic curves, thereby breaking elliptic-curve cryptography. Roetteler, Naehrig, Svore and Lauter make that elliptic-curve variant concrete by giving reversible circuits for modular addition, multiplication and inversion and for elliptic-curve point addition, then counting the qubits and Toffoli gates such a circuit needs.
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 paper gives efficient randomized quantum algorithms for two problems believed hard classically, integer factoring and discrete logarithms, and both take a number of steps polynomial in the input size. The Zoo entry points the reader to the abelian hidden subgroup problem, and it states that by similar techniques quantum computers can solve the discrete logarithm problem on elliptic curves, thereby breaking elliptic-curve cryptography. Roetteler, Naehrig, Svore and Lauter make that elliptic-curve variant concrete by giving reversible circuits for modular addition, multiplication and inversion and for elliptic-curve point addition, then counting the qubits and Toffoli gates such a circuit needs. This record's speedup class, "Superpolynomial", is a secondary source's classification of the algebraic and number theoretic algorithms it files this under — not a claim its primary paper makes. Not checked against the primary source yet. Reported cost: Polynomial in the input size: the Zoo states that s can be found in poly(n) time for n-bit inputs while the fastest known classical algorithm takes time superpolynomial in n, and neither source quotes an exponent or constant. For the elliptic-curve variant over an n-bit prime field, Roetteler et al. estimate at most 9n + 2⌈log₂(n)⌉ + 10 logical qubits and a circuit of at most 448 n³ log₂(n) + 4090 n³ Toffoli gates. Their abstract states that qubit figure without the qualifier; section 5 is where they call it logical, and the paper states no error-correction assumption at all, so it supports no physical-qubit reading..
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 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Superpolynomial
- Primary source on the speedup
- Not checked against the primary source yet
- Reported cost
- Polynomial in the input size: the Zoo states that s can be found in poly(n) time for n-bit inputs while the fastest known classical algorithm takes time superpolynomial in n, and neither source quotes an exponent or constant. For the elliptic-curve variant over an n-bit prime field, Roetteler et al. estimate at most 9n + 2⌈log₂(n)⌉ + 10 **logical** qubits and a circuit of at most 448 n³ log₂(n) + 4090 n³ Toffoli gates. Their abstract states that qubit figure without the qualifier; section 5 is where they call it logical, and the paper states no error-correction assumption at all, so it supports no physical-qubit reading.
- Speedup class
- Superpolynomial (not yet checked against the record's own primary paper)
- Complexity basis
- Zoo entry "Discrete-log": "this can be achieved on a quantum computer in poly( n ) time. The fastest known classical algorithm requires time superpolynomial in n"; abstract of arXiv:quant-ph/9508027: "These algorithms take a number of steps polynomial in the input size, e.g., the number of digits of the integer to be factored"; abstract of arXiv:1706.06752: "can be computed on a quantum computer with at most 9n + 2⌈log_2(n)⌉+10 qubits using a quantum circuit of at most 448 n^3 log_2(n) + 4090 n^3 Toffoli gates"; that abstract does not say whether those qubits are logical or physical, and section 5 of the same paper does: "the overall number of logical qubits for the controlled elliptic curve point addition in our simulation is 9n + 2⌈log_2(n)⌉ + 10", with section 1 calling the P-256 figure "2330 logical qubits". The words "physical qubit", "error correction" and "noiseless" appear nowhere in it.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Hidden-period / factoring with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Discrete logarithm on a quantum computer
PROBLEM: Given three n-bit numbers a, b and N with the promise that b = a^s mod N for some s, recover the exponent s.
IDEA: Shor's paper gives efficient randomized quantum algorithms for two problems believed hard classically, integer factoring and discrete logarithms, and both take a number of steps polynomial in the input size. The Zoo entry points the reader to the abelian hidden subgroup problem, and it states that by similar techniques quantum computers can solve the discrete logarithm problem on elliptic curves, thereby breaking elliptic-curve cryptography. Roetteler, Naehrig, Svore and Lauter make that elliptic-curve variant concrete by giving reversible circuits for modular addition, multiplication and inversion and for elliptic-curve point addition, then counting the qubits and Toffoli gates such a circuit needs.
REPORTED COST: Polynomial in the input size: the Zoo states that s can be found in poly(n) time for n-bit inputs while the fastest known classical algorithm takes time superpolynomial in n, and neither source quotes an exponent or constant. For the elliptic-curve variant over an n-bit prime field, Roetteler et al. estimate at most 9n + 2⌈log₂(n)⌉ + 10 **logical** qubits and a circuit of at most 448 n³ log₂(n) + 4090 n³ Toffoli gates. Their abstract states that qubit figure without the qualifier; section 5 is where they call it logical, and the paper states no error-correction assumption at all, so it supports no physical-qubit reading.
BASIS: Zoo entry "Discrete-log": "this can be achieved on a quantum computer in poly( n ) time. The fastest known classical algorithm requires time superpolynomial in n"; abstract of arXiv:quant-ph/9508027: "These algorithms take a number of steps polynomial in the input size, e.g., the number of digits of the integer to be factored"; abstract of arXiv:1706.06752: "can be computed on a quantum computer with at most 9n + 2⌈log_2(n)⌉+10 qubits using a quantum circuit of at most 448 n^3 log_2(n) + 4090 n^3 Toffoli gates"; that abstract does not say whether those qubits are logical or physical, and section 5 of the same paper does: "the overall number of logical qubits for the controlled elliptic curve point addition in our simulation is 9n + 2⌈log_2(n)⌉ + 10", with section 1 calling the P-256 figure "2330 logical qubits". The words "physical qubit", "error correction" and "noiseless" appear nowhere in it.
PRIMARY SOURCE: Peter W. Shor (1995), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer — https://arxiv.org/abs/quant-ph/9508027
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
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
- Shor period finding
Algorithms
- Quantum Fourier Transform
Algorithms
- Quantum phase estimation
Algorithms
- QFT resource screen
Algorithms
References
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Peter W. Shor · 1995
Primary reference for discrete logarithm on a quantum computer; the source of this record's cost claim.
- Quantum resource estimates for computing elliptic curve discrete logarithms
Martin Roetteler, Michael Naehrig, Krysta M. Svore, Kristin Lauter · 2017
Resource-estimate companion for the elliptic-curve case. The authors give circuit implementations for reversible modular arithmetic and elliptic-curve point addition, and report qubit and Toffoli-gate counts for an n-bit prime field. The paper states that these estimates are derived from a simulation of a Toffoli gate network for controlled elliptic curve point addition, implemented within the software tool suite LIQUi|⟩, and that the authors were able to simulate those networks classically for the NIST standard curves P-192, P-224, P-256, P-384 and P-521. It also reports that the results indicate a lower qubit requirement for tackling elliptic curves than for attacking RSA, for current parameters at comparable classical security levels, which the authors suggest makes ECC the easier target.