improvements-point-counting-hyperelliptic-curves-genus-two

Abstract: 

Schoof's algorithm is a standard method for counting points on elliptic curves defined over finite fields of large characteristic, and it was extended by Pila to higher-dimensional abelian varieties. Improvements by Elkies and Atkin lead to an even faster method for elliptic curves, known as the SEA algorithm. This is the current state of the art for elliptic curves. Motivated by the fact that Jacobians of hyperelliptic curves of genus two have recently been found to be good alternatives to elliptic curves in cryptography, we investigate the possibility of applying the improvements of Elkies and Atkin to Pila's point counting algorithm for such varieties. We prove analogous theoretical results for genus two Jacobians with real multiplication by maximal orders, and we discuss the challenges involved in the practical implementation, such as the computation of suitable modular ideals.