Elliptic Curves

Theorem [Hasse]: Consider an elliptic curve $E$ over a field of characteristic $q$.
Let $t=q+1-\mid E({𝔽}_q)\mid$ (the trace of Frobenius).
Let $\varphi$ denote the Frobenius map. Then

1. ${\varphi }^2-[t]\varphi +[q]=[0]$
2. $\mid t\mid \le 2\sqrt{q}$

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

Fact: Let $p=charK$. Then a curve $E(K)$ is supersingular if and only if $p=\mathrm{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 ${𝔽}_q$.
Let $t=q+1-\mid E({𝔽}_q\mid$.
Let $\alpha ,\beta$ be the roots of the equation $x^2-\mathrm{tx}+q$ in the complex numbers $ℂ$. Then $\mid E({𝔽}_{q^m})\mid =q^m+1-({\alpha }^m+{\beta }^m)$ for any positive integer $m$.

Theorem [Ruck]: $E({𝔽}_q)\cong {\mathbb{Z}}_{n_1}\times {\mathbb{Z}}_{n_2}$, where $n_1\mid n_2$ and $n_1\mid 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 $tmodL$ for any $L>4\sqrt{q}$ by solving ${\varphi }^2-t\varphi +q=0$ for a set of primes whose product exceeds $L$ (and applies the Chinese Remainder Theorem).