Generalising AGM point-counting for elliptic curves over large finite fields of small characteristic


Michael Harrison


University of Sydney


Wed, 01/04/2015 - 1:30pm


OMB 145 (Old Main Building)


Extremely fast computational algorithms for determining the number of points on an elliptic curve over a large finite field of small characteristic p using canonical lifting to p-adic fields were introduced at the end of the 1990s. Satoh gave a general formulation for any p >= 5 based on canonical polynomials, which was quickly followed by the AGM/SST/MSST algorithms in characteristic 2 using different modular parameters and more efficient lifting methods. David Kohel generalised these AGM-style algorithms to the case of all p where a single modular parameter exists - i.e. where the modular curve X0(p) has genus 0: p<11 and p=13. I further generalised to the elliptic and hyperelliptic cases - where X0(p) can be defined by a Weierstrass equation - which covers most of the remaining p<50 as well as p=59 and 71.

In the talk, I shall explain the general theory behind these methods and give a detailed description of the genus > 0 cases.

School Seminar Series: