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

M. Rötteler and R. Steinwandt

July 2014

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

Publication type | Article |

Published in | Quant. Inform. & Comp. |

Pages | 888-900 |

Volume | 14 |

Number | 9&10 |

Publisher | Rinton Press |

- A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
- Efficient quantum circuits for binary elliptic curve arithmetic: reducing T-gate complexity
- Quantum binary field inversion: improved circuit depth via choice of basis representation

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