On quadratic polynomials for the number field sieve

178. B. A. Murphy and R. P. Brent, On quadratic polynomials for the number field sieve, Proc. Fourth Australasian Theory Symposium (CATS'98, Perth, Feb. 1998), special issue of Australian Computer Science Communications 20, 3 (1998), 199-213. MR 2000i:11189. Longer version available as Report TR-CS-97-17, CSL, ANU, August 1997, 18 pp.

Paper: pdf (104K), ps (92K).

Report: pdf (179K), ps (143K).


The newest, and asymptotically the fastest known integer factorisation algorithm is the number field sieve. The area in which the number field sieve has the greatest capacity for improvement is polynomial selection. The best known polynomial selection method finds quadratic polynomials. In this paper we examine the smoothness properties of integer values taken by these polynomials. Given a quadratic NFS polynomial, let delta be its discriminant. We show that p need only appear in the factor base if the Legendre symbol (delta/p) = 1. Using this knowledge, we adapt a parameter alpha, developed for analysis of MPQS, to quadratic NFS polynomials. We estimate the yield of smooth values for these polynomials as a function of alpha, and conclude that practical changes in alpha might bring significant changes in the yield of smooth polynomial values, and polynomial values which are smooth but for the appearance of up to two large primes.


The method of polynomial selection described here was subsequently improved, as described in Murphy's thesis Polynomial selection for the number field sieve integer factorisation algorithm and used in the factorisation of the 512-bit number RSA155. See Brent [193] for more details.

Go to next publication

Return to Richard Brent's index page