Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

On polynomial selection for the general number field sieve

Author: Thorsten Kleinjung
Journal: Math. Comp. 75 (2006), 2037-2047
MSC (2000): Primary 11Y05, 11Y16
Posted: 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

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-, E-mail announcement, 2003.
```
http://www.crypto-world.com/announcements/rsa576.txt 
```
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
Email: thor@math.uni-bonn.de

DOI: http://dx.doi.org/10.1090/S0025-5718-06-01870-9
PII: S 0025-5718(06)01870-9
Keywords: Integer factorization, GNFS, polynomial selection
Received by editor(s): December 22, 2004
Received by editor(s) in revised form: June 22, 2005
Posted: June 28, 2006
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|