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:
-
\(\phi^2 - [t]\phi + [q] = [0]\)
-
\(|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
-
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.
-
Schoof’s Algorithm: determines \(t \mod L\) for any \(L > 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).