Factorization of integers (Q1569723)

The author provides a very readable survey of methods for factoring integers and primality testing. The tests include several probable prime tests, J. L. Selfridge's converse to Fermat's little theorem and the Goldwasser-Kilian elliptic curve primality test. The factorization algorithms described are trial division, J. M. Pollard's \(\rho\) and \(p-1\) algorithms, the elliptic curve method of H. W. Lenstra jun., Fermat's difference of squares method, the continued fraction algorithm, the quadratic sieve and the number field sieve. In the last section she discusses factoring integers on a quantum computer.