|
On polynomial selection for the general number field sieve
Author(s):
Thorsten
Kleinjung.
Journal:
Math. Comp.
75
(2006),
2037-2047.
MSC (2000):
Primary 11Y05, 11Y16
Posted:
June 28, 2006
Retrieve article in:
PDF DVI PostScript
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:
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
Copyright of article:
Copyright
2006,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
Comments: webmaster@ams.org