Factorization of integers. (Faktorisieren ganzer Zahlen.) (German) Zbl 1159.11325

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.


11Y05 Factorization
11Y11 Primality
11A51 Factorization; primality