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?)

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