Factoring integers is quite an old challenge. Thirty years ago, two researchers factored the mythic number F_{7} = 2^{27}+1. A few years later public-key cryptography was born, and with it the famous RSA algorithm. Even if the security of RSA is not equivalent to integer factorization, factoring the RSA key is the simplest way to decode everything, so a lot of people tried to factor. In 1990, F_{9} = 2^{29}+1, the ninth Fermat number was factored, with the help of hundreds of computers. In august 1999, it was the turn of the first ordinary 512-bit integer. What follows is a survey of thirty years of factorization, describing the different methods used and the technical problems met.
A lot of different methods exist to factor a number, starting from the linear sieve up to the algebraic sieve, including methods based on elliptic curves. Their complexity can be expressed in terms of the function
Method Complexity sieve p r (p)^{1/2} elliptic curve method L_{p}[1,1/2] quadratic sieve (QS) L_{N}[1/2,c] number field sieve (NFS) L_{N}[1/3,c]
Table 1: Complexity of factorization methods (N is the integer to be factored, p its smallest factor)
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.