Shor's discrete logarithm quantum algorithm for elliptic curves
| dc.creator | Proos, John | |
| dc.creator | Zalka, Christof | |
| dc.date | 2003-01-25 | |
| dc.date | 2004-01-22 | |
| dc.date.accessioned | 2026-07-07T06:05:58Z | |
| dc.date.available | 2026-07-07T06:05:58Z | |
| dc.description | 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''. | |
| dc.description | 34 pages Latex, essentially published version, but not using Journal style file | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0301141 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0301141 | |
| dc.identifier | QIC 3 (No. 4) (2003) pp.317-344 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/90819 | |
| dc.subject | Quantum Physics | |
| dc.title | Shor's discrete logarithm quantum algorithm for elliptic curves | |
| dc.type | text |