Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Selecting polynomials for the Function Field Sieve

Author: Razvan Barbulescu
Journal: Math. Comp. 84 (2015), 2987-3012
MSC (2010): Primary 12Y05; Secondary 12F15
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

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

American Mathematical Society