Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

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
DOI: https://doi.org/10.1090/mcom/3112
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
Email: razvan.barbulescu@imj-prg.fr

Armand Lachand
Affiliation: Institut Elie Cartan, Université de Lorraine, B.P. 70239, 54506 Vandoeuvre-lés-Nancy Cedex, France
Email: armand.lachand@univ-lorraine.fr

DOI: https://doi.org/10.1090/mcom/3112
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