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
Reports

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 :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00071747
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

Identifiers

  • HAL Id : inria-00071747, version 1

Collections

Citation

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

Share

Metrics

Record views

86

Files downloads

200