On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography

摘要

We consider a quantum polynomial-time algorithm whichrnsolves the discrete logarithm problem for points on elliptic curves overrnGF(2~m). We improve over earlier algorithms by constructing an efficientrncircuit for multiplying elements of binary finite fields and by representingrnelliptic curve points using a technique based on projective coordinates.rnThe depth of our proposed implementation is O(m~2), which is an im-rnprovement over the previous bound of O(m~3 ).