An $L (1/3)$ Discrete Logarithm Algorithm for Low Degree Curves

Andreas Enge 1, 2 Pierrick Gaudry 3 Emmanuel Thomé 3
1 LFANT - Lithe and fast algorithmic number theory
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
3 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : We present an algorithm for solving the discrete logarithm problem in Jacobians of families of plane curves whose degrees in $X$ and $Y$ are low with respect to their genera. The finite base fields $\FF_q$ are arbitrary, but their sizes should not grow too fast compared to the genus. For such families, the group structure and discrete logarithms can be computed in subexponential time of $L_{q^g}(1/3, O(1))$. The runtime bounds rely on heuristics similar to the ones used in the number field sieve or the function field sieve.
Type de document :
Article dans une revue
Journal of Cryptology, Springer Verlag, 2011, 24, pp.24-41. <10.1007/s00145-010-9057-y>
Liste complète des métadonnées

https://hal.inria.fr/inria-00383941
Contributeur : Andreas Enge <>
Soumis le : dimanche 20 décembre 2009 - 12:24:14
Dernière modification le : jeudi 22 septembre 2016 - 14:31:13
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 10:58:09

Fichiers

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

Identifiants

Collections

Citation

Andreas Enge, Pierrick Gaudry, Emmanuel Thomé. An $L (1/3)$ Discrete Logarithm Algorithm for Low Degree Curves. Journal of Cryptology, Springer Verlag, 2011, 24, pp.24-41. <10.1007/s00145-010-9057-y>. <inria-00383941v2>

Partager

Métriques

Consultations de
la notice

493

Téléchargements du document

321