An extension of Kedlaya's algorithm to superelliptic curves

Abstract : We present an algorithm for counting points on superelliptic curves y^r=f(x) over a finite field F_q of small characteristic different from r. This is an extension of an algorithm for hyperelliptic curves due to Kedlaya. In this extension, the complexity, assuming r and the genus are fixed, is O(log^{3+epsilon}q) in time and space, just like for hyperelliptic curves. We give some numerical examples obtained with our first implementation, thus proving that cryptographic sizes are now reachable.
Type de document :
Communication dans un congrès
Colin Boyd. Asiacrypt, 2001, Gold Coast, Australia. Springer Verlag, 2248, pp.480-494, 2001, LNCS. 〈10.1007/3-540-45682-1_28〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00514826
Contributeur : Pierrick Gaudry <>
Soumis le : vendredi 3 septembre 2010 - 12:52:53
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44
Document(s) archivé(s) le : samedi 4 décembre 2010 - 02:46:14

Fichier

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

Identifiants

Collections

Citation

Pierrick Gaudry, Nicolas Gürel. An extension of Kedlaya's algorithm to superelliptic curves. Colin Boyd. Asiacrypt, 2001, Gold Coast, Australia. Springer Verlag, 2248, pp.480-494, 2001, LNCS. 〈10.1007/3-540-45682-1_28〉. 〈inria-00514826〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

49