Cryptography Reference
In-Depth Information
> Statistics:-PointPlot(egos1009, xcoords = [$947 .. 1073],
color = black, symbol = solidcircle, symbolsize = 9);
The naive algorithmwe have used to compute the order of an elliptic curve runs in
exponential time and is not useful to compute the orders of elliptic curves suitable for
cryptographic use. The computation of these orders is important, however, because
one of the preferred methods to generate the curves is to choose a large finite field
and to randomly select curves over that field until one is found with a suitable order
which, as we will see, should be either prime or a product of a large prime by a small
integer.
Fortunately, there are efficient methods to compute the order and they are based
on an algorithm discovered by R. Schoof in 1985. If
E
is an elliptic curve over
F
q
,
p
n
a
nd
p
is prime, then we know by Hasse's theorem
t
hat the trace
t
where
q
=
2
√
q
and hence falls within an interval of length 4
√
q
. Therefore, in
order to determine
t
it
is
enough to compute
t
mod
l
forasetofsmallprimes
l
whose product is
satisfies
|
t
|≤
4
√
q
which, using the Chinese remainder theorem, determines
t
uniquely. This is the idea of Schoof's algorithm whose running time is
O
>
ln
8
q
(
)
,
which can be improved if asymptotically fast integer multiplication algorithms are
used.
