## 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 💡