HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Counting points in medium characteristic using Kedlaya's algorithm

Pierrick Gaudry 1 Nicolas Gürel 1
1 TANC - Algorithmic number theory for cryptology
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 6:40:33 PM
Last modification on : Friday, February 4, 2022 - 3:14:43 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:43:46 PM


  • HAL Id : inria-00071747, version 1



Pierrick Gaudry, Nicolas Gürel. Counting points in medium characteristic using Kedlaya's algorithm. [Research Report] RR-4838, INRIA. 2003. ⟨inria-00071747⟩



Record views


Files downloads