Elliptic Curves

Zeta Functions of Elliptic Curves

Counting points over finite fields, the Hasse bound, and how local counts assemble into a global zeta function.

Engineering / MathematicsElliptic Curves2 min readKV-MATH-0641

The number of points on a curve over a finite field is close to the field size, and the discrepancy is a single integer. Assembling these across all primes gives the curve's L-function.

The Hasse bound

|#E(F_q) - (q + 1)| <= 2 sqrt(q)The discrepancy is the trace of Frobenius.

Trace of Frobenius: The integer measuring the discrepancy. It determines the point count completely.
Hasse interval: The range of possible point counts, of width four times the square root of the field size.
Supersingular: Trace divisible by the characteristic. Rare and behaves differently.

Counting methods

Point counting methods
Method	Cost	Range
Exhaustive over x	Proportional to the field size	Very small fields
Baby-step giant-step	Fourth root of the field size	Moderate fields
Schoof	Polynomial in the logarithm of the field size	Large fields
SEA improvements	Substantially faster in practice	Very large fields

The local zeta function

For a curve over a finite field, the zeta function encoding point counts over all extensions is rational, with numerator determined by the trace of Frobenius.

Numerator = 1 - a T + q T^2a the trace of Frobenius; the roots have absolute value the square root of q.

Assembling globally

For a curve over the rationals, the local factors at all primes multiply into the L-function of the curve. Bad primes contribute simpler factors determined by the reduction type — see Tate's algorithm.

Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 7.3.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.