Cryptography Reference
In-Depth Information
shows that the curve
y
2
x
3
F
5
has exactly 8 points. While this method
is not suitable for curves of cryptographic size, much larger orders can be computed
in a matter of seconds, for example:
=
+
4
x
over
> E := EllipticCurve(98316, 201554, 1234577):
EllipticGroupOrder(E);
1234599
The following Maple function generates, on input a prime
p
>
3, the list of all
elliptic curves defined over
F
p
.
> EllipticCurvesList := proc(p::posint)
local prod, curves, E;
if not isprime(p) orp<5then
error "%1 is not a prime greater than 3", p
end if
prod := combinat:-cartprod([[$0 .. p-1], [$0 .. p-1]]);
curves := [];
while not prod[finished] do
E := [op(prod[nextvalue]()), p];
if discr(E) <> 0 then
curves := [op(curves), E]
end if;
end do;
curves
end proc:
Example 11.5
The elliptic curves over
F
5
are the following:
> EllipticCurvesList(5);
[[0, 1, 5], [0, 2, 5], [0, 3, 5], [0, 4, 5], [1, 0, 5], [1, 1, 5], [1, 2, 5],
[1, 3, 5], [1, 4, 5], [2, 0, 5], [2, 1, 5], [2, 4, 5], [3, 0, 5], [3, 2, 5],
[3, 3, 5], [4, 0, 5], [4, 1, 5], [4, 2, 5], [4, 3, 5], [4, 4, 5]]
Exercise 11.11
Show that the number of elliptic curves over
F
p
,for
p
>
3, is exactly
p
2
p
. (Hint: Use the Legendre symbol to show that if 4
a
3
27
b
2
−
+
=
0
∈ F
p
, then
3
c
2
and
b
2
c
3
, and
c
is uniquely determined
there exists
c
∈ F
p
such that
a
=−
=
)
−
1
whenever
a
2
p
by
a
and
b
because
c
=−
3
b
(
2
a
=
0. This gives
p
pairs
(
a
,
b
)
∈ F
such that the curve
y
2
x
3
=
+
ax
+
b
is singular.)
F
5
listed in Example 11.5 are isomorphic to
some others, which means that the curves are essentially the same. We refer to [97,
181] for the definition of isomorphic elliptic curves and here we merely point out
that the curves over
Some of the 20 elliptic curves over
3) given by the equations
y
2
x
3
F
p
(with
p
=
2
,
=
+
ax
+
b
and
y
2
x
3
a
x
b
are isomorphic if and only if there exists
u
∈ F
p
such that
=
+
+
u
4
a
=
a
and
u
6
b
=
b
. We remark that isomorphic curves have isomorphic groups
of points but the converse does not hold (see Exercise 11.13 below.)
Example 11.6
We have seen in Example 11.1 that the elliptic curves over
F
5
given
by the equations
y
2
x
3
x
and
y
2
x
3
=
+
=
+
x
+
2 have groups isomorphic to
