Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

Selecting polynomials for the Function Field Sieve


Author: Razvan Barbulescu
Journal: Math. Comp. 84 (2015), 2987-3012
MSC (2010): Primary 12Y05; Secondary 12F15
DOI: https://doi.org/10.1090/S0025-5718-2015-02940-8
Published electronically: March 20, 2015
MathSciNet review: 3378859
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The Function Field Sieve algorithm is dedicated to computing discrete logarithms in a finite field $ \mathbb{F}_{q^n}$, where $ q$ is a small prime power. The scope of this article is to select good polynomials for this algorithm by defining and measuring the size property and the so-called root and cancellation properties. In particular we present an algorithm for rapidly testing a large set of polynomials. Our study also explains the behaviour of inseparable polynomials, in particular we give an easy way to see that the algorithm encompass the Coppersmith algorithm as a particular case.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 12Y05, 12F15

Retrieve articles in all journals with MSC (2010): 12Y05, 12F15


Additional Information

Razvan Barbulescu
Affiliation: Université de Lorraine, CNRS, INRIA, France
Email: razvan.barbulescu@inria.fr

DOI: https://doi.org/10.1090/S0025-5718-2015-02940-8
Received by editor(s): March 8, 2013
Received by editor(s) in revised form: October 18, 2013, and February 12, 2014
Published electronically: March 20, 2015
Article copyright: © Copyright 2015 American Mathematical Society