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 Free Access

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. H. W. Lenstra Jr., The number field sieve: an annotated bibliography, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 1–3. MR 1321217,
  • 4. Brian Murphy and Richard P. Brent, On quadratic polynomials for the number field sieve, Computing theory ’98 (Perth), Aust. Comput. Sci. Commun., vol. 20, Springer, Singapore, 1998, pp. 199–213. MR 1723947
  • 5. Brian Murphy, Modelling the yield of number field sieve polynomials, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 137–150. MR 1726067,
  • 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.