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 997 (representation).
Besides, these results may be current point counting records for elliptic curves over finite fields GF(p^{n}) with 5 ≤ p < 1000 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}

3.30 GHz Intel Core i7-5775R
2.60 GHz AWS Graviton3
3.40 GHz Intel Xeon Platinum 8151 (AWS)
3.80 GHz Intel Xeon Platinum 8252C (AWS)
3.60 GHz AMD Ryzen 7 3700X
3.20 GHz Apple M1fastest

*Yes, the single core performance of Apple's M1 is really impressive.*