zbMATH — the first resource for mathematics

A multiple polynomial general number field sieve. (English) Zbl 0899.11060
Cohen, Henri (ed.), Algorithmic number theory. Second international symposium, ANTS-II, Talence, France, May 18-23, 1996. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1122, 99-114 (1996).
The primary contribution of this article is to describe how to employ two or more polynomials with the general number field sieve (GNFS). After giving a brief overview of the GNFS, the author explains how multiple polynomials are used. The choice of polynomials is given particular attention. She then gives a detailed description of the implementation and experiments performed using 2-4 polynomials. In the end, it was discovered that using two polynomials is optimal for line sieving (a special form of lattice sieving), but using four polynomials helped classical sieving considerably, giving speedup factors exceeding 1.8 over two polynomials. Yet line sieving was faster than classical sieving. The experiments involved factoring the 96-digit divisor of \(80^{61}-1\).
For the entire collection see [Zbl 0852.00023].

11Y16 Number-theoretic algorithms; complexity
11Y05 Factorization