Skip to Main content Skip to Navigation
New interface
Conference papers

Relation collection for the Function Field Sieve

Jérémie Detrey 1 Pierrick Gaudry 1 Marion Videau 1 
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : In this paper, we focus on the relation collection step of the Function Field Sieve (FFS), which is to date the best known algorithm for computing discrete logarithms in small-characteristic finite fields of cryptographic sizes. Denoting such a finite field by GF(p^n), where p is much smaller than n, the main idea behind this step is to find polynomials of the form a(t)-b(t)x in GF(p)[t][x] which, when considered as principal ideals in carefully selected function fields, can be factored into products of low-degree prime ideals. Such polynomials are called ''relations'', and current record-sized discrete-logarithm computations require billions of them. Collecting relations is therefore a crucial and extremely expensive step in FFS, and a practical implementation thereof requires heavy use of cache-aware sieving algorithms, along with efficient polynomial arithmetic over GF(p)[t]. This paper presents the algorithmic and arithmetic techniques which were put together as part of a new implementation of FFS, aimed at medium- to record-sized computations, and planned for public release in the near future.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Pierrick Gaudry Connect in order to contact the contributor
Submitted on : Friday, January 18, 2013 - 2:01:58 PM
Last modification on : Wednesday, February 2, 2022 - 3:59:45 PM
Long-term archiving on: : Saturday, April 1, 2017 - 7:04:23 AM


Files produced by the author(s)




Jérémie Detrey, Pierrick Gaudry, Marion Videau. Relation collection for the Function Field Sieve. ARITH 21 - 21st IEEE International Symposium on Computer Arithmetic, Apr 2013, Austin, Texas, United States. pp.201-210, ⟨10.1109/ARITH.2013.28⟩. ⟨hal-00736123v2⟩



Record views


Files downloads