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 metadatas

https://hal.inria.fr/hal-00798386
Contributor : Razvan Barbulescu <>
Submitted on : Friday, March 8, 2013 - 2:45:02 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:25 PM
Long-term archiving on : Sunday, June 9, 2013 - 8:20:07 AM

Files

article.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

Razvan Barbulescu. Selecting polynomials for the Function Field Sieve. Mathematics of Computation, American Mathematical Society, 2015, 84 (296), pp.2987-3012 ⟨http://www.ams.org/journals/mcom/2015-84-296/S0025-5718-2015-02940-8/⟩. ⟨hal-00798386⟩

Share

Metrics

Record views

542

Files downloads

419