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.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
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 →
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
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..
Implementation
Unsupported
elliptic-curve-discrete-log-resources.txt
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.
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.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Shor's discrete logarithm quantum algorithm for elliptic curves2003 · John Proos, Christof Zalka
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.