A Rigorous Time Bound for Factoring Integers

Abstract

In this paper a probabilistic algorithm is exhibited that factors any positive integer into prime factors in expected time at most <!-- MATH ${L_n}[\tfrac{1}{2},1 + o(1)]$ --> for <!-- MATH $n \to \infty$ --> , where <!-- MATH ${L_x}[a,b] = {\text{exp}}(b{(\log x)^a}{({\text{log}}\log x)^{1 - a}})$ --> . Many practical factoring algorithms, including the quadratic sieve and the elliptic curve method, are conjectured to have an expected running time that satisfies the same bound, but this is the first algorithm for which the bound can be rigorously proved. Nevertheless, this does not close the gap between rigorously established time bounds and merely conjectural ones for factoring algorithms. This is due to the advent of a new factoring algorithm, the number field sieve, which is conjectured to factor any positive integer in time <!-- MATH ${L_n}[\tfrac{1}{3},O(1)]$ --> .