Physics – Quantum Physics
Scientific paper
2003-01-25
QIC 3 (No. 4) (2003) pp.317-344
Physics
Quantum Physics
34 pages Latex, essentially published version, but not using Journal style file
Scientific paper
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''.
Proos John
Zalka Christof
No associations
LandOfFree
Shor's discrete logarithm quantum algorithm for elliptic curves does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Shor's discrete logarithm quantum algorithm for elliptic curves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shor's discrete logarithm quantum algorithm for elliptic curves will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-496973