Asymptotically Fast Factorization of Integers

Abstract

The paper describes a "probabilistic algorithm" for finding a factor of any large composite integer n (the required input is the integer n together with an auxiliary sequence of random numbers). It is proved that the expected number of operations which will be required is $O(\exp \{ \beta {(\ln n\ln \ln n)^{1/2}}\} )$ for some constant $\beta > 0$. Asymptotically, this algorithm is much faster than any previously analyzed algorithm for factoring integers; earlier algorithms have all required $O({n^\alpha })$ operations where $\alpha > 1/5$.