Cryptography Reference
In-Depth Information
Example 4.5
Let
E
be the curve
y
2
=
x
3
+
x
+1 over
F
5
, as in Example 4.1. The nonzero
squares mod 5 are 1 and 4. Therefore
x
3
+
x
+1
5
4
#
E
(
F
5
)=5+1+
x
=0
=6+
1
5
+
3
5
+
1
5
+
1
5
+
4
5
=6+1
−
1+1+1+1=9
.
When using Theorem 4.14, it is possible to compute each individual gen-
eralized Legendre symbol quickly (see Exercise 4.4), but it is more e
cient
to square all the elements of
F
q
and store the list of squares. For simplicity,
consider the case of
F
p
. Make a vector with
p
entries, one for each element
of
F
p
. Initially, all entries in the vector are set equal to
−
1. For each
j
with
1
≤ j ≤
(
p−
1)
/
2, square
j
and reduce to get
k
mod
p
. Change the
k
th entry
in the vector to +1. Finally, change the 0th entry in the vector to 0. The
resulting vector will be a list of the values of the Legendre symbol.
Theorem 4.14, which is sometimes known as the Lang-Trotter method,
works quickly for small values of
q
, perhaps
q<
100, but is slow for larger
q
,
and is impossible to use when
q
is around 10
100
or larger.
4.3.3
Orders of Points
Let
P ∈ E
(
F
q
). The
order
of
P
is the smallest positive integer
k
such that
kP
=
. A fundamental result from group theory (a corollary of Lagrange's
theorem) is that the order of a point always divides the order of the group
E
(
F
q
). Also, for an integer
n
,wehave
nP
=
∞
∞
if and only if the order
o
f
P
divides
n
. By Hasse's theorem, #
E
(
F
q
)liesinanint
er
valoflength4
√
q
.
Therefore, if we can find a point of order greater than 4
√
q
, there can be only
one multiple of this order in the correct interval,
a
nd it must be #
E
(
F
q
).
Even if the order of the point is smaller than 4
√
q
, we obtain a small list
of possibilities for #
E
(
F
q
). Using a few more points often shortens the list
enough that there is a unique possibility for #
E
(
F
q
). For an addiitonal trick
that helps in this situation, see Proposition 4.18.
How do we find the order of a point? If we know the order of the full group
of points, then we can look at factors of this order. But, at present, the order
of the group is what we're trying to find. In Section 4.3.4, we'll discuss a
method (Baby Step, Giant Step) for finding the order of a point.
Search WWH ::
Custom Search