Genus 2 point counting over prime fields

For counting points of Jacobians 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 21282128 and desirable speed properties. This curve and its quadratic twist have a Jacobian group whose order is 16 times a prime.

► We give a detailed point-counting algorithm for genus 2 curves over a prime field. ► We conduct a large-scale computation, using more than 1000,000 CPU hours. ► We obtain a doubly-secure curve with 128 bit security. ► This curve has small coefficients for the Kummer pseudo-group law.