Paper 2014/419

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

Jérémie Detrey

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Discrete logarithmFunction field sieveCryptanalysis
Contact author(s)
Jeremie Detrey @ loria fr
History
2014-06-05: received
Short URL
https://ia.cr/2014/419
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/419,
      author = {Jérémie Detrey},
      title = {FFS Factory: Adapting Coppersmith's "Factorization Factory" to the Function Field Sieve},
      howpublished = {Cryptology ePrint Archive, Paper 2014/419},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/419}},
      url = {https://eprint.iacr.org/2014/419}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.