FFS Factory: Adapting Coppersmith's "Factorization Factory" to the Function Field Sieve

Jérémie Detrey 1, *
* Auteur correspondant
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : In 1993, Coppersmith introduced the "factorization factory" approach as a means to speed up the Number Field Sieve algorithm (NFS) when factoring batches of integers of similar size: at the expense of a large precomputation whose cost is amortized when considering sufficiently many integers to factor, the complexity of each individual factorization can then be lowered. We suggest here to extend this idea to the computation of discrete logarithms in finite fields of small characteristic using the Function Field Sieve (FFS), thus referring to this approach as the "FFS factory". In this paper, the benefits of the proposed technique are established thanks to both a theoretical complexity analysis along with a practical experiment in which we solved the discrete logarithm problem in fifty different binary fields of sizes ranging from 601 to 699 bits.
Type de document :
Pré-publication, Document de travail
2014
Liste complète des métadonnées


https://hal.inria.fr/hal-01002419
Contributeur : Jérémie Detrey <>
Soumis le : vendredi 6 juin 2014 - 10:21:44
Dernière modification le : jeudi 22 septembre 2016 - 14:31:11
Document(s) archivé(s) le : samedi 6 septembre 2014 - 11:32:13

Fichier

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

Identifiants

  • HAL Id : hal-01002419, version 1

Collections

Citation

Jérémie Detrey. FFS Factory: Adapting Coppersmith's "Factorization Factory" to the Function Field Sieve. 2014. <hal-01002419>

Partager

Métriques

Consultations de
la notice

269

Téléchargements du document

153