For my diploma thesis, I have implemented Satoh’s algorithm for counting points on elliptic curves over finite fields of small characteristic in C++ (using NTL and GMP).

Example

GF(23^{37}) = GF(23)[X]/(F(X)), F(X) = 22 + X^{2} + X^{37}

E/GF(23^{37}): y^{2} = x^{3} + ax + b

a = 1 + X + X^{2} + 19X^{4} + (F(X))

b = 2 + 3X + 4X^{2} + 7X^{5} + (F(X))

#E(GF(23^{37})) = 11 × 47 × 67 × 37313 × q

A combination of Satoh’s algorithm and an “early-abort strategy” was used to find cryptographically strong curves
(with prime order) for all characteristics up to 809 (representation).
Besides, these results may be current point counting records for elliptic curves over finite fields GF(p^{n}) with p ≥ 5 and n≫1.

The needed modular polynomials have to be provided separately. For p ≥ 367, I thankfully used the coefficients published by Andrew Sutherland. In addition to (classical) modular polynomials, the implementation also relies on division polynomials, which can be partially precomputed (based on the work of James McKee).

If you are interested in running times, you may follow these links (ordered by speed), where n is always the *smallest* prime such that p^{n} > 2^{512}