Algorithms · Hidden-period / factoring
Resource counts for elliptic-curve discrete logarithms
Carry Shor's discrete-logarithm algorithm through concretely for the group of points on an elliptic curve over GF(p), and count the qubits and operations it needs, so that the cost of attacking elliptic-curve cryptography can be compared with the cost of attacking RSA at an equivalent classical security level.
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)Various
- Primary source on the speedupStated by the primary source: "The classical complexity of this problem seems to depend strongly on the underlying group… for discrete logarithms over elliptic curves, nothing better than "generic" algorithms are known… e.g. the Pollard ρ algorithm [3], have truly exponential complexity."
- Reported costAbout 6n **logical** qubits and order n³ operations for an n-bit prime field, given as roughly 360n³ n-bit additions against about 4kn³ for factoring. Concretely the paper's table pairs a 160-bit elliptic-curve key at around 1000 logical qubits on a machine the authors twice call perfect and noise-free, with the security-equivalent 1024-bit RSA modulus at about 2000, and it gives the same pairing at 512, 2048, 3072 and 15360-bit RSA against 110, 224, 256 and 512-bit curves.
- Papers1
Carry Shor's discrete-logarithm algorithm through concretely for the group of points on an elliptic curve over GF(p), and count the qubits and operations it needs, so that the cost of attacking elliptic-curve cryptography can be compared with the cost of attacking RSA at an equivalent classical security level. The algorithm is Shor's two-dimensional hidden-subgroup construction: build the superposition over |x, y, xP + yQ⟩ using double-and-add point arithmetic on the curve, then apply a two-dimensional quantum Fourier transform and read the discrete logarithm off the dual lattice. The work is in the arithmetic. Each group operation decomposes into modular divisions and multiplications, and each division needs a reversible extended Euclidean algorithm — whose classical running time depends on its input, which is the obstacle the authors call the quantum halting problem. Their contribution is a piecewise-reversible implementation that lets different branches of the superposition desynchronize and move through the algorithm's five basic operations at their own pace instead of in lockstep, taking that subroutine from cubic to quadratic. Sharing registers between intermediate values then brings the qubit count down further.
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 →
The algorithm is Shor's two-dimensional hidden-subgroup construction: build the superposition over |x, y, xP + yQ⟩ using double-and-add point arithmetic on the curve, then apply a two-dimensional quantum Fourier transform and read the discrete logarithm off the dual lattice. The work is in the arithmetic. Each group operation decomposes into modular divisions and multiplications, and each division needs a reversible extended Euclidean algorithm — whose classical running time depends on its input, which is the obstacle the authors call the quantum halting problem. Their contribution is a piecewise-reversible implementation that lets different branches of the superposition desynchronize and move through the algorithm's five basic operations at their own pace instead of in lockstep, taking that subroutine from cubic to quadratic. Sharing registers between intermediate values then brings the qubit count down further. This record's speedup class, "Various", is a secondary source's classification of the algebraic and number theoretic algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "The classical complexity of this problem seems to depend strongly on the underlying group… for discrete logarithms over elliptic curves, nothing better than "generic" algorithms are known… e.g. the Pollard ρ algorithm [3], have truly exponential complexity.". Reported cost: About 6n logical qubits and order n³ operations for an n-bit prime field, given as roughly 360n³ n-bit additions against about 4kn³ for factoring. Concretely the paper's table pairs a 160-bit elliptic-curve key at around 1000 logical qubits on a machine the authors twice call perfect and noise-free, with the security-equivalent 1024-bit RSA modulus at about 2000, and it gives the same pairing at 512, 2048, 3072 and 15360-bit RSA against 110, 224, 256 and 512-bit curves..
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)
- Various
- Primary source on the speedup
- Stated by the primary source: "The classical complexity of this problem seems to depend strongly on the underlying group… for discrete logarithms over elliptic curves, nothing better than "generic" algorithms are known… e.g. the Pollard ρ algorithm [3], have truly exponential complexity."
- Reported cost
- About 6n **logical** qubits and order n³ operations for an n-bit prime field, given as roughly 360n³ n-bit additions against about 4kn³ for factoring. Concretely the paper's table pairs a 160-bit elliptic-curve key at around 1000 logical qubits on a machine the authors twice call perfect and noise-free, with the security-equivalent 1024-bit RSA modulus at about 2000, and it gives the same pairing at 512, 2048, 3072 and 15360-bit RSA against 110, 224, 256 and 512-bit curves.
- Speedup class
- Various (checked against the record's own primary paper, which states it)
- Complexity basis
- abstract of arXiv:quant-ph/0301141: "A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits."; section 6.2: "the DLP algorithm requires either f(n) = 7n + 4 log₂ n + ǫ or f′(n) = 5n + 8√n + 4 log₂ n + ǫ bits depending o[n] whether register sharing is used"; section 6.1: "the discrete logarithm algorithm is O(n³) … has a running time of approximately 360kn³ compared to only about 4kn³ for factoring."
- 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: Resource counts for elliptic-curve discrete logarithms
PROBLEM: Carry Shor's discrete-logarithm algorithm through concretely for the group of points on an elliptic curve over GF(p), and count the qubits and operations it needs, so that the cost of attacking elliptic-curve cryptography can be compared with the cost of attacking RSA at an equivalent classical security level.
IDEA: The algorithm is Shor's two-dimensional hidden-subgroup construction: build the superposition over |x, y, xP + yQ⟩ using double-and-add point arithmetic on the curve, then apply a two-dimensional quantum Fourier transform and read the discrete logarithm off the dual lattice. The work is in the arithmetic. Each group operation decomposes into modular divisions and multiplications, and each division needs a reversible extended Euclidean algorithm — whose classical running time depends on its input, which is the obstacle the authors call the quantum halting problem. Their contribution is a piecewise-reversible implementation that lets different branches of the superposition desynchronize and move through the algorithm's five basic operations at their own pace instead of in lockstep, taking that subroutine from cubic to quadratic. Sharing registers between intermediate values then brings the qubit count down further.
REPORTED COST: About 6n **logical** qubits and order n³ operations for an n-bit prime field, given as roughly 360n³ n-bit additions against about 4kn³ for factoring. Concretely the paper's table pairs a 160-bit elliptic-curve key at around 1000 logical qubits on a machine the authors twice call perfect and noise-free, with the security-equivalent 1024-bit RSA modulus at about 2000, and it gives the same pairing at 512, 2048, 3072 and 15360-bit RSA against 110, 224, 256 and 512-bit curves.
BASIS: abstract of arXiv:quant-ph/0301141: "A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits."; section 6.2: "the DLP algorithm requires either f(n) = 7n + 4 log₂ n + ǫ or f′(n) = 5n + 8√n + 4 log₂ n + ǫ bits depending o[n] whether register sharing is used"; section 6.1: "the discrete logarithm algorithm is O(n³) … has a running time of approximately 360kn³ compared to only about 4kn³ for factoring."
PRIMARY SOURCE: John Proos, Christof Zalka (2003), Shor's discrete logarithm quantum algorithm for elliptic curves — https://arxiv.org/abs/quant-ph/0301141
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
- Discrete logarithm on a quantum computer
Algorithms
- Shor period finding
Algorithms
- Quantum Fourier Transform
Algorithms
References
- Shor's discrete logarithm quantum algorithm for elliptic curves
John Proos, Christof Zalka · 2003
Primary source, and the source of this record's cost claim. The qubit and operation counts are in section 6, with the RSA-versus-curve table in section 6.3; the reversible extended Euclidean algorithm that the whole cost turns on is in section 5. Consult section 6.3 in particular before quoting any number from this record: it is where the authors say that error correction or fault tolerance is very probably necessary and that each logical qubit would then become several physical ones, which is the overhead none of the published figures include.