An extension of Kedlaya's algorithm to superelliptic curves
Résumé
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.
Domaines
Cryptographie et sécurité [cs.CR]
Origine : Fichiers produits par l'(les) auteur(s)