Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

Better polynomials for GNFS


Authors: Shi Bai, Cyril Bouvier, Alexander Kruppa and Paul Zimmermann
Journal: Math. Comp. 85 (2016), 861-873
MSC (2010): Primary 11Y05, 11Y16
DOI: https://doi.org/10.1090/mcom3048
Published electronically: October 19, 2015
MathSciNet review: 3434885
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The general number field sieve (GNFS) is the most efficient algorithm known for factoring large integers. It consists of several stages, the first one being polynomial selection. The quality of the selected polynomials can be modelled in terms of size and root properties. We propose a new kind of polynomial for GNFS: with a new degree of freedom, we further improve the size property. We demonstrate the efficiency of our algorithm by exhibiting a better polynomial than the one used for the factorization of RSA-768 and a polynomial for RSA-1024 that outperforms the best published one.


References [Enhancements On Off] (What's this?)

  • [1] S. Bai, C. Bouvier, A. Filbois, P. Gaudry, L. Imbert, A. Kruppa, F. Morain, E. Thomé, and P. Zimmermann,
    CADO-NFS, an implementation of the number field sieve.
    Release 2.1, available from http://cado-nfs.gforge.inria.fr, 2014.
  • [2] Shi Bai, Richard P. Brent, and Emmanuel Thomé, Root optimization of polynomials in the number field sieve, Math. Comp. 84 (2015), no. 295, 2447-2457. MR 3356034, https://doi.org/10.1090/S0025-5718-2015-02926-3
  • [3] S. Bai, E. Thomé, and P. Zimmermann,
    Factorisation of RSA-704 with CADO-NFS,
    Report, 2012.
    http://eprint.iacr.org/2012/369.pdf.
  • [4] R. Barbulescu and A. Lachand,
    Some mathematical remarks on the polynomial selection in NFS.
    Report, 2014,
    http://arxiv.org/abs/1403.0184.
  • [5] H. Boender,
    Factoring large integers with the quadratic sieve,
    PhD thesis, Leiden University, 1997.
  • [6] J. P. Buhler, H. W. Lenstra Jr., and Carl Pomerance, Factoring integers with the number field sieve, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 50-94. MR 1321221, https://doi.org/10.1007/BFb0091539
  • [7] Andrew Granville, Smooth numbers: computational number theory and beyond, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 267-323. MR 2467549 (2010g:11214)
  • [8] Adolf Hildebrand and Gérald Tenenbaum, Integers without large prime factors, J. Théor. Nombres Bordeaux 5 (1993), no. 2, 411-484. MR 1265913 (95d:11116)
  • [9] Thorsten Kleinjung, On polynomial selection for the general number field sieve, Math. Comp. 75 (2006), no. 256, 2037-2047 (electronic). MR 2249770 (2007f:11140), https://doi.org/10.1090/S0025-5718-06-01870-9
  • [10] T. Kleinjung,
    Polynomial selection,
    in CADO workshop on integer factorization, INRIA Nancy, 2008,
    http://cado.gforge.inria.fr/workshop/slides/kleinjung.pdf.
  • [11] A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216 (96m:11116)
  • [12] 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 (2001d:11029), https://doi.org/10.1007/BFb0054858
  • [13] B. A. Murphy,
    Polynomial selection for the number field sieve integer factorisation algorithm,
    PhD thesis, The Australian National University, 1999.
  • [14] 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 (2000i:11189)
  • [15] J. Papadopoulos,
    Call for volunteers: RSA768 polynomial selection, 2011.
    http://www.mersenneforum.org/showthread.php?t=15540.
  • [16] J. Papadopoulos,
    Msieve v$ 1.48$, 2011,
    http://sourceforge.net/projects/msieve.
  • [17] J. M. Pollard, The lattice sieve, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 43-49. MR 1321220, https://doi.org/10.1007/BFb0091538
  • [18] Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Joppe W. Bos, Pierrick Gaudry, Alexander Kruppa, Peter L. Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, and Paul Zimmermann, Factorization of a 768-bit RSA modulus, Advances in cryptology--CRYPTO 2010, Lecture Notes in Comput. Sci., vol. 6223, Springer, Berlin, 2010, pp. 333-350. MR 2725602, https://doi.org/10.1007/978-3-642-14623-7_18
  • [19] Robert D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), no. 177, 329-339. MR 866119 (88c:11079), https://doi.org/10.2307/2007894
  • [20] Arjen Lenstra, Eran Tromer, Adi Shamir, Wil Kortsmit, Bruce Dodson, James Hughes, and Paul Leyland, Factoring estimates for a 1024-bit RSA modulus, Advances in cryptology--ASIACRYPT 2003, Lecture Notes in Comput. Sci., vol. 2894, Springer, Berlin, 2003, pp. 55-74. MR 2093252 (2005e:11163), https://doi.org/10.1007/978-3-540-40061-5_4
  • [21] T. Kleinjung, Cofactorisation strategies for the number field sieve and an estimate for the sieving step for factoring 1024 bit integers, http://www.hyperelliptic.org/tanja/SHARCS/talks06/thorsten.pdf, 2005.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y05, 11Y16

Retrieve articles in all journals with MSC (2010): 11Y05, 11Y16


Additional Information

Shi Bai
Affiliation: ENS de Lyon, Laboratoire LIP, (Université de Lyon, CNRS, ENSL, INRIA, UCBL), 69007 Lyon, France
Email: shih.bai@gmail.com

Cyril Bouvier
Affiliation: INRIA Nancy - Grand Est, 54600 Villers-lès-Nancy, France
Email: cyril.bouvier@inria.fr

Alexander Kruppa
Affiliation: INRIA Nancy - Grand Est, 54600 Villers-lès-Nancy, France
Email: alexander.kruppa@inria.fr

Paul Zimmermann
Affiliation: INRIA Nancy - Grand Est, 54600 Villers-lès-Nancy, France
Email: paul.zimmermann@inria.fr

DOI: https://doi.org/10.1090/mcom3048
Received by editor(s): June 18, 2013
Received by editor(s) in revised form: September 16, 2014
Published electronically: October 19, 2015
Additional Notes: The first author was supported in part by the ERC Starting Grant ERC-2013-StG-335086-LATTAC
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society