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

over

By 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

and then to compute
by using the Chinese remainder theorem.

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.

Boogie Math Newsletter

Some characters on this website might be partially or entirely fictional. You have been warned, my friend!

© 2023 Boogie Math, all rights reserved Follow us: Twitter