Elliptic Curves

Theorem [Hasse]: Consider an elliptic curve $E$ over a field of characteristic $q$. <br /> Let $t=q+1-\mid E({𝔽}_q)\mid$ (the trace of Frobenius). <br /> Let $\varphi$ denote the Frobenius map. Then <ol> <li> ${\varphi }^2-[t]\varphi +[q]=[0]$ </li> <li> $\mid t\mid \le 2\sqrt{q}$ </li> </ol>

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$. <br /> Let $t=q+1-\mid E({𝔽}_q\mid$. <br /> 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$.

<ol> <li> Baby-step Giant-step: a probabilistic algorithm taking <br /> $O(\sqrt[4]{q}{\log }^{2}q\log \log q)$ group operations and storage of <br /> $O(\sqrt[4]{q})$ group elements. </li> <li> 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). </li> </ol>