Skip to Main content Skip to Navigation
Journal articles

Selecting polynomials for the Function Field Sieve

Razvan Barbulescu 1 
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : The Function Field Sieve algorithm is dedicated to computing discrete logarithms in a finite field GF(q^n) , where q is small an 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Razvan Barbulescu Connect in order to contact the contributor
Submitted on : Friday, March 8, 2013 - 2:45:02 PM
Last modification on : Wednesday, February 2, 2022 - 3:59:44 PM
Long-term archiving on: : Sunday, June 9, 2013 - 8:20:07 AM


Files produced by the author(s)


  • HAL Id : hal-00798386, version 1
  • ARXIV : 1303.1998



Razvan Barbulescu. Selecting polynomials for the Function Field Sieve. Mathematics of Computation, American Mathematical Society, 2015, 84 (296), pp.2987-3012. ⟨hal-00798386⟩



Record views


Files downloads