Hasse's bound on (foundation of ECM)
OpenPolyTimeFactorization.hasse_boundHasse's theorem (the Hasse bound). Let be prime and let be a Weierstrass curve
over with nonzero discriminant (equivalently, nonsingular, hence an elliptic curve). Let be the number of -rational points of the curve: the number of affine solutions of the Weierstrass equation, plus the single point at infinity. Then
This bound is the theoretical foundation of Lenstra's elliptic curve method: it places the group order in the interval , which is what makes ECM's smoothness heuristic plausible. It is a deep theorem — equivalent to the Riemann hypothesis for the curve's function field — and is not yet formalized in Mathlib.
Formalization Note. The curve is Mathlib's WeierstrassCurve (ZMod p); the affine solution set is counted with Nat.card over the subtype satisfying WeierstrassCurve.Affine.Equation, and the point at infinity contributes the explicit .
import Mathlib
namespace PolyTimeFactorization
theorem hasse_bound (p : ℕ) [Fact p.Prime] (W : WeierstrassCurve (ZMod p)) (hW : W.Δ ≠ 0) :
|((Nat.card {xy : ZMod p × ZMod p // WeierstrassCurve.Affine.Equation W xy.1 xy.2} : ℝ) + 1)
- ((p : ℝ) + 1)| ≤ 2 * Real.sqrt (p : ℝ) := by sorry
end PolyTimeFactorizationConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.