Cryptography Reference
In-Depth Information
Proof
See Corollary V.1.16 of Stichtenoth [
529
].
Equation (
10.18
) can be read in two ways. On the one hand, it shows that given
L
(
t
)
one can determine #
C
(
F
q
n
). On the other hand, it shows that if one knows #
C
(
F
q
n
)for
1
g
then one has
g
non-linear equations in the
g
variables
α
1
,...,α
g
(there are
only
g
variables since
α
i
+
g
=
≤
n
≤
g
). The following result shows that one can
therefore deduce the coefficients
a
1
,...,a
g
giving the polynomial
L
(
t
).
q/α
i
for 1
≤
i
≤
and define t
n
=
2
g
Lemma 10.7.6
(Newton's identities) Let α
1
,...,α
2
g
∈ C
i
=
1
α
i
. Let
a
1
,...,a
2
g
be such that
2
g
−
=
x
2
g
+
a
1
x
2
g
−
1
+···+
≤
≤
i
=
1
(
x
α
i
)
a
2
g
. Then, for
1
n
2
g,
n
−
1
na
n
=−
t
n
−
a
n
−
i
t
i
.
i
=
1
(
t
1
−
In particular, a
1
=−
t
1
and a
2
=
t
2
)
/
2
.
Exercise 10.7.7
Prove Lemma
10.7.6
.
Exercise 10.7.8
Suppose
C
is a genus 3 curve over
F
7
such that #
C
(
F
7
)
=
8
,
#
C
(
F
7
2
)
=
344. Determine
L
(
t
) and hence #Pic
0
F
7
(
C
). (One can take
y
2
x
7
92
,
#
C
(
F
7
3
)
=
=
+
x
+
1
for
C
.)
Exercise 10.7.9
(
Weil bounds
)Let
C
be a curve of genus
g
over
F
q
. Use Theorem
10.7.1
and Theorem 10.7.5 to show that
2
g
q
n
(
q
n
|
F
q
n
)
−
+
|≤
#
C
(
1)
and
(
q
n
(
q
n
1)
2
g
#Pic
0
1)
2
g
.
−
≤
F
q
n
(
C
)
≤
+
More precise bounds on #
C
(
F
q
) are known; we refer to Section V.3 of Stichtenoth [
529
]
for discussion and references.
Consider the
q
-power Frobenius map
π
:
C
(
x
q
,y
q
). This map
→
C
given by
π
(
x,y
)
=
induces a morphism
π
:
J
C
→
J
C
(indeed, an isogeny of Abelian varieties) where
J
C
is the
Jacobian variety of
C
. By considering the action of
π
on the Tate module (the Tate module
of an Abelian variety is defined in the analogous way to elliptic curves, see Section 19 of
Mumford [
398
]) it can be shown that
π
satisfies a characteristic equation given by a monic
polynomial
P
(
T
)
T
2
g
L
(1
/T
)
(we refer to Section 21 of [
398
], especially the subsection entitled “Application II: The
Riemann Hypothesis”).
∈ Z
[
T
]ofdegree2
g
. It can further be shown that
P
(
T
)
=
Definition 10.7.10
Let
C
be a curve over
F
q
.The
characteristic polynomial of Frobenius
=
T
2
g
L
(1
/T
).
is the polynomial
P
(
T
)
C
also induces the map
π
∗
:Pic
0
Pic
0
F
q
(
C
), and
we abuse notation by calling it
π
as well. If
D
is any divisor representing a divisor class in
The Frobenius map
π
:
C
→
F
q
(
C
)
→