Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Some mathematical remarks on the polynomial selection in NFS

Authors: Razvan Barbulescu and Armand Lachand
Journal: Math. Comp. 86 (2017), 397-418
MSC (2010): Primary 11E76, 11N25, 11N36; Secondary 11Y05, 11Y16
Published electronically: April 13, 2016
MathSciNet review: 3557804
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this work, we consider the proportion of friable (free of large prime factors) values of a binary form $ F(X_1,X_2)\in \mathbf {Z}[X_1,X_2]$. In the particular case of quadratic forms, we give an asymptotic equivalent for this proportion which depends on $ F$. This is related to Murphy's $ \alpha $ function, which is known in the cryptologic community, but which has not been studied before from a mathematical point of view. This has consequences on the first step, called polynomial selection, of the Number Field Sieve, the fastest algorithm of integer factorization.

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

  • [Bai11] S. Bai, Polynomial selection for the number field sieve, Ph.D. thesis, Australian National University, 2011.
  • [Bar15] Razvan Barbulescu, Selecting polynomials for the Function Field Sieve, Math. Comp. 84 (2015), no. 296, 2987-3012. MR 3378859,
  • [BBDT12] Antal Balog, Valentin Blomer, Cécile Dartyge, and Gérald Tenenbaum, Friable values of binary forms, Comment. Math. Helv. 87 (2012), no. 3, 639-667. MR 2980522,
  • [BGI14] C. Bouvier, P. Gaudry, L. Imbert, H. Jeljeli, and E. Thomas, Announcement to the number theory mailing list: Discrete logarithms in GF(p) -- 180 digits, 2014. Announcement available at the NMBRTHRY archives, item 004703.
  • [Boe96] H. Boender, The number of relations in the quadratic sieve algorithm, Tech. report, Department of Numerical Mathematics, CWI, Amsterdam, 1996.
  • [Bue89] Duncan A. Buell, Binary quadratic forms: Classical theory and modern computations, Springer-Verlag, New York, 1989. MR 1012948 (92b:11021)
  • [Ded78] R. Dedekind, Über den Zusammenhang zwischen der Theorie der Ideale und der höheren Kongruenzen, Abh. Kgl. Ges. Wiss. Göttingen 23 (1878), 1-23.
  • [FT91] É. Fouvry and G. Tenenbaum, Entiers sans grand facteur premier en progressions arithmetiques, Proc. London Math. Soc. (3) 63 (1991), no. 3, 449-494 (French). MR 1127146 (93c:11074),
  • [Gra08] 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)
  • [Hil86] Adolf Hildebrand, On the number of positive integers $ \leq x$ and free of prime factors $ >y$, J. Number Theory 22 (1986), no. 3, 289-307. MR 831874 (87d:11066),
  • [HT93] 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)
  • [HTW08] Guillaume Hanrot, Gérald Tenenbaum, and Jie Wu, Moyennes de certaines fonctions multiplicatives sur les entiers friables. II, Proc. Lond. Math. Soc. (3) 96 (2008), no. 1, 107-135 (French, with English summary). MR 2392317 (2009c:11147),
  • [JL03] Antoine Joux and Reynald Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method, Math. Comp. 72 (2003), no. 242, 953-967 (electronic). MR 1954978 (2003k:11192),
  • [JLSV06] Antoine Joux, Reynald Lercier, Nigel Smart, and Frederik Vercauteren, The number field sieve in the medium prime case, Advances in cryptology--CRYPTO 2006, Lecture Notes in Comput. Sci., vol. 4117, Springer, Berlin, 2006, pp. 326-344. MR 2422170 (2010a:11237),
  • [KAF10] 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,
  • [Kle06] Thorsten Kleinjung, On polynomial selection for the general number field sieve, Math. Comp. 75 (2006), no. 256, 2037-2047 (electronic). MR 2249770 (2007f:11140),
  • [Kle08] Thorsten Kleinjung, Polynomial selection, 2008, CADO workshop on integer factorization. Slides available online at
  • [Lac14a] A. Lachand, Fonctions arithmétiques et formes binaires irréductibles de degré $ 3$,, 2014.
  • [Lac14b] Armand Lachand, Valeurs friables d'une forme quadratique et d'une forme linéaire, Q. J. Math. 66 (2015), no. 1, 225-244 (French, with English summary). MR 3356288,
  • [LL93] A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse, and J. M. Pollard, The number field sieve, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 11-42. MR 1321219,
  • [LO77] J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $ L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409-464. MR 0447191 (56 #5506)
  • [Mur99] B. A. Murphy, Polynomial selection for the number field sieve integer factorisation algorithm, Ph.D. thesis, Australian National University, 1999.
  • [Nag21] T. Nagell, Généralisation d'un théorème de Tchebycheff, J. Math. Pures Appl. (8) 4 (1921), no. 4, 343-356.
  • [Oes79] J. Oesterlé, Versions effectives du théorème de Chebotarev sous l'hypothèse de Riemann généralisée, Astérisque 61 (1979), 165-167.
  • [Pol93] J. M. Pollard, Factoring with cubic integers, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 4-10. MR 1321218,
  • [RS62] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-94. MR 0137689 (25 #1139)
  • [Sai89] Éric Saias, Sur le nombre des entiers sans grand facteur premier, J. Number Theory 32 (1989), no. 1, 78-99 (French). MR 1002116 (90f:11080),
  • [Sch93] Oliver Schirokauer, Discrete logarithms and local units, Philos. Trans. Roy. Soc. London Ser. A 345 (1993), no. 1676, 409-423. MR 1253502 (95c:11156),
  • [Ten90] Gérald Tenenbaum, Sur un problème d'Erdős et Alladi, Séminaire de Théorie des Nombres, Paris 1988-1989, Progr. Math., vol. 91, Birkhäuser Boston, Boston, MA, 1990, pp. 221-239 (French). MR 1104708 (92d:11098)
  • [Win] B. Winckler, Théorème de Chebotarev effectif, preprint available at

Similar Articles

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

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

Additional Information

Razvan Barbulescu
Affiliation: Université de Lorraine, 34 Cours Léopold, 54000 Nancy, France – and – CNRS, INRIA

Armand Lachand
Affiliation: Institut Elie Cartan, Université de Lorraine, B.P. 70239, 54506 Vandoeuvre-lés-Nancy Cedex, France

Received by editor(s): March 12, 2014
Received by editor(s) in revised form: May 27, 2014, August 9, 2014, September 8, 2014, February 13, 2015, and June 30, 2015
Published electronically: April 13, 2016
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society