What does Hasse's theorem say about the number of points on an elliptic curve over $\mathbb{F}_p$?
Hasse's theorem bounds the group order: $p + 1 - 2\sqrt{p} \leq |E(\mathbb{F}_p)| \leq p + 1 + 2\sqrt{p}$. The number of points is approximately $p$, give or take $2\sqrt{p}$.
* The number of points is pinned to a narrow band of width $4\sqrt{p}$ around $p+1$ — tiny relative to $p$, so the group is always about the field size. *
The theorem: For an elliptic curve $E$ over $\mathbb{F}_p$: $$|E(\mathbb{F}_p)| = p + 1 - t \quad \text{where } |t| \leq 2\sqrt{p}$$
The value $t$ is called the trace of Frobenius.
What this means in practice:
- For a 256-bit prime $p$, the group has roughly $2^{256}$ points
- The deviation from $p + 1$ is at most $2\sqrt{p} \approx 2^{129}$ — negligible compared to $p$
- The group order is roughly the same as the field size
Why this matters for cryptography:
- Security depends on the group order $n = |E|$ (specifically, on the largest prime factor of $n$)
- Hasse guarantees that we always get a group of about the right size
- We want $n$ to have a large prime factor (ideally $n$ itself is prime for maximum security)
- If $n$ is prime, every non-identity point is a generator — simplifying parameter selection
Point counting: Computing the exact group order is done with Schoof's algorithm (polynomial time) — essential for verifying that a chosen curve has good security properties.
Go deeper:
Hasse's theorem on elliptic curves — Wikipedia — the $p+1\pm2\sqrt{p}$ bound and its link to the Frobenius trace.