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
Liste complète des métadonnées

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00736123
Contributor : Pierrick Gaudry <>
Submitted on : Friday, January 18, 2013 - 2:01:58 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:25 PM
Document(s) archivé(s) le : Saturday, April 1, 2017 - 7:04:23 AM

File

arith.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

639

Files downloads

291