Elliptic Curves
Schoof's Point Counting Algorithm
Schoof's polynomial-time algorithm for counting points on a curve over a finite field, and the SEA improvements.
Engineering / MathematicsElliptic Curves2 min readKV-MATH-0645
Schoof's algorithm counts points on a curve over a finite field in time polynomial in the logarithm of the field size. It was the first such method and it made cryptographic-size point counting possible.
The idea
The trace of Frobenius is determined modulo many small primes by working in the torsion subgroups, then reassembled by the Chinese remainder theorem. The Hasse bound tells you when enough primes have been used.
Schoof's algorithm
- Choose small primesEnough that their product exceeds the width of the Hasse interval.
- Work in the l-torsionRepresented as the quotient by the l-th division polynomial.
- Test candidatesFind the value of the trace modulo l satisfying the Frobenius relation there.
- ReassembleApply the Chinese remainder theorem.
- SelectThe Hasse bound identifies the unique candidate in range.
Division polynomials
The l-torsion points are the roots of the l-th division polynomial. Computing modulo it is how the algorithm works in the torsion subgroup without ever finding the points.
Cost
| Method | Complexity | Practical range |
|---|---|---|
| Baby-step giant-step | Fourth root of the field size | Moderate fields |
| Schoof | Polynomial in the logarithm, with a large exponent | Large fields, slowly |
| SEA | Substantially better in practice | Very large fields |
The SEA improvements
Elkies and Atkin observed that for many primes the division polynomial has a factor of much lower degree, obtainable from modular equations. Working modulo that factor instead is far cheaper.
- Elkies primes
- The modular equation has roots in the field; a low-degree factor exists and the trace is determined directly.
- Atkin primes
- No such factor; the modular equation still constrains the trace to a small set of possibilities.
- Combination
- Elkies primes give exact values; Atkin primes give constraints, combined by a search over the remaining possibilities.
Application
Point counting is required for Goldwasser-Kilian primality proving, where the order of the curve group must be known exactly. The expense of point counting is what motivated the Atkin-Morain alternative, which constructs curves of known order instead.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 7.4.4. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.