Schoof–Elkies–Atkin keeps Schoof’s Frobenius-trace framework but makes the small-prime calculations much more efficient by exploiting how Frobenius acts on ℓ-torsion.
The key distinction is whether the Frobenius characteristic polynomial splits modulo ℓ. If it does, ℓ is an Elkies prime and the ℓ-torsion decomposes into Frobenius eigenspaces that can be represented by much smaller polynomials. If it does not, ℓ is an Atkin prime and a different set of restrictions is used to narrow the possible trace residues.
This is Guide 34 in the Bukit Timah Tutor Computational Number Theory series. It builds directly on Guide 33: Schoof’s Algorithm.
1. Start from the Frobenius polynomial
For E/F_q with trace t, Frobenius satisfies
X²−tX+q.
Modulo a small prime ℓ≠char(F_q), its discriminant is
Δ_ℓ = t²−4q mod ℓ.
The splitting behaviour of this quadratic over F_ℓ determines whether ℓ is Elkies or Atkin.
2. Elkies prime
A prime ℓ is Elkies when
X²−tX+q
splits over F_ℓ with two distinct roots.
Equivalently, Δ_ℓ is a nonzero quadratic residue modulo ℓ.
Frobenius then has eigenvalues λ and μ in F_ℓ satisfying
λ+μ≡t (modℓ), λμ≡q (modℓ).
The corresponding eigenspaces are one-dimensional subgroups of E[ℓ].
3. Atkin prime
A prime ℓ is Atkin when the Frobenius polynomial is irreducible over F_ℓ.
Equivalently, Δ_ℓ is a quadratic nonresidue modulo ℓ.
Frobenius eigenvalues then lie in F_(ℓ²) rather than F_ℓ.
Although no rational eigenspace over F_ℓ is available, the action still constrains the possible trace t mod ℓ.
4. The ramified/special case
If
Δ_ℓ≡0 (modℓ),
the Frobenius polynomial has a repeated root. This special case is neither the generic Elkies nor the generic Atkin situation and must be handled separately.
A robust implementation therefore classifies ℓ into split, irreducible or repeated-root behaviour rather than forcing every prime into two bins blindly.
5. Worked curve from Guide 33
Use again
E: y²=x³+2x+3 over F97, #E(F97)=100, t=−2.
The Frobenius discriminant is
D=t²−4q =4−388 =−384.
We can use this known trace to illustrate how SEA would classify small primes.
6. ℓ=5 is Elkies
Reduce D modulo5:
−384≡1 (mod5).
Since1 is a nonzero square, ℓ=5 is Elkies.
The Frobenius polynomial is
X²−(−2)X+97 ≡X²+2X+2 ≡X²−3X+2 ≡(X−1)(X−2) (mod5).
Thus the eigenvalues are1 and2 modulo5.
Their sum is3, agreeing with
t≡−2≡3 (mod5).
7. ℓ=7 is Elkies
Now
−384≡1 (mod7),
again a square.
The Frobenius polynomial becomes
X²+2X+97 ≡X²+2X+6 ≡X²−5X+6 ≡(X−2)(X−3) (mod7).
The eigenvalues2 and3 sum to5, matching
t≡−2≡5 (mod7).
8. ℓ=11 is Elkies
Reduce the discriminant:
−384≡1 (mod11).
So ℓ=11 is also Elkies.
The trace residue is
t≡9 (mod11).
The existence of split eigenvalues lets the algorithm work with a kernel polynomial of degree about (ℓ−1)/2 rather than the full ℓ-division polynomial of degree about ℓ²/2.
9. ℓ=13 is Atkin
Reduce D modulo13:
−384≡6 (mod13).
The squares modulo13 are
1,3,4,9,10,12.
Since6 is not a square, ℓ=13 is Atkin.
The Frobenius characteristic polynomial is irreducible over F13.
10. Why Elkies primes are computationally valuable
In plain Schoof, one works modulo the full division polynomial ψ_ℓ, whose degree is roughly ℓ²/2.
For an Elkies prime, Frobenius preserves a one-dimensional ℓ-torsion subgroup. Its x-coordinates are described by a much smaller kernel polynomial of degree roughly (ℓ−1)/2.
Replacing quadratic-degree torsion algebra by linear-degree kernel algebra is the central practical speedup.
11. Modular polynomials
The classical modular polynomial Φ_ℓ(X,Y) encodes pairs of j-invariants linked by cyclic ℓ-isogenies.
For a curve with j-invariant j(E), compute
Φ_ℓ(j(E),Y) mod q.
If it has a root in F_q, then E has an F_q-rational ℓ-isogeny, corresponding generically to Elkies behaviour.
The root gives the j-invariant of an ℓ-isogenous neighbour.
12. j-invariant of the worked curve
For
E:y²=x³+Ax+B
with A=2,B=3, the j-invariant is
j=1728·4A³/(4A³+27B²).
Over F97, the denominator is
4·8+27·9=32+243=275≡81.
The numerator factor is
1728·32.
A production implementation computes this exactly modulo97 and inserts the result into Φ_ℓ.
13. Elkies eigenvalue route
Suppose λ is the Frobenius eigenvalue on the kernel of an ℓ-isogeny.
Because the second eigenvalue is q/λ modulo ℓ,
t ≡ λ + q λ^−1 (modℓ).
Thus identifying one eigenvalue gives the trace residue directly.
SEA uses isogeny-kernel information to determine λ far more efficiently than testing every τ in F_ℓ against full torsion arithmetic.
14. Atkin restrictions
For an Atkin prime, let r be the order of the ratio of Frobenius eigenvalues in the norm-one subgroup of F_(ℓ²)*.
The possible trace residues are constrained by this order.
Instead of producing one immediate residue, Atkin analysis often yields a small candidate set for t mod ℓ.
Combining several candidate sets with Hasse bounds and other primes still reduces the global trace search dramatically.
15. SEA is not “Schoof plus only Elkies primes”
Elkies primes provide the strongest practical speedups, but Atkin primes also contribute information.
A practical SEA implementation can use both, together with early-abort strategies and baby-step giant-step techniques for final trace disambiguation.
The algorithm is best viewed as an adaptive trace-information system rather than a rigid fixed list of tests.
16. Precomputed modular polynomials
Classical Φ_ℓ polynomials grow rapidly in coefficient size.
They depend only on ℓ, not on the target curve. Therefore they can be precomputed and reused across many point counts.
The memory and I/O cost of storing large modular polynomials becomes an engineering issue in its own right.
17. Alternative modular functions
Practical implementations often use modular functions with smaller modular equations than the classical j-polynomial Φ_ℓ.
Weber functions and other class invariants can reduce coefficient growth and accelerate evaluation.
The underlying isogeny information is unchanged; only the coordinate system used to encode modular relationships changes.
18. CRT trace accumulation
As each small prime contributes either an exact residue or a restricted candidate set, maintain the accumulated trace information modulo
M=product of used ℓ values.
Once the possible traces inside the Hasse interval collapse to one integer, stop.
There is no need to process unnecessary primes after uniqueness is established.
19. Expected distribution of Elkies primes
Heuristically, roughly half of suitable small primes behave as Elkies primes for a typical ordinary curve, because a random nonzero discriminant is a square about half the time.
Rigorous average and conditional results are more subtle, but the heuristic explains why SEA expects a steady supply of efficient Elkies steps.
20. Supersingular curves
Supersingular elliptic curves have exceptional endomorphism structure and can change the behaviour of point-counting and isogeny algorithms.
SEA remains meaningful, but ordinary-curve heuristics should not be transferred without checking the supersingular case.
Modern isogeny theory often treats ordinary and supersingular graphs as distinct computational worlds.
21. Complexity viewpoint
Schoof is deterministic polynomial time but expensive in practice because full ℓ-torsion polynomial degrees grow quadratically.
SEA lowers the practical and heuristic asymptotic cost by exploiting Elkies kernels of degree O(ℓ), together with faster modular polynomial and isogeny computations.
The exact complexity quoted depends on polynomial arithmetic, modular-polynomial availability, field size and algorithm variant.
22. Verification receipts
For each processed ℓ, retain:
ℓ classification: Elkies / Atkin / repeated modular-polynomial factorisation evidence kernel polynomial or Atkin order data trace residue or candidate set.
Then retain the accumulated CRT state, Hasse interval and final point count.
23. Common mistakes
1. Calling every square discriminant Elkies without handling Δ=0 separately. 2. Testing the integer discriminant instead of reducing modulo ℓ. 3. Confusing the elliptic-curve discriminant with the Frobenius discriminant t²−4q.
4. Assuming a root of Φ_ℓ(j,Y) directly gives the trace. It gives isogeny information used to recover the trace. 5. Forgetting q modulo ℓ in the eigenvalue formula. 6. Assuming all Atkin primes are useless. 7. Treating heuristic Elkies density as a theorem for every individual curve. 8. Mixing classical modular-polynomial Φ_ℓ with division-polynomial ψ_ℓ.
24. Practice set
1. Define the Frobenius discriminant. 2. What makes ℓ an Elkies prime? 3. What makes ℓ an Atkin prime? 4. What is the repeated-root case?
5. For q=97,t=−2 compute D. 6. Classify ℓ=5. 7. Factor the Frobenius polynomial mod5. 8. Classify ℓ=7.
9. Classify ℓ=13. 10. Why are Elkies kernel polynomials smaller? 11. What does Φ_ℓ(X,Y) encode? 12. State t in terms of one Frobenius eigenvalue λ.
25. Answers
1. t²−4q moduloℓ. 2. A nonzero square discriminant, so Frobenius splits over F_ℓ. 3. A nonsquare discriminant, so the polynomial is irreducible over F_ℓ. 4. Discriminant zero moduloℓ.
5. −384. 6. Elkies because D≡1 mod5. 7. (X−1)(X−2). 8. Elkies because D≡1 mod7.
9. Atkin because6 is a nonsquare mod13. 10. They represent one-dimensional Frobenius eigenspaces rather than all ℓ-torsion. 11. Cyclic ℓ-isogeny relationships between j-invariants. 12. t≡λ+qλ^−1 modℓ.
Sources and further study
René Schoof, Counting points on elliptic curves over finite fields, discusses Schoof’s algorithm together with practical improvements by Atkin and Elkies. Modern computational elliptic-curve systems use modular polynomials, kernel polynomials and fast finite-field arithmetic to implement SEA efficiently.
Continue through Batch 09
Return to Guide 33. Continue to Guide 35: Elliptic-Curve Isogenies and Guide 36: Complex Multiplication.