Genus 2 point counting over prime fields

Pierrick Gaudry (1) , Éric Schost (2)

1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
2 Department of Computer Science

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.

Domaines: Cryptographie et sécurité [cs.CR]

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