Paper 2013/582

The Special Number Field Sieve in $\F _{p^{n}}$, Application to Pairing-Friendly Constructions

Antoine Joux and Cécile Pierrot

Abstract

In this paper, we study the discrete logarithm problem in finite fields related to pairing-based curves. We start with a precise analysis of the state-of-the-art algorithms for computing discrete logarithms that are suitable for finite fields related to pairing-friendly constructions. To improve upon these algorithms, we extend the Special Number Field Sieve to compute discrete logarithms in $\F_{p^{n}}$, where $p$ has an adequate sparse representation. Our improved algorithm works for the whole range of applicability of the Number Field Sieve.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Discrete logarithmsSNFSpairing-based
Contact author(s)
Antoine Joux @ m4x org
History
2013-09-14: received
Short URL
https://ia.cr/2013/582
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/582,
      author = {Antoine Joux and Cécile Pierrot},
      title = {The Special Number Field Sieve in $\F _{p^{n}}$, Application to Pairing-Friendly Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2013/582},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/582}},
      url = {https://eprint.iacr.org/2013/582}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.