Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1306.1161

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2 n)

Martin Roetteler, Rainer Steinwandt

Published Jun 5, 2013• 0 citations
arXivHTMLPDF

Abstract

Improving over an earlier construction by Kaye and Zalka, Maslov et al. describe an implementation of Shor's algorithm which can solve the discrete logarithm problem on binary elliptic curves in quadratic depth O(n^2). In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth O(log^2 n). As technical tools we introduce quantum circuits for GF(2^n) multiplication in depth O(log n) and for GF(2^n) inversion in depth O(log^2 n).

DOI
10.48550/arxiv.1306.1161

Related papers

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2n)

Martin Rötteler, Rainer Steinwandt

Improving over an earlier construction by Kaye and Zalka \cite{KaZa04}, in \cite{MMCP09b} Maslov et al. describe an implementation of Shor's algorithm, which can solve the discrete logarithm problem on ordinary binary elliptic curves in quadratic depth $\bigO(n^2)$. In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth $\bigO(\log^2n)$. As technical tools we introduce quantum circuits for ${\mathbb F}_{2^n}$-multiplication in depth $\bigO(\log n)$ and for ${\mathbb F}_{2^n}$-inversion in depth $\bigO(\log^2 n)$.

Quantum Information and Computation•Jul 1, 2014•9 citations

A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log2 n)

RöttelerMartin, SteinwandtRainer

Improving over an earlier construction by Kaye and Zalka [1], in [2] Maslov et al. describe an implementation of Shor's algorithm, which can solve the discrete logarithm problem on ordinary binary ...

Quantum Information and Computation•Jul 1, 2014•0 citations

Shor's discrete logarithm quantum algorithm for elliptic curves

John Proos, Christof Zalka

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''.

arXiv:quant-ph/0301141•Quantum Information and Computation•Jul 1, 2003•340 citations

An O(m^2)-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2^m)

D. Maslov, J. Mathew, D. Cheung +1 more

We consider a quantum polynomial-time algorithm which solves the discrete logarithm problem for points on elliptic curves over $GF(2^m)$. We improve over earlier algorithms by constructing an efficient circuit for multiplying elements of binary finite fields and by representing elliptic curve points using a technique based on projective coordinates. The depth of our proposed implementation, executable in the Linear Nearest Neighbor (LNN) architecture, is $O(m^2)$, which is an improvement over the previous bound of $O(m^3)$ derived assuming no architectural restrictions.

Quantum Information and Computation•Jul 1, 2009•18 citations

An O(m 2 )-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2 m ) a

Dmitri Maslov, Jimson Mathew, Donny Cheung +1 more

We consider a quantum polynomial-time algorithm which solves the discrete logarithm problem for points on elliptic curves over GF(2m). We improve over earlier algorithms by constructing an efficient circuit for multiplying elements of binary finite fields and by representing elliptic curve points using a technique based on projective coordinates. The depth of our proposed implementation, executable in the Linear Nearest Neighbor (LNN) architecture, is O(m2), which is an improvement over the previous bound of O(m3) derived assuming no architectural restrictions.

Quantum Information and Computation•Jul 1, 2009•19 citations

Efficient quantum circuits for binary elliptic curve arithmetic: reducing T-gate complexity

Brittanney Amento, Rainer Steinwandt, Martin Roetteler

Elliptic curves over finite fields GF(2^n) play a prominent role in modern cryptography. Published quantum algorithms dealing with such curves build on a short Weierstrass form in combination with affine or projective coordinates. In this paper we show that changing the curve representation allows a substantial reduction in the number of T-gates needed to implement the curve arithmetic. As a tool, we present a quantum circuit for computing multiplicative inverses in GF(2^n) in depth O(n log n) using a polynomial basis representation, which may be of independent interest.

arXiv:1209.6348•Sep 27, 2012•2 citations
Improving over an earlier construction by Kaye and Zalka, Maslov et al. describe an implementation of Shor's algorithm which can solve the discrete logarithm problem on binary elliptic curves in quadratic depth O(n^2). In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth O(log^2 n). As technical tools we introduce quantum circuits for GF(2^n) multiplication in depth O(log n) and for GF(2^n) inversion in depth O(log^2 n).
Improving over an earlier construction by Kaye and Zalka \cite{KaZa04}, in \cite{MMCP09b} Maslov et al. describe an implementation of Shor's algorithm, which can solve the discrete logarithm problem on ordinary binary elliptic curves in quadratic depth $\bigO(n^2)$. In this paper we show that discrete logarithms on such curves can be found with a quantum circuit of depth $\bigO(\log^2n)$. As technical tools we introduce quantum circuits for F2n{\mathbb F}_{2^n}F2n​-multiplication in depth $\bigO(\log n)$ and for F2n{\mathbb F}_{2^n}F2n​-inversion in depth $\bigO(\log^2 n)$.
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''.
We consider a quantum polynomial-time algorithm which solves the discrete logarithm problem for points on elliptic curves over GF(2m)GF(2^m)GF(2m). We improve over earlier algorithms by constructing an efficient circuit for multiplying elements of binary finite fields and by representing elliptic curve points using a technique based on projective coordinates. The depth of our proposed implementation, executable in the Linear Nearest Neighbor (LNN) architecture, is O(m2)O(m^2)O(m2), which is an improvement over the previous bound of O(m3)O(m^3)O(m3) derived assuming no architectural restrictions.
We consider a quantum polynomial-time algorithm which solves the discrete logarithm problem for points on elliptic curves over GF(2m). We improve over earlier algorithms by constructing an efficient circuit for multiplying elements of binary finite fields and by representing elliptic curve points using a technique based on projective coordinates. The depth of our proposed implementation, executable in the Linear Nearest Neighbor (LNN) architecture, is O(m2), which is an improvement over the previous bound of O(m3) derived assuming no architectural restrictions.
Elliptic curves over finite fields GF(2^n) play a prominent role in modern cryptography. Published quantum algorithms dealing with such curves build on a short Weierstrass form in combination with affine or projective coordinates. In this paper we show that changing the curve representation allows a substantial reduction in the number of T-gates needed to implement the curve arithmetic. As a tool, we present a quantum circuit for computing multiplicative inverses in GF(2^n) in depth O(n log n) using a polynomial basis representation, which may be of independent interest.