dorsal/arxiv
View SchemaShor's discrete logarithm quantum algorithm for elliptic curves
| Authors | John Proos, Christof Zalka |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0301141 |
| URL | https://arxiv.org/abs/quant-ph/0301141 |
| Journal | QIC 3 (No. 4) (2003) pp.317-344 |
Abstract
We show in some detail how to implement Shor's efficient quantum algorithm for discrete logarithms for the particular case of elliptic curve groups. It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. 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. In this paper we only consider elliptic curves over GF($p$) and not yet the equally important ones over GF($2^n$) or other finite fields. The main technical difficulty is to implement Euclid's gcd algorithm to compute multiplicative inverses modulo $p$. As the runtime of Euclid's algorithm depends on the input, one difficulty encountered is the ``quantum halting problem''.
{
"annotation_id": "05edb7e2-3b6d-47f6-84ef-db6a499e7b02",
"date_created": "2026-03-02T18:01:55.586000Z",
"date_modified": "2026-03-02T18:01:55.586000Z",
"file_hash": "31414deddb3946c8f9369d27996d47e08db718d50bca322a3425fc2bb1bc9b52",
"private": false,
"record": {
"abstract": "We show in some detail how to implement Shor\u0027s efficient quantum algorithm\nfor discrete logarithms for the particular case of elliptic curve groups. It\nturns out that for this problem a smaller quantum computer can solve problems\nfurther beyond current computing than for integer factorisation. A 160 bit\nelliptic curve cryptographic key could be broken on a quantum computer using\naround 1000 qubits while factoring the security-wise equivalent 1024 bit RSA\nmodulus would require about 2000 qubits. In this paper we only consider\nelliptic curves over GF($p$) and not yet the equally important ones over\nGF($2^n$) or other finite fields. The main technical difficulty is to implement\nEuclid\u0027s gcd algorithm to compute multiplicative inverses modulo $p$. As the\nruntime of Euclid\u0027s algorithm depends on the input, one difficulty encountered\nis the ``quantum halting problem\u0027\u0027.",
"arxiv_id": "quant-ph/0301141",
"authors": [
"John Proos",
"Christof Zalka"
],
"categories": [
"quant-ph"
],
"journal_ref": "QIC 3 (No. 4) (2003) pp.317-344",
"title": "Shor\u0027s discrete logarithm quantum algorithm for elliptic curves",
"url": "https://arxiv.org/abs/quant-ph/0301141"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "fb7d2759-af7b-49ba-9f55-01fdc83db037",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}