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

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

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

Given $(x_1, y_1)$, define
(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
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
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
\end{displaymath} (6)

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

© 1996-9 Eric W. Weisstein