Cryptography Reference
In-Depth Information
p
m
, E an elliptic curve over
Theorem 9.10.16
Let p beaprime,q
=
F
q
and t
=
q
+
1
−
F
q
)
if and only if n
2
#
E
(
F
q
)
. Let n
∈ N
be such that p
n. Then E
[
n
]
⊆
E
(
|
(
q
+
1
−
t
)
,
2
√
q (equivalently, π
q
∈ Z
n
|
(
q
−
1)
, and (either t
=±
)or
End
F
q
(
E
)
contains the order
of discriminant
(
t
2
4
q
)
/n
2
).
−
Proof
If the kernel of
π
q
−
1 contains the kernel of [
n
] then, by Theorem
9.6.18
, there is an
isogeny
ψ
∈
End
F
q
(
E
) such that
π
q
−
1
=
ψ
◦
[
n
]. We write
ψ
=
(
π
q
−
1)
/n
. The result
follows easily; see Proposition 3.7 of Schoof [
476
] for the details.
F
q
with
2
gcd(
q,t
)
Exercise 9.10.17
Let
E
be an elliptic curve over
=
1, where #
E
(
F
q
)
=
q
+
1
−
t
. Deduce from Theorem
9.10.16
that if End
F
q
(
E
)
= Z
[
π
q
] then
E
(
F
q
) is a cyclic
group.
9.10.1 Complex multiplication
A lot of information about the numbers of points on elliptic curves arises from the theory of
complex multiplication. We do not have space to develop this theory in detail. Some crucial
tools are the lifting and reduction theorems of Deuring (see Sections 13.4 and 13.5 of
Lang [
328
] or Chapter 10 of Washington [
560
]). We summarise some of the most important
ideas in the following theorem.
Theorem 9.10.18
Let
be an order in an imaginary quadratic field K. Then there is a
number field L containing K (called the ring class field) and an elliptic curve E over L
with
End
L
(
E
)
=
O
O
.
Let p be a rational prime that splits completely in L, and let ℘ be a prime of
O
L
above
O
L
/℘
=
F
p
). If E
h
as good reduction modulo ℘ (this holds if ℘ does not divide
the discriminant of E) w
ri
te E for the elliptic curve over
p (so that
F
p
obtained as the reduction of E
F
p
(
E
)
=
O
modulo ℘. Then
End
and there is an element π
∈
O
such that p
=
ππ (where
the overline denotes complex conjugation). Furthermore
#
E
(
F
p
)
=
p
+
1
−
(
π
+
π
)
.
(9.12)
F
p
(
E
)
=
O
Conversely, every elliptic curve E over
F
p
such that
End
arises in this way as a
reduction modulo ℘ of an elliptic curve over L.
Proof
This is Theorem 14.16 of Cox [
145
]; we refer to the topics [
145
,
328
] for much more
information about complex multiplication and elliptic curves.
Remark 9.10.19
An important consequence of the theory of complex multiplication is that
the weighted number of
F
q
-isomorphism classes of elliptic curves over
F
q
with number
t
is the Hurwitz class number
3
H
(
t
2
of points equal to
q
4
q
) (see Theorem 14.18
of Cox [
145
], Section 1.5 of Lenstra [
339
] or Schoof [
476
]). The Hurwitz class number is
+
1
−
−
2
In fact, if gcd(
q,t
)
=
1 then the condition End
F
q
(
E
)
= Z
[
π
q
] never holds.
3
Lenstra and Schoof call it the Kronecker class number.
