A QUANTUM CIRCUIT TO FIND DISCRETE LOGARITHMS ON ORDINARY BINARY ELLIPTIC CURVES IN DEPTH O(log~2n)

摘要

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 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~2n). As technical tools we introduce quantum circuits for F_(2~n)-multiplication in depth O(logn) and for F2~n-inversion in depth O(log~2n).