Cryptography Reference
In-Depth Information
The polynomial
x
3
4
x
2
has 0 as a double root over
F
5
(we already knew that this
should happen because it was obtained from the tangent line that intersects the curve
at
+
with multiplicity at least 2). To find the remaining root of this polynomial
we factor out the term
x
2
so that the remaining polynomial is
x
(
0
,
2
)
+
4. The only root of
this polynomial in
1 which is then the
x
-coordinate of the third intersection
point. To find the
y
-coordinate we substitute
x
F
5
is
x
=
=
1 in the equation of the tangent
and we obtain
y
=
1, so that the intersection point is
(
1
,
1
)
.Thesumof
(
0
,
2
)
with
itself is then the opposite of
(
1
,
1
)
, namely:
2
(
0
,
2
)
=
(
1
,
4
).
Since
(
1
,
4
)
=
(
0
,
−
2
)
=
(
0
,
3
)
we see that
(
0
,
2
)
does not have order 3. Hence it
has order 9 and so
H
is a generator.
We have given all these details to illustrate the chord-tangent method which works
over a finite field exactly the same as over
(
F
5
)
is cyclic and
(
0
,
2
)
. However, this calculation can be done
more quickly if one uses the duplication formula given in Theorem 11.1.
R
Exercise 11.7
Show that the group of points of the elliptic curve defined by
y
2
=
x
3
+
3
x
over
F
5
has 10 elements and prove, using Theorem 11.1, that
(
2
,
3
)
is a
generator of this group.
Exercise 11.8
Show that in the elliptic curve defined by
y
2
x
3
=
+
x
+
1 over
F
5
,
the point
(
2
,
1
)
is an inflection point.
F
5
defined by the equations
y
2
Exercise 11.9
Prove that the elliptic curves over
=
x
3
2,
y
2
x
3
2,
y
2
x
3
1,
y
2
x
3
1,
y
2
x
3
4
x
have
groups of order 3, 5, 6, 7, 8, respectively (together with the previous examples, this
shows that all integers in the interval
+
4
x
+
=
+
3
x
+
=
+
=
+
2
x
+
=
+
[
,
]
F
5
).
2
10
are orders of elliptic curves over
11.2.2 Elliptic Curve Elementary Computations
In order to be able to work with larger examples, we are going to give a simple Maple
implementation of elliptic curves over prime fields of characteristic greater than 3.
An elliptic curve over
F
p
will be given by a Weierstrass equation
y
2
x
3
b
whose discriminant is nonzero and we will represent it by a Maple list of the form
[
=
+
ax
+
. To initialize an elliptic curve we will use the following procedure which, on
input the parameters
a
,
b
,
p
, given either in decimal form or as hexadecimal strings,
checks that
p
is a (probable) prime
a
,
b
,
p
]
>
3 and that the discriminant is nonzero and, if
these conditions hold, outputs the list
[
a
,
b
,
p
]
in decimal form.
