Cryptography Reference
In-Depth Information
2.
φ
q
−
1
is a separable endom orphism , so
#
E
(
F
q
n
)=deg(
φ
q
−
1)
.
PROOF
Since
φ
q
is the Frobenius map for the field
F
q
n
, part (1) is just
a restatement of Lemma 4.5. The fact that
φ
q
−
1 is separable was proved in
Proposition 2.29. Therefore (2) follows from Proposition 2.21.
ProofofHasse'stheorem :
We can now prove Hasse's theorem (Theorem 4.2). Let
a
=
q
+1
−
#
E
(
F
q
)=
q
+1
−
deg(
φ
q
−
1)
.
(4.1)
We want to show that
|a|≤
2
√
q
.Weneedthefollowing.
LEMMA 4.8
Let
r, s
be integers w ith
gcd(
s, q
)=1
.Then
deg(
rφ
q
−
s
)=
r
2
q
+
s
2
−
rsa
.
PROOF
Proposition 3.16 implies that
s
)=
r
2
deg(
φ
q
)+
s
2
deg(
deg(
rφ
q
−
−
1) +
rs
(deg(
φ
q
−
1)
−
deg(
φ
q
)
−
deg(
−
1))
.
Since deg(
φ
q
)=
q
and deg(
−
1) = 1, the result follows from (4.1).
REMARK 4.9
The assumption that gcd(
s, q
) = 1 is not needed. We
include it since we have proved Proposition 3.16 not in general, but only
when the endomorphisms are separable or
φ
q
.
We can now finish the proof of Hasse's theorem. Since deg(
rφ
q
−
s
)
≥
0,
the lemma implies that
q
r
s
2
a
r
s
+1
−
≥
0
for all
r, s
with gcd(
s, q
) = 1. The set of rational numbers
r/s
such that
gcd(
s, q
) = 1 is dense in
R
.(
Proof:
Take
s
tobeapowerof2orapowerof3,
one of which must be relatively prime with
q
. The rationals of the form
r/
2
m
and those of the form
r/
3
m
are easily seen to be dense in
R
.) Therefore,
qx
2
−
ax
+1
≥
0
for all real numbers
x
. Therefore the discriminant of th
e p
olynomial is negative
or 0, which means that
a
2
2
√
q
. This completes the
−
4
q
≤
0, hence
|
a
|≤
proof of Hasse's theorem.
There are several major ingredients of the above proof. One is that we can
identify
E
(
F
q
)asthekernelof
φ
q
−
1. Another is that
φ
q
−
1 is separable,
Search WWH ::
Custom Search