Better polynomials for GNFS

Bai, Shi; Bouvier, Cyril; Kruppa, Alexander; Zimmermann, Paul

doi:10.1090/mcom3048

Better polynomials for GNFS
HTML articles powered by AMS MathViewer

by Shi Bai, Cyril Bouvier, Alexander Kruppa and Paul Zimmermann PDF

Math. Comp. 85 (2016), 861-873 Request permission

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

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.
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, DOI 10.1090/S0025-5718-2015-02926-3
S. Bai, E. Thomé, and P. Zimmermann, Factorisation of RSA-704 with CADO-NFS, Report, 2012. http://eprint.iacr.org/2012/369.pdf.
R. Barbulescu and A. Lachand, Some mathematical remarks on the polynomial selection in NFS. Report, 2014, http://arxiv.org/abs/1403.0184.
H. Boender, Factoring large integers with the quadratic sieve, PhD thesis, Leiden University, 1997.
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, DOI 10.1007/BFb0091539
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
Adolf Hildebrand and Gérald Tenenbaum, Integers without large prime factors, J. Théor. Nombres Bordeaux 5 (1993), no. 2, 411–484. MR 1265913
Thorsten Kleinjung, On polynomial selection for the general number field sieve, Math. Comp. 75 (2006), no. 256, 2037–2047. MR 2249770, DOI 10.1090/S0025-5718-06-01870-9
T. Kleinjung, Polynomial selection, in CADO workshop on integer factorization, INRIA Nancy, 2008, http://cado.gforge.inria.fr/workshop/slides/kleinjung.pdf.
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, DOI 10.1007/BFb0091534
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, PhD thesis, The Australian National University, 1999.
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
J. Papadopoulos, Call for volunteers: RSA768 polynomial selection, 2011. http://www.mersenneforum.org/showthread.php?t=15540.
J. Papadopoulos, Msieve v$1.48$, 2011, http://sourceforge.net/projects/msieve.
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, DOI 10.1007/BFb0091538
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, DOI 10.1007/978-3-642-14623-7_{1}8
Robert D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), no. 177, 329–339. MR 866119, DOI 10.1090/S0025-5718-1987-0866119-8
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, DOI 10.1007/978-3-540-40061-5_{4}
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.