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).
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 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.
Comments
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