Cryptography Reference
In-Depth Information
second prime the most abundant order is 48, corresponding to the curves of trace 0
(we will see later that the DLP is easier than usual in curves of trace 0 or trace 2).
Investigate also the prime 43 and observe that in this case the most abundant orders
are 40 and 48 (corresponding to traces 4 and
−
4).
The previous method to compute the orders of elliptic curves runs, as we have
mentioned, in exponential time. A more efficient—but still exponential—method
based on the same argument consists of storing the Legendre symbols of all elements
of the field in a list or array. This can be more efficiently accomplished without
actually computing Legendre symbols. Instead, a one-dimensional array
ls
, indexed
by the range 0
..
p
−
1, is initialized by setting all entries equal to
−
1. Then we set
0, compute the squares
x
2
mod
p
ls
[
0
]:=
∈ F
p
for
x
=
1
,...,
p
−
1, and set
x
2
mod
p
. At the end of this process we have that
ls
[
s
]:=
1 for each square
s
=
p
for all
x
ls
[
x
]=
∈[
0
,
p
−
1
]
. Then, given an elliptic curve, we compute the
b
and we obtain
x
∈F
p
x
3
as the sum of the terms
+
ax
+
b
p
elements
x
3
+
ax
+
x
3
ls
. This way we do not have to use quadratic reciprocity and, moreover,
much is gained in speed if we want to compute the orders of many elliptic curves
over the same field because
ls
is only computed once for a given
[
+
ax
+
b
]
F
p
. We illustrate
this method by coding it in Maple.
We start by giving a procedure to build the array just described. This is done
by the following function that, on input a prime
p
outputs the array containing the
Legendre symbols modulo
p
:
> LS := proc(p::posint)
local ls, i;
if not isprime(p) orp<5then
error "%1 is not a prime >3", p
end if;
ls := Array(0 .. p-1, datatype = integer[1], fill = -1);
ls[0] := 0;
for i to p-1 do
ls[iˆ2 mod p] := 1
end do;
ls
end proc:
The next procedure computes the order of the group of points of an elliptic curve
E
over
F
p
on input the curve
E
and an array containing the Legendre symbols of
the elements of
F
p
in the format output by the function
LS
:
> EllipticGroupOrderL := proc(E::list(integer), ls::Array)
local a, b, p, i;
a := E[1];
b := E[2];
p := E[3];
1+p+add(ls[(iˆ3+a*i+b) mod p], i=0..p-1)
end proc:
This is more efficient than the previous function
EllipticGroupOrder
.For
example, the following order is quickly computed:
> EllipticGroupOrderL(EllipticCurve(9550684, 11443958, 12345701), LS(12345701));
12344442
