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.
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
Bibliographic Information
Thorsten Kleinjung
Affiliation: Department of Mathematics, University of Bonn, Beringstrasse 1, 53115 Bonn, Germany