Razvan Barbulescu. A comprehensive analysis of Regev's quantum algorithm

abstract: Shor's algorithm requires 2n+1 qubits and n M(n) gates to break RSA-n. It has been implemented on toy examples of n less than 10 but the problem is the number of gates, which is n^3 for small n. In 2023 Regev proposed an algorithm which uses sqrt(n) M(n) gates, which has been later extended to computing discrete logarithms in the multiplicative group. Unlike Shor, Regev doesn't apply directly to elliptic curves. In this work we explain a strategy to extend Regev to elliptic curves and make it work on several curves from the NIST list, including Bernstein's Curve25519. Using celebrated conjectures in Number Theory we conclude that the speed-up with respect to Shor goes to infinity with the size of the input. The heuristics in the initial variant of Regevs algorithm have been removed by Pilatte (2024) with the expense of a slight modification. We prove that the modification was needed because the initial variant fails to factor infinitely many RSA moduli.