Root optimization of polynomials in the number field sieve

Bai, Shi; Brent, Richard; Thomé, Emmanuel

doi:10.1090/S0025-5718-2015-02926-3

Root optimization of polynomials in the number field sieve
HTML articles powered by AMS MathViewer

by Shi Bai, Richard P. Brent and Emmanuel Thomé PDF

Math. Comp. 84 (2015), 2447-2457 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 chosen polynomials in polynomial selection can be modelled in terms of size and root properties. In this paper, we describe some algorithms for selecting polynomials with very good root properties.

References

Kazumaro Aoki and Hiroki Ueda, Sieving using bucket sort, Advances in cryptology—ASIACRYPT 2004, Lecture Notes in Comput. Sci., vol. 3329, Springer, Berlin, 2004, pp. 92–102. MR 2150089, DOI 10.1007/978-3-540-30539-2_{8}
Eric Bach and René Peralta, Asymptotic semismoothness probabilities, Math. Comp. 65 (1996), no. 216, 1701–1715. MR 1370848, DOI 10.1090/S0025-5718-96-00775-2
S. Bai, C. Bouvier, A. Filbois, P. Gaudry, L. Imbert, A. Kruppa, F. Morain, E. Thomé, P. Zimmermann, CADO-NFS, an implementation of the number field sieve algorithm. Release 2.0, available from http://cado-nfs.gforge.inria.fr, 2013.
S. Bai, E. Thomé, P. Zimmermann, Factorisation of RSA-704 with CADO-NFS. Report, 2012. http://eprint.iacr.org/2012/369.pdf.
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
Willemien Ekkelkamp, Predicting the sieving effort for the number field sieve, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 167–179. MR 2467845, DOI 10.1007/978-3-540-79456-1_{1}1
Jason E. Gower, Rotations and translations of number field sieve polynomials, Advances in cryptology—ASIACRYPT 2003, Lecture Notes in Comput. Sci., vol. 2894, Springer, Berlin, 2003, pp. 302–310. MR 2093587, DOI 10.1007/978-3-540-40061-5_{1}8
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.
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
A. K. Lenstra and H. W. Lenstra, Jr., editors, The Development of the Number Field Sieve, volume 1554, Lecture Notes in Mathematics, Springer, 1993.
Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-5
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. 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
Carl Pomerance and Samuel S. Wagstaff Jr., Implementation of the continued fraction integer factoring algorithm, Congr. Numer. 37 (1983), 99–118. MR 703581
C. Stahlke and T. Kleinjung, Ideas for Finding Better Polynomials to Use in GNFS. In Workshop on Factoring Large Numbers, Discrete Logarithms and Cryptanalytical Hardware, Institut für Experimentelle Mathematik, Universität Duisburg-Essen, 2008.