notes
- January 9, 2024

# Schoof's algorithm

In 1985, René Schoof published a paper 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

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

Let us have the elliptic curve

overBy Hasse's theorem:

Let us have the set of primes

such that the product of these primes is sufficiently large:The main idea behind Schoof's algorithm is to compute

Let

be the Frobenius endomorphism:It holds:

So we have a formula which we can use to compute

The formula above means:

We find a point

of the order Let Because we have a point of the order we have:And:

The point

is also of the order so we compute and have:We know everything except

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