Skip to Main content Skip to Navigation
Conference papers

An extension of Kedlaya's algorithm to superelliptic curves

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00514826
Contributor : Pierrick Gaudry <>
Submitted on : Friday, September 3, 2010 - 12:52:53 PM
Last modification on : Thursday, March 5, 2020 - 6:21:52 PM
Long-term archiving on: : Saturday, December 4, 2010 - 2:46:14 AM

File

asia01.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Pierrick Gaudry, Nicolas Gürel. An extension of Kedlaya's algorithm to superelliptic curves. Asiacrypt, 2001, Gold Coast, Australia. pp.480-494, ⟨10.1007/3-540-45682-1_28⟩. ⟨inria-00514826⟩

Share

Metrics

Record views

139

Files downloads

113