Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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.
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
  • 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