Cryptography Reference
In-Depth Information
There were subsequent improvements of Schoof's algorithm, mainly due to Elkies
and Atkin, which resulted in the so-called
SEA algorithm
which runs in time
O
ln
6
q
)
with standard multiplication techniques. We refer to [181, 197] for descriptions of
Schoof's algorithm. The SEA algorithm is also described in [197] and in more detail
in Chap. 17 of [53]. There are several available implementations of these algorithms,
such as those in the open source computer algebra package Sage [171], in the portable
C libraryMIRACL (which is free for academic and non-commercial use and contains
good support for elliptic curve cryptography) [143], and also in the computer alge-
bra package Magma [132]. For example, even the basic implementation of Schoof's
algorithm in MIRACL is able to compute reasonably quickly the order of an ellip-
tic curve group over
(
F
p
, with
p
a 256-bit prime—which is an adequate size for
cryptographic use—and the SEA algorithm can compute the order for much larger
primes.
Next we define a class of elliptic curves that play a special role in cryptographic
applications:
Definition 11.2
Let
E
be an elliptic curve defined over a finite field
F
q
of char-
acteristic
p
and let
t
be the trace of
E
. Then
E
is said to be
supersingular
6
if
p
divides
t
. Otherwise
E
is
ordinary
(or
non-supersingular
).
=
q
+
1
−|
E
(
F
q
)
|
Remark 11.2
It can be shown that an elliptic curve over a field
F
q
of characteristic
p
is supersingular precisely when the curve has no points of order
p
over an algebraic
closure of
F
q
[see, for example [197] (Proposition 4.31)].
In the particular case that
F
q
= F
p
is a prime field of characteristic
=
2
,
3 then
E
is supersingular if and
o
nly if
|
E
(
F
p
)
|=
p
+
1. This is because, by Hasse's theorem,
2
√
p
and hence
p
we have that
|
t
|≤
|
t
is equivalent to
t
=
0.
Example 11.9
Looking at the list containing the number of elliptic curves of each
possible order over
F
223
, computed in Example 11.7, we see that there are exactly
1554 supersingular curves, namely, the element in position 30 in the list, which
corresponds
to t
he curves of trace 0, since for
p
=
223 the maximum value of the
2
√
223
trace is
F
1009
studied in Example 11.8, we
may use the array
egos1009
and we see that the number of supersingular curves—
i.e., the number of curves of order 1010—is
egos1009[1010] = 10080
.
=
29. Similarly, in the case of
Exercise 11.15
Show that there are 4 supersingular elliptic curves over
F
5
distrib-
uted in two isomorphism classes containing two curves each.
>
Exercise 11.16
Write a Maple program that, given a prime
p
3 of moderate
size, computes the number of supersingular elliptic curves over
F
p
,aswellasthe
number of elliptic curves with trace equal to 1 (these are called anomalous curves,
see
11.3.3.2
below) and the number of curves with trace equal to 2. Use it to find the
6
Note that this use of the term supersingular gives rise to another little terminological paradox: a
supersingular elliptic curve is, by definition, nonsingular.
