Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic
verfasst von : Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, Emmanuel Thomé
Erschienen in: Advances in Cryptology – EUROCRYPT 2014
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The difficulty of computing discrete logarithms in fields
$\mathbb{F}_{q^k}$
depends on the relative sizes of
k
and
q
. Until recently all the cases had a sub-exponential complexity of type
L
(1/3), similar to the factorization problem. In 2013, Joux designed a new algorithm with a complexity of
L
(1/4 +
ε
) in small characteristic. In the same spirit, we propose in this article another heuristic algorithm that provides a quasi-polynomial complexity when
q
is of size at most comparable with
k
. By quasi-polynomial, we mean a runtime of
n
O
(log
n
)
where
n
is the bit-size of the input. For larger values of
q
that stay below the limit
$L_{q^k}(1/3)$
, our algorithm loses its quasi-polynomial nature, but still surpasses the Function Field Sieve. Complexity results in this article rely on heuristics which have been checked experimentally.