Cryptography Reference
In-Depth Information
Proof
We have
E
(
F
q
)
=
ker(
π
q
−
1) and, since
π
q
−
1 is separable, #
E
(
F
q
)
=
deg(
π
q
−
1). Now,
P
(1)
=
1
+
q
−
t
where, as noted in the proof of Theorem
9.9.3
,
t
=
1
+
deg(
π
q
)
−
deg(1
−
π
q
).
2 (mod 3). Show that the elliptic curve
E
:
y
2
x
3
Exercise 9.10.4
Let
p
≡
=
+
a
6
for
a
6
∈ F
p
has
p
F
p
.
[Hint: Rearrange the equation.]
+
1 points over
3(mod4)and
a
4
∈ F
p
. Show that
E
:
y
2
x
3
Exercise 9.10.5
Let
p
≡
=
+
a
4
x
over
F
p
has #
E
(
1.
[Hint: Write the right-hand side as
x
(
x
2
F
p
)
=
p
+
a
4
) and use the fact that (
−
p
)
+
=−
1.]
Theorem 9.10.6
(Hasse) Let E be an ellip
ti
c curve over
F
q
and denote by t the trace of
2
√
q.
the q-power Frobenius map. Then
|
t
|≤
Proof
(Sketch) The idea is to use the fact that deg : End(
E
)
is a positive definite
quadratic form. See Theorem V.1.1 of [
505
], Theorem 4.2 of [
560
], Theorem 1 of Chapter 25
of [
114
] or Theorem 13.4 of [
119
].
→ Z
In other words, th
e
number of p
oi
nts on an elliptic curve over
F
q
lies in the
Hasse
2
√
q,q
2
√
q
].
interval
[
q
+
1
−
+
1
+
Corollary 9.10.7
Let E be an elliptic curve over
F
q
and let P
(
T
)
be the characteristic
∈ C
=
−
−
=
polyno
mi
al of Frobenius. Le
t
α,β
be such that P
(
T
)
(
T
α
)(
T
β
)
. Then β
|=
√
q.
=
|
|=|
q/α
α and
α
β
∈ Z
Proof
It follows from the proof of Theorem
9.10.6
that if
P
(
T
)
[
T
] has a real root then
it is a repeated root (otherwise, the quadratic form is not positive definite). Obviously, if
the root
α
is not real then
β
=
α
. Since the constant coefficient of
P
(
T
)is
q
it follows that
2
and similarly for
β
.
q
=
αβ
=
αα
=|
α
|
=±
√
q
The
ca
se of repeated roots of
P
(
T
) on
ly
happens when
α
∈ Z
and
P
(
T
)
=
|=
√
q
is known as the
Riemann hypothesis for
elliptic curves
. This concept has been generalised to general varieties over finite fields as
part of the Weil conjectures (proved by Deligne).
±
√
q
)
2
. The condition
(
T
|
α
|=|
β
Corollary 9.10.8
Let E be an elliptic curve over
F
q
and let P
(
T
)
=
(
T
−
α
)(
T
−
β
)
be
α
n
)(1
β
n
)
.
the characteristic polynomial of Frobenius. Let n
∈ N
. Then
#
E
(
F
q
n
)
=
(1
−
−
ker(
π
q
−
Proof
We
have
E
(
F
q
n
)
=
ker(
π
q
n
−
1)
=
1).
The
result
follows
from
Lemma
9.9.6
.
Corollary
9.10.8
shows that for practical calculations we can identify the isogeny
π
q
with
a complex number
α
that is one of the roots of
P
(
T
). The name “complex multiplication”
for endomorphisms of elliptic curves that are not in
Z
comes from this identification.
When working with elliptic curves over
C
the analogy is even stronger, see Theorem 5.5
of [
505
].
