Counting points on elliptic curves

Counting points on elliptic curves refers to the mathematical problem of determining the number of rational points that lie on a given elliptic curve, most commonly over a finite field $\mathbb{F}_q$. For an elliptic curve $E$ defined by a Weierstrass equation

$$ E: y^{2} = x^{3} + ax + b \qquad (a,b \in \mathbb{F}_q,; 4a^{3}+27b^{2} eq 0), $$

the set of $\mathbb{F}_q$-rational points $E(\mathbb{F}_q)$ consists of all pairs $(x,y) \in \mathbb{F}_q \times \mathbb{F}_q$ satisfying the equation, together with a distinguished point at infinity $O$. The count

$$ #E(\mathbb{F}_q) = |E(\mathbb{F}_q)| $$

is a central invariant in number theory and cryptography.

Theoretical background

• Hasse’s theorem (1936) provides a bound for the number of points:

  $$ \bigl|,#E(\mathbb{F}_q) - (q+1),\bigr| \le 2\sqrt{q}. $$

  The term $q+1$ is the expected number of points, and the deviation is called the trace of Frobenius $t = q + 1 - #E(\mathbb{F}_q)$, satisfying $|t| \le 2\sqrt{q}$.

• Weil conjectures (proved for curves by Weil) imply that the eigenvalues of the Frobenius endomorphism are complex numbers of absolute value $\sqrt{q}$, leading to the Hasse bound.

• Group structure: Over $\mathbb{F}_q$ the set $E(\mathbb{F}_q)$ forms a finite abelian group, isomorphic to

  $$ E(\mathbb{F}_q) \cong \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z}, $$

  where $n_2\mid n_1$. Knowledge of $#E(\mathbb{F}_q)$ determines the possible group structures.

Algorithms for point counting

1. Naïve enumeration

   • Directly test each $x \in \mathbb{F}_q$ to see whether the right‑hand side is a quadratic residue.
   • Complexity $O(q)$; feasible only for very small fields.

2. Baby‑step giant‑step (BSGS)

   • Uses the group law to search for the order of a chosen point.
   • Runs in $O(\sqrt{q})$ group operations, still impractical for cryptographic‑size fields (e.g., $q\approx 2^{256}$).

3. Schoof’s algorithm (1985)

   • Computes $#E(\mathbb{F}_q)$ in polynomial time $O(\log^{8} q)$ by determining the trace of Frobenius modulo small primes $\ell$ and applying the Chinese Remainder Theorem.
   • Works for any characteristic, but the original version is slower in practice.

4. Schoof–Elkies–Atkin (SEA) algorithm

   • An improvement of Schoof’s method that distinguishes Elkies and Atkin primes $\ell$.
   • For Elkies primes, one computes a modular polynomial to obtain a smaller-degree computation.
   • Typical running time $O(\log^{5} q)$ and widely used in implementations (e.g., in the PARI/GP, SageMath, and MAGMA libraries).

5. p‑adic methods (Satoh, Kedlaya, etc.)

   • Applicable when $q=p^{k}$ with small $p$.
   • Use $p$-adic cohomology to compute the characteristic polynomial of Frobenius.
   • Often faster than SEA for fields of characteristic 2 or 3.

Applications

• Elliptic Curve Cryptography (ECC) – Security parameters are selected so that $#E(\mathbb{F}_q)$ has a large prime factor, preventing discrete‑log attacks. Accurate point counting is required when generating cryptographically suitable curves (e.g., NIST, Brainpool, Curve25519).

• Pairing‑based cryptography – The order of the curve and of its twist must satisfy specific divisibility properties for efficient Tate or Weil pairings.

• Number theory – Point counting contributes to the verification of the Birch and Swinnerton‑Dyer conjecture for specific curves, and to the construction of curves with prescribed properties (e.g., maximal or minimal curves achieving the Hasse bound).

• Algorithmic research – Improvements in point‑counting algorithms influence broader computational arithmetic geometry, including the study of hyperelliptic curves and higher‑dimensional abelian varieties.

Example

For the curve $E: y^{2}=x^{3}+2x+3$ over $\mathbb{F}_{11}$:

Carrying out the table yields 12 affine points; adding the point at infinity gives $#E(\mathbb{F}_{11}) = 13$. The Hasse bound predicts $11+1-2\sqrt{11}\le#E\le11+1+2\sqrt{11}$, i.e. $5\le#E\le 17$, which is satisfied.

References

• H. Hasse, “Zur Theorie der abstrakten elliptischen Funktionenkörper. I. Die Struktur des Meromorphismenrings,” J. Reine Angew. Math. 1936.
• R. Schoof, “Counting points on elliptic curves over finite fields,” J. Théor. Nombres Bordeaux 1985.
• A. O. L. Atkin and J. H. Silverman, “Elliptic curve cryptosystems,” Advances in Cryptology – CRYPTO ’84.
• J. S. Milne, Elliptic Curves, online notes, 2022.

The above overview reflects the established mathematical understanding of counting points on elliptic curves.