Coding Schoof's 1985 Elliptic Curve Point Counting Algorithm in Python

We teach programmers how to turn PhD-level math into Python code they understand.

Abstract for Elliptic Curves over Finite Fields and the Computation of Square Roots mod p (Schoof, 1985)Here’s 20% off scheduling meetings with Cal.comHere’s 20% off Simplified’s Marketing Agent

1.0 Paper Introduction

Elliptic Curves over Finite Fields and the Computation of Square Roots mod p (Schoof, 1985) 1 introduced the world’s first polynomial time algorithm to compute the number of points, denoted by #E(F q ), on an elliptic curve (Sutherland, 2025) 2.

(Schoof, 1985) is canonical because it reduced the complexity of counting points on elliptic curves from exponential to polynomial-time.

The algorithm is simple: compute the trace of frobenius t modulo many small primes and use the Chinese Remainder Theorem to uniquely determine t (Sutherland, 2025):

Schoof’s algorithm in pseudocode. Taken from page 1 of (Sutherland, 2025)

Schoof realized that a curve’s division polynomials identified torsion points modulo small primes. Then he related this to to the frobenius endomorphism. That’s how we got a polynomial-time point counting algo!

Arithmetic in the curve’s endomorphism leads to Schoof’s algorithm. Taken from page 2 of (Sutherland, 2025)

This is part of our series on Practical Elliptic Curve Theory For Programmers:Part 1: Hacking Dormant Bitcoin Wallets in C.Part 2: Smart Attack on Anomalous Curves.Part 3: Finding Anomalous Curves.Part 4: Division Polynomials of Elliptic Curves in Python.

Part 5 (we are here): Applying Division Polynomials to Point Counting.Part 6: Fast Point Multiplication on Curves With Efficient Endomorphisms.

2.0 Coding Schoof’s Algorithm

Code is available on GitHub and Google Colab *

• My work keeps appearing verbatim in Codex. This is theoretical math wildly outside the distribution so I know they’re training on my private repos.

This section closely follows (Dinges, 2010) 3. We assume you saw the Trace of Frobenius in Part 2 and t…