Counting Points On Elliptic Curves - Schoof's Algorithm

Schoof's Algorithm

A theoretical breakthrough for the problem of computing the cardinality of groups of the type was achieved by René Schoof, who, in 1985, published the first deterministic polynomial time algorithm. Central to Schoof's algorithm are the use of division polynomials and Hasse's theorem, along with the Chinese remainder theorem.

Schoof's insight exploits the fact that, by Hasse's Theorem, there is a finite range of possible values for . It suffices to compute modulo an integer . This is achieved by computing modulo primes whose product exceeds, and then applying the Chinese remainder theorem. The key to the algorithm is using the division polynomial to efficiently compute modulo .

The running time of Schoof's Algorithm is polynomial in, with an asymptotic complexity of, where denotes the complexity of multiplication. Its space complexity is .