Cryptography Reference
In-Depth Information
9.10.2 Counting points on elliptic curves
A computational problem of fundamental importance is to compute #
E
(
F
q
) where
E
is
an elliptic curve over a finite field
F
q
. Due to lack of space we are unable to give a full
treatment of this topic.
We know that #
E
(
2
√
q,q
2
√
q
]. In many
F
q
) lies in the Hasse interval [
q
+
1
−
+
1
+
cases, to determine #
E
(
F
q
) it suffices to determine the order
n
of a random point
P
∈
E
(
F
q
).
Determining all multiples of
n
that lie in the Hasse interval for a point in
E
(
F
q
) can be done
using the baby-step-giant-step algorithm in
O
(
q
1
/
4
) bit operations (see Exercise
13.3.11
).
If there is only one multiple of
n
in the Hasse interval th
en
we have determined #
E
(
F
q
). This
4
√
q
. Mestre suggested determining the
F
q
) uniquely if
n
≤
process will not determine #
E
(
F
q
) and its quadratic twist. This leads to a randomised algorithm
order of points on both
E
(
F
q
)in
O
(
q
1
/
4
) bit operations. We refer to Section 3 of Schoof [
477
]for
to compute #
E
(
details.
A polynomial-time algorithm to compute #
E
(
F
q
) was given by Schoof [
475
,
477
].
Improvements have been given by numerous authors, especially Atkin and Elkies. The
crucial idea is to use equation (
9.11
). Indeed, the basis of Schoof's algorithm is that if
P
is
a point of small prime order
l
then one can compute
t
(mod
l
) by solving the (easy) discrete
logarithm problem
π
q
(
π
q
(
P
))
+
[
q
]
P
=
[
t
(mod
l
)]
π
q
(
P
)
.
One finds a point
P
of order
l
using the division polynomials (in fact, Schoof never writes
down an explicit
P
, but rather works with a “generic” point of order
l
by performing
polynomial arithmetic modulo
ψ
l
(
x,y
)). Repeating this idea for different small primes
l
and applying the Chinese remainder theorem gives
t
. We refer to [
477
], Chapters VI and VII
of [
60
], Chapter VI of [
61
] and Chapter 17 of [
16
] for details and references.
Exercise 9.10.24
Let
E
:
y
2
F
q
. Show that one can determine
t
(mod 2) by
considering the number of roots of
F
(
x
)in
=
F
(
x
) over
F
q
.
There are a number of point counting algorithms using
p
-adic ideas. We do not have
space to discuss these algorithms. See Chapter VI of [
61
] and Chapter IV of [
16
] for details
and references.
9.11 Supersingular elliptic curves
This section is about a particular class of elliptic curves over finite fields that have quite
different properties to the general case. For many cryptographic applications these ellip-
tic curves are avoided, though in pairing-based cryptography they have some desirable
properties.
p
m
where
p
is prime and let
E
be an elliptic curve over
Exercise 9.11.1
Let
q
=
F
q
. Show
using Exercise
9.10.9
that if #
E
(
F
q
)
≡
1(mod
p
) then #
E
(
F
q
n
)
≡
1(mod
p
) for all
n
∈ N
.
Hence, show that
E
[
p
]
={
O
E
}
for such an elliptic curve.
