Cryptography Reference
In-Depth Information
Finally, the next function
EllipticGroupOrders
(not to be confused with
the previous function
EllipticGroupOrder
, which only computes the order
of a single curve) computes the number of curves of each possible order over a
prime field
F
p
. The only required input parameter is
p
for the prime characteristic
and there is an additional optional parameter
ls
. This parameter is used for the
array containing the precomputed values of the Legendre symbols modulo
p
of the
elements of
F
p
and, if no argument is passed to it, this array is computed by default
within the f
un
ction. The out
pu
t is a one-dimensional array indexed by the range
p
2
√
p
2
√
p
(corresponding to the Hasse interval) and the value
corresponding to a given index
x
is the number of elliptic curves of order
x
:
+
1
−
..
p
+
1
+
> EllipticGroupOrders := proc(p::posint, ls::Array := LS(p))
local prod, t, orders, E, ord;
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]]);
t := floor(2*sqrt(p));
orders := Array(p+1-t .. p+1+t, datatype = integer[8]);
while not prod[finished] do
E := [op(prod[nextvalue]()), p];
if discr(E) <> 0 then
ord := EllipticGroupOrderL(E, ls);
orders[ord] := orders[ord] + 1
end if;
end do;
orders
end proc:
Example 11.8
We are going to use the previous procedure to compute the number of
curves of each possible order over
F
1009
. There are over one million elliptic curves
over this field (1009
2
1017072 curves, to be precise) and the function
computes the order of each of these curves. Since the average number of points
per curve is 1010, this computation involves going through over one billion points
(although, of course, the number of points in
−
1009
=
1009
is just 1009
2
and each of these
points belongs to many curves). We store the array containing the number of curves
of each order in a global Maple variable called
egos1009
:
F
> egos1009 := EllipticGroupOrders(1009):
1073 array and, for example, we can look at the minimum and
maximum values as well as at the total number of curves which are, respectively:
We obtain a 947
..
> min(egos1009);
max(egos1009);
add(egos1009[i], i = 947 .. 1073);
504
21168
1017072
We can obtain a visual representation of the distribution of the orders by plotting:
