| HAL-Inria | Publications, software ... of Inria's scientists |
Reports
Counting points in medium characteristic using Kedlaya's algorithm
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.
https://hal.inria.fr/inria-00071747
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:40:33 PM
Last modification on : Thursday, March 5, 2020 - 6:27:26 PM
Long-term archiving on: : Sunday, April 4, 2010 - 8:43:46 PM
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:40:33 PM
Last modification on : Thursday, March 5, 2020 - 6:27:26 PM
Long-term archiving on: : Sunday, April 4, 2010 - 8:43:46 PM