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.
Type de document :
Communication dans un congrès
Alberto Nannarelli and Peter-Michael Seidel and Ping Tak Peter Tang. ARITH 21 - 21st IEEE International Symposium on Computer Arithmetic, Apr 2013, Austin, Texas, United States. IEEE, pp.201-210, 2013, ARITH 21. 〈10.1109/ARITH.2013.28〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00736123
Contributeur : Pierrick Gaudry <>
Soumis le : vendredi 18 janvier 2013 - 14:01:58
Dernière modification le : jeudi 22 septembre 2016 - 14:31:14
Document(s) archivé(s) le : samedi 1 avril 2017 - 07:04:23

Fichier

arith.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jérémie Detrey, Pierrick Gaudry, Marion Videau. Relation collection for the Function Field Sieve. Alberto Nannarelli and Peter-Michael Seidel and Ping Tak Peter Tang. ARITH 21 - 21st IEEE International Symposium on Computer Arithmetic, Apr 2013, Austin, Texas, United States. IEEE, pp.201-210, 2013, ARITH 21. 〈10.1109/ARITH.2013.28〉. 〈hal-00736123v2〉

Partager

Métriques

Consultations de la notice

565

Téléchargements de fichiers

251