Cryptography Reference
In-Depth Information
F
5
. Thus, apart from
O
quadratic non-residues in
, the only other point on the curve
(
,
)
(
F
5
)
={
O,(
,
)
}
is
0
0
, so that
E
0
0
, the (cyclic) group of order 2.
F
5
given by the equation
y
2
x
3
x
(in all
these examples the discriminant is nonzero, so we will not mention this fact again).
For
x
Consider now the curve
F
over
=
+
4, we obtain values of
x
3
=
1
,
+
x
which are quadratic non-residues but
3 we obtain
x
3
0; this is because the polynomial
x
3
for
x
=
0
,
2
,
+
x
=
+
x
splits into linear factors in
F
5
with the values of
x
just mentioned being its zeros.
Thus
F
is a 4-element group. Since all the nonzero
elements of the group have second coordinate 0 and hence have order 2, we can see
that the group is isomorphic to
(
F
5
)
={
O,(
0
,
0
), (
2
,
0
), (
3
,
0
)
}
Z
2
× Z
2
(the so-called “Four-Group”).
Next we look at the curve
G
defined by the equation
y
2
x
3
=
+
x
+
2 over
F
5
.
In this case we obtain the quadratic residue
y
2
=
4for
x
=
1. The square roots of 4
in
F
5
are 2 and
−
2mod5
=
3 so this gives us the points
(
1
,
2
)
,
(
1
,
3
)
.
x
=
4isa
root of
x
3
. The remaining values of
x
give
values of
y
2
which are quadratic non-residues and hence they give no points on the
curve. Thus
G
+
x
+
2 and hence gives the point
(
4
,
0
)
(
F
5
)
={
O,(
1
,
2
), (
1
,
3
), (
4
,
0
)
}
. In this case there is just one point of
order 2, namely
2 and,
by Lagrange's theorem this order must be a divisor of 4. Thus both points have order
4, which means that
G
(
4
,
0
)
. The remaining points except
O
must have order
=
1
,
(
F
5
)
is a group of order 4 (and hence isomorphic to
Z
4
)of
which both
are generators.
Let us now consider the curve
H
defined by
y
2
(
1
,
2
)
and
(
1
,
3
)
x
3
=
+
x
+
4 over
F
5
. Now, the only
∈ F
5
such that
x
3
value of
x
+
x
+
4 is a quadratic non-residue (with value 2) is
x
=
4
(
F
5
)
={
O,(
,
), (
,
), (
,
), (
,
), (
,
), (
,
),
and the remaining values give
H
0
2
0
3
1
1
1
4
2
2
2
3
(
,
), (
,
)
}
, which is a group of order 9. Since the order of a point divides the order
of the group, all points except
3
2
3
3
must have order either 3 (in which case they are
inflection points) or 9 (in which case they are generators of the group). If we find a
point which is not an inflection point thenwe know that it has order 9 and, in particular,
that the group is cyclic, and generated by this point. Let us check, for example, the
point
O
(
0
,
2
)
. Bearing in mind that
−
4
≡
1 mod 5, the equation of the curve may be
written as
y
2
4
x
3
y
2
4
x
3
+
+
4
x
+
1
≡
0
(
mod 5
)
and writing
h
(
x
,
y
)
=
+
+
4
x
+
1,
the tangent line to the curve at this point has the equation:
h
x
(
0
,
2
)(
y
−
2
)
+
h
y
(
0
,
2
)
x
≡
0
(
mod 5
).
After computing the partial derivatives and evaluating them at the point
(
0
,
2
)
,
this gives the equation 4
(
y
−
2
)
+
4
x
≡
0
(
mod 5
)
which, after some simplification,
may be written as:
y
≡
4
x
+
2
(
mod 5
).
Next we compute the third intersection point of this line with the elliptic curve.
Substituting this value of
y
into
h
we obtain:
2
x
3
x
3
4
x
2
(
4
x
+
2
)
≡
+
x
+
4
(
mod 5
)
⇔
+
≡
0
(
mod 5
).
