Counting points in medium characteristic using Kedlaya's algorithm

Pierrick Gaudry 1, 2 Nicolas Gürel 1, 2
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : Recently, many new results have been found concerning algorithms for counting points on curves over finite fields of characteristic p, mostly due to the use of p-adic liftings. The complexity of these new methods is exponential in p therefore they behave well when p is small, the ideal case being p=2. When applicable, these new methods are usually faster than those based on SEA algorithms, and are more easily extended to non-elliptic curves. We investigate more precisely this dependance on the characteristic, and in particular, we show that after a few modifications using fast algorithms for radix-conversion, Kedlaya's algorithm works in time almost linear in p. As a consequence, this algorithm can also be applied to medium values of p. We give an example of a cryptographic size genus 3 hyperelliptic curve over a finite field of characteristic 251.
Type de document :
Article dans une revue
Experimental Mathematics (Project Euclid), A K Peters, Ltd, 2003, 12, pp.395-402
Liste complète des métadonnées
Contributeur : Pierrick Gaudry <>
Soumis le : vendredi 3 septembre 2010 - 13:09:20
Dernière modification le : mercredi 25 avril 2018 - 10:45:27
Document(s) archivé(s) le : samedi 4 décembre 2010 - 02:46:53


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00514830, version 1



Pierrick Gaudry, Nicolas Gürel. Counting points in medium characteristic using Kedlaya's algorithm. Experimental Mathematics (Project Euclid), A K Peters, Ltd, 2003, 12, pp.395-402. 〈inria-00514830〉



Consultations de la notice


Téléchargements de fichiers