Schoof’s algorithm

In 1985, René Schoof published a paper (opens new window) titled "Counting points on elliptic curves over finite fields". It is about an efficient algorithm for computing the number of points on elliptic curves over finite fields $F_q.$

The notes below are just a brief sketch of the proof.

Let us have the elliptic curve $E: y^2 = x^3 + ax + b$ over $F_q.$

By Hasse’s theorem:

$\#E = q + 1 - t,$

$t < 2\sqrt q.$

Let us have the set of primes $S = \{2,3,5,7,...,L\}$ such that the product of these primes is sufficiently large:

$\Pi_{l \in S}l > 4\sqrt q$

The main idea behind Schoof’s algorithm is to compute

$t \; mod \; l \; \text{for} \; \text{ each } \; l \in S$

and then to compute $t$ by using the Chinese remainder theorem.

Let $\phi_q$ be the Frobenius endomorphism:

$\phi_q(x, y) = (x^q, y^q)$

It holds:

$\phi_q^2 - t\phi_q + q = 0$

So we have a formula which we can use to compute $t.$

The formula above means:

$(x^{q^2}, y^{q^2}) - t(x^q, y^q) + q(x, y) = 0$

We find a point $(x, y)$ of the order $l.$ Let $q_l = q \; mod \; l.$ Because we have a point of the order $l,$ we have:

$q(x,y) = q_l(x,y)$

And:

$(x^{q^2}, y^{q^2}) + q_l(x, y) = t(x^q, y^q)$

The point $(x^q, y^q)$ is also of the order $l,$ so we compute $t_l = t \; mod \; l$ and have:

$(x^{q^2}, y^{q^2}) + q_l(x, y) = t_l(x^q, y^q)$

We know everything except $t_l$ in the equation. We search for $t_l$ such that the equation holds. When we succeed, we know the number of points modulo $l.$ We need to do this for all $l \in S$ and then apply the Chinese remainder theorem.