ANU Computer Science Technical Reports
TR-CS-97-17
Brian Murphy and Richard P. Brent.
On quadratic polynomials for the number field sieve.
August 1997.
[POSTSCRIPT (145396 bytes)]
Abstract: 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 (\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.
Technical Reports <Technical.Reports@cs.anu.edu.au>
Last modified: Mon Sep 1 11:49:13 EST 1997