info prev up next book cdrom email home

Elliptic Group Modulo p

$E(a,b)/p$ denotes the elliptic Group modulo $p$ whose elements are $1$ and $\infty$ together with the pairs of Integers $(x,y)$ with $0\leq x,y<p$ satisfying

\begin{displaymath}
y^2\equiv x^3+ax+b\ \left({{\rm mod\ } {p}}\right)
\end{displaymath} (1)

with $a$ and $b$ Integers such that
\begin{displaymath}
4a^3+27b^2\not\equiv 0\ ({\rm mod\ }p).
\end{displaymath} (2)

Given $(x_1, y_1)$, define
\begin{displaymath}
(x_i,y_i)\equiv (x_1,y_1)^i\ \left({{\rm mod\ } {p}}\right).
\end{displaymath} (3)

The Order $h$ of $E(a,b)/p$ is given by
\begin{displaymath}
h=1+\sum_{x=1}^p \left[{\left({x^3+ax+b\over p}\right)+1}\right],
\end{displaymath} (4)

where $(x^3+ax+b/p)$ is the Legendre Symbol, although this Formula quickly becomes impractical. However, it has been proven that
\begin{displaymath}
p+1-2\sqrt{p} \leq h(E(a,b)/p)\leq p+1+2\sqrt{p}.
\end{displaymath} (5)

Furthermore, for $p$ a Prime $>3$ and Integer $n$ in the above interval, there exists $a$ and $b$ such that
\begin{displaymath}
h(E(a,b)/p)=n,
\end{displaymath} (6)

and the orders of elliptic Groups mod $p$ are nearly uniformly distributed in the interval.




© 1996-9 Eric W. Weisstein
1999-05-25