On polynomial selection for the general number field sieve
HTML articles powered by AMS MathViewer
- by Thorsten Kleinjung PDF
- Math. Comp. 75 (2006), 2037-2047 Request permission
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
- 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.
- J. Franke, T. Kleinjung et al., RSA-$576$, E-mail announcement, 2003. http://www.crypto-world.com/announcements/rsa576.txt
- 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, DOI 10.1007/BFb0091535
- 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
- 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, DOI 10.1007/BFb0054858
- B. A. Murphy, Polynomial selection for the Number Field Sieve Integer Factorisation Algorithm, Ph.D. thesis, The Australian National University, 1999.
Additional Information
- Thorsten Kleinjung
- Affiliation: Department of Mathematics, University of Bonn, Beringstrasse 1, 53115 Bonn, Germany
- MR Author ID: 704259
- Email: thor@math.uni-bonn.de
- Received by editor(s): December 22, 2004
- Received by editor(s) in revised form: June 22, 2005
- Published electronically: June 28, 2006
- © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 75 (2006), 2037-2047
- MSC (2000): Primary 11Y05, 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-06-01870-9
- MathSciNet review: 2249770