| This thesis presents an asymptotically fast algorithm to count points on typical genus-2 hyperelliptic curves over large prime fields Fp . Specifically, the algorithm takes time ≤ (1g p) 8 (lg lg p)1+o(1) and space ≤ (lg p)5(lg lg p)0+o(1). The algorithm has been implemented and, by computer experiments, demonstrated to work on randomly chosen examples.;The previously fastest algorithm is due to Gaudry and Schost, improving upon a previous algorithm by Gaudry and Harley. The algorithm in this thesis has three important asymptotic improvements over the previous algorithms.;The ideas used in this algorithm are also expected to be useful in practice. In very recent followup work, extending the work presented in this thesis and incorporating other ideas, Gaudry and Schost have successfully counted points on a genus-2 curve over a 127-bit prime field. Continued computations will eventually find a suitable curve to standardize for high-speed high-security genus-2 hyperelliptic-curve cryptography, specifically a secure Gaudry-form genus-2 hyperelliptic curve with small coefficients. |
