Quantum Computational Number Theory
Song Yuan Yan · 2012
This chapter gives an account of ef?cient algorithms for solving the three important infeasible problems in computational number theory, including the Integer Factorization Problem (IFP), the Discrete Logarithm Problems (DLP), and the Elliptic Curve Discrete Logarithm Problem (ECDLP). The quantum algorithms for order ?nding and factoring can be used, with some small modi?cations, to solve the Discrete Logarithm Problem (DLP) ef?ciently in polynomial time. Quantum factoring is reportedly in its very earliest stages and will not threaten the security of RSA at least at present, as the current quantum computer can only factor a number with just 2 digits, such as 15, which is essentially hopeless. The Elliptic Curve Method (ECM) factoring algorithm is very well suited to parallel implementation. The Number Field Sieve (NFS) factoring algorithm is also very well suited to parallel implementation.