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) in Zp ×
Zp to the congruence
y2 = x3 + A x +
B (mod p),
where A, B in 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 = lambda2 - x1
- x2y3 = lambda(x1
- x3) - y1,
and
lambda = (3x12 + a)
(2y1)-1 if P = Q
and else
lambda = (y2 - y1)
(x2 - x1)-1
Finally define
P + O = O + P = P
for all P in 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) in E.
4.3 Elliptic Curves: Sample applet for small numbers
