Counting Points

Theorem [Hasse]: Consider an elliptic curve $E$ over a field of characteristic $q$.

Let $t = q + 1 - |E(\mathbb{F}_q)|$ (the trace of Frobenius).

Let $\phi$ denote the Frobenius map.

Then:

  1. $\phi^2 - [t]\phi + [q] = [0]$

  2. $|t| \le 2\sqrt{q}$

An elliptic curve is said to be supersingular if the characteristic of the field divides $t$.

Fact: Let $p = \mathrm{char} K$. Then a curve $E(K)$ is supersingular if and only if $p = 2,3$ and $j = 0$ (recall $j$ is the $j$-invariant), or $p \ge 5$ and $t = 0$.

Theorem [Weil]: Consider an elliptic curve $E$ over a finite field $\mathbb{F}_q$.

Let $t = q + 1 - |E(\mathbb{F}_q|$.

Let $\alpha, \beta$ be the roots of the equation $x^2 - tx + q$ in the complex numbers $\mathbb{C}$. Then $|E(\mathbb{F}_{q^m})| = q^m + 1 - (\alpha^m + \beta^m)$ for any positive integer $m$.

Theorem [Ruck]: $E(\mathbb{F}_q) \cong \mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2}$, where $n_1 | n_2$ and $n_1 | q-1$.

Algorithms

  1. Baby-step Giant-step: a probabilistic algorithm taking $O(\sqrt[4]{q}\log^2 q \log \log q)$ group operations and storage of $O(\sqrt[4]{q})$ group elements.

  2. Schoof’s Algorithm: determines $t \mod L$ for any $L \gt 4\sqrt{q}$ by solving $\phi^2 - t\phi + q = 0$ for a set of primes whose product exceeds $L$ (and applies the Chinese Remainder Theorem).