Schoof’s algorithm turns elliptic-curve point counting into a finite collection of modular trace calculations. Instead of checking every x-coordinate in a large finite field, it computes the Frobenius trace modulo many small primes ℓ and reconstructs the unique integer trace allowed by Hasse’s bound.
This is a decisive algorithmic shift. The number of points on an elliptic curve over a finite field is not guessed from random sampling and need not be found by exhaustive enumeration. The curve’s Frobenius endomorphism satisfies an algebraic relation, and that relation can be tested on ℓ-torsion using exact polynomial arithmetic.
This is Guide 33 in the Bukit Timah Tutor Computational Number Theory series. It deepens the elliptic-curve arithmetic of Guide 8 and prepares the Schoof–Elkies–Atkin improvements in Guide 34.
1. The point-counting problem
Let
E: y²=x³+Ax+B
be a nonsingular elliptic curve over F_q, with q a prime power not of characteristic 2 or 3 for this short-Weierstrass discussion.
The goal is to compute
#E(F_q).
Write
#E(F_q)=q+1−t.
The integer t is the trace of Frobenius.
2. Hasse’s theorem makes the answer interval short
Hasse’s bound states
|t|≤2√q.
Thus the unknown trace lies in an interval of width about 4√q.
This means that if we determine t modulo an integer M satisfying
M>4√q,
then at most one integer in the Hasse interval can match that residue.
Schoof’s algorithm builds such an M as a product of small primes.
3. Frobenius endomorphism
The q-power Frobenius map is
π(x,y)=(x^q,y^q).
For points defined over F_q, π fixes the point. For points over extension fields, π acts nontrivially.
The fundamental relation is
π²−tπ+[q]=0
as endomorphisms of E, where [q] means scalar multiplication by q.
This is the elliptic-curve analogue of a characteristic polynomial.
4. The characteristic polynomial of Frobenius
Frobenius has characteristic polynomial
X²−tX+q.
Its roots are complex numbers α,β satisfying
α+β=t, αβ=q, |α|=|β|=√q.
Then
#E(F_q)=q+1−(α+β).
The same trace governs point counts over extensions through α^n+β^n.
5. Why small primes ℓ help
Choose a small prime ℓ different from the characteristic of F_q.
The ℓ-torsion group over an algebraic closure is
E[ℓ] ≅ (Z/ℓZ)².
On this two-dimensional vector space over F_ℓ, Frobenius satisfies
π²−tπ+q=0 mod ℓ.
Therefore it is enough to determine t modulo ℓ.
6. Division polynomials encode ℓ-torsion
The ℓ-division polynomial ψ_ℓ(x) vanishes at the x-coordinates of nonzero ℓ-torsion points.
For odd ℓ, its degree is
(ℓ²−1)/2.
Computations on generic ℓ-torsion points can therefore be carried out in a quotient ring such as
F_q[x]/(ψ_ℓ(x))
together with the curve equation for y.
Schoof avoids explicitly constructing the enormous extension field containing all ℓ-torsion points.
7. The trace test modulo ℓ
For a generic ℓ-torsion point P, test candidate residues τ in F_ℓ against
π²(P)+[q]P = [τ]π(P).
The correct τ equals t mod ℓ.
All group operations are reduced modulo the curve equation and division polynomial.
The algorithm uses additional shortcuts, including determination of t mod2 and tests based on whether q is a quadratic residue mod ℓ, but the governing identity remains the Frobenius characteristic equation.
8. Worked curve over F97
Consider
E: y²=x³+2x+3 over F97.
A direct count for this small teaching example gives
#E(F97)=100.
Therefore
t=97+1−100=−2.
Hasse permits
|t|≤2√97≈19.70.
So t lies between −19 and19.
9. What Schoof would recover
Rather than using the direct count, Schoof computes the trace modulo small primes.
For this curve the true residues are
t ≡1 (mod3) t ≡3 (mod5) t ≡5 (mod7).
Because
3·5·7=105>4√97≈39.40,
these three residues determine the trace uniquely inside the Hasse interval.
10. CRT reconstruction
Chinese remainder reconstruction gives
t ≡103 (mod105).
The integers congruent to103 mod105 are
..., −107, −2, 103, 208, ...
Only
t=−2
lies in the Hasse interval.
Hence
#E(F97)=97+1−(−2)=100.
11. Why the worked CRT example matters
The computational burden of Schoof is not CRT. CRT is the cheap final assembly stage.
The difficult part is obtaining each residue t mod ℓ exactly from Frobenius action on ℓ-torsion.
The teaching example separates these jobs: small-prime torsion computations provide local trace data; Hasse plus CRT turns that local data into the global point count.
12. Determining t modulo 2
The parity of #E(F_q) is controlled by rational 2-torsion.
A nontrivial 2-torsion point has y=0, so its x-coordinate is a root of
x³+Ax+B.
If the cubic has an F_q root, then E(F_q) has even order.
Since
#E(F_q)=q+1−t,
this gives t mod2.
13. Why exhaustive counting is not scalable
Naïvely, for every x in F_q one can test whether x³+Ax+B is a quadratic residue. This takes on the order of q field operations.
If q is a 256-bit prime, q is astronomically large. Exhaustive counting is impossible.
Schoof’s running time is polynomial in log q. That theoretical breakthrough made exact point counting algorithmically feasible in principle for large finite fields.
14. Polynomial-time significance
Schoof’s original algorithm was the first deterministic polynomial-time algorithm for counting points on elliptic curves over finite fields.
Its practical constants were large, but its conceptual importance is enormous: point counting belongs to polynomial-time computation in the input bit length.
Later improvements by Elkies and Atkin turned the framework into a practical high-performance method for many curves.
15. Frobenius over extension fields
Once t is known over F_q, define
S_0=2, S_1=t, S_n=tS_(n−1)−qS_(n−2).
Then
S_n=α^n+β^n.
Therefore
#E(F_(q^n))=q^n+1−S_n.
One point count controls infinitely many extension-field counts through a simple recurrence.
16. Example of extension counting
For the F97 curve with t=−2:
S_0=2, S_1=−2, S_2=t²−2q=4−194=−190.
Hence
#E(F_(97²))=97²+1−(−190) =9409+1+190 =9600.
This result follows without enumerating points in F_(97²).
17. Group order versus group structure
Schoof gives #E(F_q), not automatically the complete abelian-group decomposition.
The group has form
E(F_q) ≅ Z/n1Z × Z/n2Z, with n1|n2
and further constraints involving q−1.
Determining exact structure may require point-order tests, factoring the group order and additional computations.
18. Point counting and cryptographic subgroup design
Applications often require a large prime-order subgroup.
After computing
#E(F_q)=h·r
with large prime r and small cofactor h, one can select points in the r-order subgroup by multiplying random points by h and verifying the resulting order.
Exact point counting is therefore part of parameter validation, not merely a theoretical exercise.
19. Point counting and ECPP
Elliptic-curve primality proving also needs curves with suitably structured orders.
Generic point counting can discover an order; CM methods can instead construct curves with controlled candidate orders.
Schoof and CM therefore solve related problems from opposite directions: count a given curve, or construct a curve for a desired arithmetic trace.
20. Verification receipts
A point-counting computation should retain:
q and curve coefficients curve nonsingularity check selected small primes ℓ trace residue t mod ℓ for each ℓ product M of moduli CRT reconstruction Hasse-interval selection final #E(F_q).
For deeper verification, retain division-polynomial and Frobenius identities used for each trace residue.
21. Common mistakes
1. Confusing q+1+t with q+1−t. 2. Forgetting ℓ must differ from the field characteristic. 3. Assuming CRT reconstruction is unique before the modulus product exceeds the Hasse interval width.
4. Treating ψ_ℓ as if all of its roots lie in F_q. 5. Counting only affine points and forgetting the point at infinity. 6. Using floating Hasse bounds to choose an ambiguous integer trace. 7. Claiming Schoof outputs group structure automatically. 8. Confusing Frobenius trace with a matrix trace from an arbitrary coordinate representation.
22. Practice set
1. Define t in terms of #E(F_q). 2. State Hasse’s bound. 3. State the Frobenius characteristic equation. 4. Why does E[ℓ] look like a two-dimensional F_ℓ vector space?
5. What does ψ_ℓ encode? 6. For E/F97 with #E=100, compute t. 7. Give t mod3,5,7. 8. Why is modulus105 sufficient?
9. Reconstruct t. 10. Compute S2 for q=97,t=−2. 11. Compute #E(F_(97²)). 12. What is Schoof’s asymptotic conceptual advantage over exhaustive counting?
23. Answers
1. #E(F_q)=q+1−t. 2. |t|≤2√q. 3. π²−tπ+[q]=0. 4. For ℓ not equal to the characteristic, E[ℓ]≅(Z/ℓZ)².
5. x-coordinates of nonzero ℓ-torsion points. 6. −2. 7. 1,3,5. 8. 105>4√97. 9. −2 within the Hasse interval.
10. −190. 11. 9600. 12. Polynomial time in log q rather than work proportional to q.
Sources and further study
René Schoof, Counting points on elliptic curves over finite fields, Journal de Théorie des Nombres de Bordeaux 7 (1995), 219–254, surveys the torsion-based deterministic point-counting method and practical Atkin–Elkies improvements. For computational background, see standard elliptic-curve texts and computer algebra systems implementing finite-field point counting.
Continue through Batch 09
Continue to Guide 34: Schoof–Elkies–Atkin, Guide 35: Elliptic-Curve Isogenies, and Guide 36: Complex Multiplication and CM Curve Construction.