Elliptic curve point counting

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).


GF(2337) = GF(23)[X]/(F(X)), F(X) = 22 + X2 + X37

E/GF(2337): y2 = x3 + ax + b

a = 1 + X + X2 + 19X4 + (F(X))
b = 2 + 3X + 4X2 + 7X5 + (F(X))

#E(GF(2337)) = 11 × 47 × 67 × 37313 × q

q = 187285613829952805985­761367930316131263729

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(pn) 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 pn > 2512

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