For my diploma thesis, I have implemented Satoh’s algorithm for counting points on elliptic curves over finite fields 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 strong curves
(with prime order) for all characteristics up to 359 (representation).
Besides, these results may be current point counting records for elliptic curves over finite fields GF(p^{n}) with 5 ≤ p ≤ 359.

If you are interested in running times, you may follow these links: