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

Nebe, G.

Jahresber. Dtsch. Math.-Ver. 102, No. 1, 1-14 (2000).

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.

Reviewer: Olaf Ninnemann (Berlin)

MSC:

11Y05	Factorization
11Y11	Primality
11A51	Factorization; primality

Keywords:

algorithms; prime numbers