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).


Ben Lynn blynn@cs.stanford.edu 💡