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  q1\).
Algorithms

Babystep Giantstep: 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 \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).