Cryptography Reference
In-Depth Information
+
1. We can give a simple heuristic argument that provides some justification for
this. Indeed, since half of the elements of
p
F
p
are quadratic residues, given the curve
y
2
=
f
(
x
)
one expects that approximately half of the nonzero values of
f
(
x
)
,for
x
in
F
p
, are quadratic residues. Since each of these values of
f
(
x
)
has two square
roots in
F
p
, we see that half the time the value of
x
gives two points on the curve and
the remaining half it gives no points at all. The values of
x
for which
f
0give
just one point each. Thus the number of points obtained this way is approximately
p
and hence, adding the point at infinity, we obtain
p
(
x
)
=
1 as the expected order value.
The following important theorem, conjectured by E. Artin and proved by Hasse
in the 1930s, shows that this heuristic reasoning is correct:
+
Theorem 11.3
(Hasse)
Let E be an elliptic curve defined over a finite field
F
q
(
p
m
where q
=
for some prime p
)
. Then the order of E
(
F
q
)
satisfies
2
√
q
2
√
q
q
+
1
−
≤|
E
(
F
q
)
|≤
q
+
1
+
.
We refer to [181, 197] for proofs of this theorem. The interval in the statement of
the theorem is often called the
Hasse interval
and the integer
t
=
q
+
1
−|
E
(
F
q
)
|
is
called the
trace
(or also the Frobenius trace) of the elliptic curve
E
over
F
q
.Using
the trace, Hasse's theorem for a curve over a prime
fie
ld
F
p
may be reformulated
2
√
p
. If we look at our previous
examples, we notice
th
at in them there is an elliptic curve of order
p
as saying that
|
E
(
F
p
)
|=
p
+
1
−
t
with
|
t
|≤
+
1
−
t
for each
2
√
p
, i.e., all the possible values in the Hasse interval are orders of
some curve. It can be shown that this is always the case when the underlying field is
a prime field of characteristic
p
t
such that
|
t
|≤
3.
Another fact which is of interest for some cryptographic applications—and also
for Lenstra's elliptic curve factoring algorithm ECM—is that, as Lenstra proved, the
orders of elliptic curve
s
over a prim
e
field
=
2
,
F
p
are “nearly uniformly distributed” on
−
√
p
+
√
p
the interval
. The precise statement of this result as well as
the way it is applied in ECM are presented in [53, Chap. 25] but suffice it to say that
the orders are fairly uniformly distributed in the interval, except that their density
drops off near the endpoints.
In order to better appreciate how the number of points of elliptic curves over
[
p
+
1
,
p
+
1
]
F
p
are distributed, we may use the following procedure that automatizes the method
used in Example 11.7 and plots a histogram of these numbers:
> EllipticOrdersHistogram := proc(p::posint)
local el, eo;
el := EllipticCurvesList(p);
eo := EllipticGroupOrder
∼
(el);
Statistics:-Histogram(eo, discrete=true, frequencyscale=absolute, color=black)
end proc:
Exercise 11.14
Use the function
EllipticOrdersHistogram
to plot the his-
tograms of the distribution of orders of elliptic curves over
F
p
when
p
=
37 and
47, and observe that for the former prime the most abundant orders are 36 and
40, which correspond to the curves of trace 2 and
p
=
−
2, respectively, while for the
