We begin by defining the concept of an elliptic curve.
Definition: Let p > 3 be prime. The elliptic curve
y2 = x3 + A x + B
over Zp is the set of solutions (x,
y) ∈ Zp ×
Zp to the congruence
y2 ≡ x3 + A x +
B (mod p),
where A, B ∈ Zp are
constants such that 4A3 + 27 B2
# 0 (mod p); together with a special point
O called the point at infinity.
The elliptic curve E can be made into an abelian group by
defining a suitable operation on its points. The operation is written
additively, and is defined as follows: Suppose
P = (x1, y1)
and
Q = (x2, y2)
are points on E. If x2 = x1
and y2 = -y1, then P +
Q = O, otherwise P + Q =
(x3, y3), where
x3 = λ2 - x1
- x2y3 = λ(x1
- x3) - y1,
and
λ =
Finally define
P + O = O + P = P
for all P ∈ E. With this definition of addition,
E is an abelian group with identity element O. The
inverse of (x, y) which we write as -(x,
y) since the group operation is additive, is (x,
-y), for all (x, y) ∈ E.
4.3 Elliptic Curves: Sample applet for small numbers
