MathLabs
TheoremProved

Hasse's bound

Statement

For an elliptic curve EE over a finite field Fp\mathbb{F}_p (pp prime), the number of points satisfies ∣#E(Fp)−(p+1)∣≤2p|\#E(\mathbb{F}_p) - (p+1)| \le 2\sqrt{p}.

Why is it true?

The quantity ap:=p+1−#E(Fp)a_p := p+1-\#E(\mathbb{F}_p) measures the 'error term' of the naive guess that a random cubic should have about pp solutions plus the point at infinity; Hasse's bound says this error can never be more than about 2p2\sqrt{p}, an astonishingly small deviation compared to the trivial bound of size pp, and it is what makes #E(Fp)\#E(\mathbb{F}_p) usable as a reliable, predictable group order in cryptographic constructions.

Proof sketch

Consider the Frobenius endomorphism φ:E(Fp‾)→E(Fp‾)\varphi: E(\overline{\mathbb{F}_p}) \to E(\overline{\mathbb{F}_p}), φ(x,y)=(xp,yp)\varphi(x,y) = (x^p, y^p). Its fixed points are exactly E(Fp)E(\mathbb{F}_p), and one shows #E(Fp)=deg⁡(φ−1)=p+1−t\#E(\mathbb{F}_p) = \deg(\varphi - 1) = p+1-t where t=φ+φ^t = \varphi + \hat\varphi is the trace of Frobenius acting on the endomorphism ring. The degree map on endomorphisms of EE is a positive-definite integer-valued quadratic form (it satisfies deg⁡(mφ+n)≥0\deg(m\varphi+n) \ge 0 for all integers m,nm,n, with equality only when mφ+n=0m\varphi+n=0), and deg⁡φ=p\deg\varphi = p. Expanding deg⁡(mφ+n)=m2p+mnt+n2≥0\deg(m\varphi+n) = m^2 p + mnt + n^2 \ge 0 as a quadratic form in m,nm,n forces its discriminant to be non-positive: t2−4p≤0t^2 - 4p \le 0, i.e. ∣t∣≤2p|t|\le 2\sqrt p. Since #E(Fp)−(p+1)=−t\#E(\mathbb{F}_p) - (p+1) = -t, this is exactly the claimed bound.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Joseph H. Silverman (2009). The Arithmetic of Elliptic Curves · DOI:10.1007/978-0-387-09494-6
  2. Andrew Wiles (1995). Modular elliptic curves and Fermat's Last Theorem · DOI:10.2307/2118559
  3. Andrew Wiles / Clay Mathematics Institute (2000). The Birch and Swinnerton-Dyer Conjecture (official Millennium Problem description)
  4. Wouter Castryck, Thomas Decru (2022). An efficient key recovery attack on SIDH