On quadratic polynomials for the number field sieve

Date

Authors

Murphy, Brian
Brent, Richard P

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

The newest, and asymptotically the fastest known integer factorization 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. Using this knowledge, we adapt a parameter a, developed for analysis of MPQS, to quadratic NFS polynomials. We estimate the yield of smooth values for these polynomials as a function of a, and conclude that practical changes in a 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.

Description

Citation

Source

Book Title

Entity type

Access Statement

License Rights

DOI

Restricted until

Downloads