Genus 2 point counting over prime fields

Pierrick Gaudry 1 Éric Schost 2
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : For counting points of genus 2 curves over a large prime field, the best known approach is essentially an extension of Schoof's genus 1 algorithm. We propose various practical improvements to this method and illustrate them with a large scale computation: we counted hundreds of curves, until one was found that is suitable for cryptographic use, with a state-of-the-art security level of approximately 2^128 and desirable speed properties. This curve and its quadratic twist have a Jacobian group whose order is 16 times a prime.
Document type :
Journal articles
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/inria-00542650
Contributor : Pierrick Gaudry <>
Submitted on : Friday, December 3, 2010 - 10:21:39 AM
Last modification on : Tuesday, December 18, 2018 - 4:18:25 PM
Long-term archiving on : Monday, November 5, 2012 - 11:15:57 AM

File

countg2.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Pierrick Gaudry, Éric Schost. Genus 2 point counting over prime fields. Journal of Symbolic Computation, Elsevier, 2012, 47 (4), pp.368-400. ⟨10.1016/j.jsc.2011.09.003⟩. ⟨inria-00542650⟩

Share

Metrics

Record views

571

Files downloads

627