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

## 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
- MR Author ID: 1075898
- 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
- MR Author ID: 273776
- Email: paul.zimmermann@inria.fr
- 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
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp.
**85**(2016), 861-873 - MSC (2010): Primary 11Y05, 11Y16
- DOI: https://doi.org/10.1090/mcom3048
- MathSciNet review: 3434885