A general framework for subexponential discrete logarithm algorithms

Abstract : We describe a generic algorithm for computing discrete logarithms in groups of known order in which a smoothness concept is available. The running time of the algorithm can be proved without using any heuristics and leads to a subexponential complexity in particular for finite fields and class groups of number and function fields which were proposed for use in cryptography. In class groups, our algorithm is substantially faster than previously suggested ones. The subexponential complexity is obtained for cyclic groups in which a certain smoothness assumption is satisfied. We also show how to modify the algorithm for cyclic subgroups of arbitrary groups when the smoothness assumption can only be verified for the full group.
Type de document :
Article dans une revue
Acta Arithmetica, Instytut Matematyczny PAN, 2002, 102, pp.83-103. 〈10.4064/aa102-1-6〉
Liste complète des métadonnées

Littérature citée [36 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00512717
Contributeur : Pierrick Gaudry <>
Soumis le : mardi 31 août 2010 - 13:35:32
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44
Document(s) archivé(s) le : mercredi 1 décembre 2010 - 02:45:38

Fichier

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

Identifiants

Collections

Citation

Andreas Enge, Pierrick Gaudry. A general framework for subexponential discrete logarithm algorithms. Acta Arithmetica, Instytut Matematyczny PAN, 2002, 102, pp.83-103. 〈10.4064/aa102-1-6〉. 〈inria-00512717〉

Partager

Métriques

Consultations de la notice

379

Téléchargements de fichiers

207