Cryptography Reference
In-Depth Information
words, for all P
∈
E
(
k
)
,
φ
(
φ
(
P
))
−
[
t
]
φ
(
P
)
+
[
d
]
P
=
O
E
.
Proof
(Sketch) Choose an auxiliary prime
l
=
char(
k
). Then
φ
acts on the Tate module
T
l
(
E
) and so corresponds to a matrix
M
Hom
Z
l
(
T
l
(
E
)
,T
l
(
E
)). Such a matrix has a
determinant
d
and a trace
t
. The trick is to show that
d
∈
=
deg(
φ
) and
t
=
1
+
deg(
φ
)
−
deg(1
2 matrices when deg is replaced by det). These
statements are independent of
l
. Proposition V.2.3 of Silverman [
505
] gives the details (this
proof uses the Weil pairing). A slightly simpler proof is given in Lemma 24.4 of [
114
].
−
φ
) (which are standard facts for 2
×
Definition 9.9.4
The integer
t
in Theorem
9.9.3
is called the
trace
of the endomorphism.
End
k
(
E
) satisfies the equation
T
2
Exercise 9.9.5
Show that if
φ
∈
−
tT
+
d
=
0 then so
does
φ
.
Lemma 9.9.6
Suppose φ
∈
End
(
E
)
has characteristic polynomial P
(
T
)
=
T
2
−
tT
+
k
d
∈ Z
[
T
]
. Let α,β
∈ C
be the roots of P
(
T
)
. Then, for n
∈ N
, φ
n
satisfies the polynomial
α
n
)(
T
β
n
)
(
T
−
−
∈ Z
[
T
]
.
Proof
This is a standard result: let
M
be a matrix representing
φ
(or at least, representing
the action of
φ
on the Tate module for some
l
) in Jordan form
M
(
α
0
β
). Then
M
n
has
=
Jordan form (
α
n
∗
0
β
n
) and the result follows by the previous statements.
9.10 Frobenius map
We have seen that the
q
-power Frobenius on an elliptic curve over
F
q
is a non-zero isogeny
of degree
q
(Corollary
9.6.15
) and that isogenies on elliptic curves satisfy a quadratic
characteristic polynomial. Hence, there is an integer
t
such that
π
q
−
tπ
q
+
q
=
0
.
(9.11)
Definition 9.10.1
The integer
t
in equation (
9.11
) is called the
trace of Frobenius
.The
polynomial
P
(
T
)
=
T
2
−
+
tT
q
is the
characteristic polynomial of Frobenius
.
Note that End
F
q
(
E
) always contains the order
Z
[
π
q
], which is an order of discriminant
t
2
−
4
q
.
Example 9.10.2
Equation (
9.11
) implies
([
t
]
−
π
q
)
◦
π
q
=
[
q
]
π
q
=
−
and so we have
[
t
]
π
q
.
Theorem 9.10.3
Let E be an elliptic curve over
F
q
and let P
(
T
)
be the characteristic
polynomial of Frobenius. Then
#
E
(
F
q
)
=
P
(1)
.
