Cryptography Reference
In-Depth Information
given do not apply when the field
K
has characteristic 2. In this section, we
sketch what happens in this case.
Note that the Weierstrass equation is singular. Let
f
(
x, y
)=
y
2
x
3
−
−
Ax
B
.Then
f
y
=2
y
= 0, since 2 = 0 in characteristic 2. Let
x
0
be a
root (possibly in some extension of
K
)of
f
x
=
−
3
x
2
A
=0andlet
y
0
bethesquarerootof
x
0
+
Ax
0
+
B
.Then
x
0
,y
0
)liesonthecurveand
f
x
(
x
0
,y
0
)=
f
y
(
x
0
,y
0
)=0.
Therefore, we work with the generalized Weierstrass equation for an elliptic
curve
E
:
−
−
y
2
+
a
1
xy
+
a
3
y
=
x
3
+
a
2
x
2
+
a
4
x
+
a
6
.
If
a
1
= 0, then the change of variables
x
=
a
1
x
1
+(
a
3
/a
1
)
,
y
=
a
1
y
1
+
a
−
3
(
a
1
a
4
+
a
3
)
1
changes the equation to the form
y
1
+
x
1
y
1
=
x
1
+
a
2
x
1
+
a
6
.
This curve is nonsingular if and only if
a
6
=0. The
j
-invariant in this case
is defined to be 1
/a
6
(more precisely, there are formulas for the
j
-invariant of
the generalized Weierstrass form, and these yield 1
/a
6
in this case).
If
a
1
=0,welet
x
=
x
1
+
a
2
,y
=
y
1
to obtain an equation of the form
y
1
+
a
3
y
1
=
x
1
+
a
4
x
1
+
a
6
.
This curve is nonsingular if and only if
a
3
=0. The
j
-invariant is defined to
be 0.
Let's return to the generalized Weierstrass equation and look for points at
infinity. Make the equation homogeneous:
y
2
z
+
a
1
xyz
+
a
3
yz
2
=
x
3
+
a
2
x
2
z
+
a
4
xz
2
+
a
6
z
3
.
Now set
z
= 0 to obtain 0 =
x
3
. Therefore,
=(0:1:0)istheonlypoint
at infinity on
E
, just as with the standard Weierstrass equation. A line
L
through (
x
0
,y
0
)and
∞
is a vertical line
x
=
x
0
.If(
x
0
,y
0
) lies on
E
then the
other point of intersection of
L
and
E
is (
x
0
, −a
1
x
0
− a
3
− y
0
). See Exercise
2.9.
We can now describe addition of points. Of course,
P
+
∞
=
P
, for all
points
P
.Threepoints
P, Q, R
add to
∞
if and only if they are collinear. The
negation of a point is given by
∞
−
(
x, y
)=(
x,
−
a
1
x
−
a
3
−
y
)
.
To add two p oints
P
1
and
P
2
, we therefore proceed as follows. Draw the line
L
through
P
1
and
P
2
(take the tangent if
P
1
=
P
2
). It will intersect
E
in a
third point
P
3
. Now compute
P
3
=
−P
3
bytheformulajustgiven(donot
simply reflect across the
x
-axis). Then
P
1
+
P
2
=
P
3
.
Search WWH ::
Custom Search