Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On polynomial selection for the general number field sieve

Author: Thorsten Kleinjung
Journal: Math. Comp. 75 (2006), 2037-2047
MSC (2000): Primary 11Y05, 11Y16
Published electronically: June 28, 2006
MathSciNet review: 2249770
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The general number field sieve (GNFS) is the asymptotically fastest algorithm for factoring large integers. Its runtime depends on a good choice of a polynomial pair. In this article we present an improvement of the polynomial selection method of Montgomery and Murphy which has been used in recent GNFS records.

References [Enhancements On Off] (What's this?)

  • 1. S. Cavallar, W. M. Lioen, H. J. J. teRiele, B. Dodson, A. K. Lenstra, P. L. Montgomery, B. Murphy et al., Factorization of a 512-bit RSA modulus, Report MAS-R0007, CWI.
  • 2. J. Franke, T. Kleinjung et al., RSA-$ 576$, E-mail announcement, 2003. 
  • 3. A. K. Lenstra and H. W. Lenstra, Jr. (eds.), The Development of the Number Field Sieve, Lecture Notes in Math. 1554, Springer, 1993.MR 1321217
  • 4. B. A. Murphy and R. P. Brent, On Quadratic Polynomials for the Number Field Sieve, Computing Theory 98, ACSC 20(3) (1998), pp. 199-215.MR 1723947 (2000i:11189)
  • 5. B. A. Murphy, Modelling the Yield of Number Field Sieve Polynomials, Algorithmic Number Theory - ANTS III, LNCS 1443 (1998), pp. 137-147.MR 1726067 (2001d:11029)
  • 6. B. A. Murphy, Polynomial selection for the Number Field Sieve Integer Factorisation Algorithm, Ph.D. thesis, The Australian National University, 1999.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y05, 11Y16

Retrieve articles in all journals with MSC (2000): 11Y05, 11Y16

Additional Information

Thorsten Kleinjung
Affiliation: Department of Mathematics, University of Bonn, Beringstrasse 1, 53115 Bonn, Germany

Keywords: Integer factorization, GNFS, polynomial selection
Received by editor(s): December 22, 2004
Received by editor(s) in revised form: June 22, 2005
Published electronically: June 28, 2006
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society