Schoof's algorithm

Schoof's algorithm is an efficient algorithm to count points on elliptic curves over finite fields. The algorithm has applications in elliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving the discrete logarithm problem in the group of points on an elliptic curve.

The algorithm was published by René Schoof in 1985 and it was a theoretical breakthrough, as it was the first deterministic polynomial time algorithm for counting points on elliptic curves. Before Schoof's algorithm, approaches to counting points on elliptic curves such as the naive and baby-step giant-step algorithms were, for the most part, tedious and had an exponential running time.

This article explains Schoof's approach, laying emphasis on the mathematical ideas underlying the structure of the algorithm.

Let ${\displaystyle E}$ be an elliptic curve defined over the finite field ${\displaystyle \mathbb {F} _{q}}$, where ${\displaystyle q=p^{n}}$ for ${\displaystyle p}$ a prime and ${\displaystyle n}$ an integer ${\displaystyle \geq 1}$. Over a field of characteristic ${\displaystyle \neq 2,3}$ an elliptic curve can be given by a (short) Weierstrass equation

...
Wikipedia