Some mathematical remarks on the polynomial selection in NFS

Barbulescu, Razvan; Lachand, Armand

doi:10.1090/mcom/3112

Some mathematical remarks on the polynomial selection in NFS
HTML articles powered by AMS MathViewer

by Razvan Barbulescu and Armand Lachand PDF

Math. Comp. 86 (2017), 397-418 Request permission

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

S. Bai, Polynomial selection for the number field sieve, Ph.D. thesis, Australian National University, 2011.
Razvan Barbulescu, Selecting polynomials for the function field sieve, Math. Comp. 84 (2015), no. 296, 2987–3012. MR 3378859, DOI 10.1090/S0025-5718-2015-02940-8
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, DOI 10.4171/CMH/264
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.
H. Boender, The number of relations in the quadratic sieve algorithm, Tech. report, Department of Numerical Mathematics, CWI, Amsterdam, 1996.
Duncan A. Buell, Binary quadratic forms, Springer-Verlag, New York, 1989. Classical theory and modern computations. MR 1012948, DOI 10.1007/978-1-4612-4542-1
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.
É. 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, DOI 10.1112/plms/s3-63.3.449
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, 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, DOI 10.1016/0022-314X(86)90013-2
Adolf Hildebrand and Gérald Tenenbaum, Integers without large prime factors, J. Théor. Nombres Bordeaux 5 (1993), no. 2, 411–484. MR 1265913
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, DOI 10.1112/plms/pdm029
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. MR 1954978, DOI 10.1090/S0025-5718-02-01482-5
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, DOI 10.1007/11818175_{1}9
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
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
Thorsten Kleinjung, Polynomial selection, 2008, CADO workshop on integer factorization. Slides available online at http://cado.gforge.inria.fr/workshop/slides/kleinjung.pdf.
A. Lachand, Fonctions arithmétiques et formes binaires irréductibles de degré $3$, https://hal.archives-ouvertes.fr/hal-01053649, 2014.
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, DOI 10.1093/qmath/hau029
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, DOI 10.1007/BFb0091537
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
B. A. Murphy, Polynomial selection for the number field sieve integer factorisation algorithm, Ph.D. thesis, Australian National University, 1999.
T. Nagell, Généralisation d’un théorème de Tchebycheff, J. Math. Pures Appl. (8) 4 (1921), no. 4, 343–356.
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.
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, DOI 10.1007/BFb0091536
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
Éric Saias, Sur le nombre des entiers sans grand facteur premier, J. Number Theory 32 (1989), no. 1, 78–99 (French). MR 1002116, DOI 10.1016/0022-314X(89)90099-1
Oliver Schirokauer, Discrete logarithms and local units, Philos. Trans. Roy. Soc. London Ser. A 345 (1993), no. 1676, 409–423. MR 1253502, DOI 10.1098/rsta.1993.0139
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
B. Winckler, Théorème de Chebotarev effectif, preprint available at http://hal.archives-ouvertes.fr/docs/00/90/74/10/PDF/chebotarev.pdf.