Cryptography Reference
In-Depth Information
The matrix (
φ
)
has characteristic polynomial
F
(
T
)=
T
2
PROOF
−
aT
+
p
.
If
F
(
T
) factors into distinct linear factors (
T
μ
)mod
,thenwe
can find a basis of
E
[
] that diagonalizes (
φ
)
. An eigenvector for
λ
is a
point
P
that generates a subgroup
C
1
such that
φ
(
P
)=
λP
for all
P
−
λ
)(
T
−
C
1
.
The eigenvalue
μ
yields a similar subgroup
C
2
.Since
λ
and
μ
are the only
two eigenvalues,
C
1
and
C
2
are the only two subgroups on which
φ
acts by
multiplication by an integer. By Proposition 12.20, there are exactly two
corresponding
j
-invariants in
F
p
that are roots of Φ
(
j, T
). Let
j
3
=
j
1
,j
2
be
another root of Φ
(
j, T
), and let
r
be the smallest integer such that
j
3
∈
F
p
r
.
By part (1) of Proposition 12.20, there is a subgroup
C
3
of
E
[
] and an integer
ν
such that
φ
r
(
P
)=
νP
for all
P ∈ C
3
.Moreover,
C
3
is the kernel of the
isogeny to a curve of invariant
j
3
∈
=
j
1
,j
2
, hence
C
3
=
C
1
,C
2
. This means
2matrix(
φ
)
r
,so(
φ
)
r
must
be scalar. Consequently, all subgroups
C
of order
are eigenspaces of (
φ
)
r
.
Part (1) of Proposition 12.20 implies that all roots of Φ
(
j, T
) lie in
F
p
r
.We
have therefore proved that all roots lie in the same field as
j
3
.Since
j
3
was
arbitrary,
r
is equal for all roots
j
3
that
C
1
,C
2
,C
3
are distinct eigenspaces of the 2
×
=
j
1
,j
2
. Since the minimal
r
such that
j
3
∈
F
p
r
is the degree of the irreducible factor that has
j
3
as a root, all
irreducible factors of Φ
(
j, T
), other than
T − j
1
and
T − j
2
,havedegree
r
.
This is Case (2). Since
T
2
− aT
+
p
factors in
F
, its discriminant
a
2
−
4
p
is
a square (this follows from the quadratic formula).
If
F
(
T
)=(
T − λ
)
2
for some
μ
, then either (
φ
)
is the scalar matrix
λI
,or
there is a basis for
E
[
] such that
(
φ
)
=
λ
1
.
0
λ
(This is the nondiagonal case of Jordan canonical form.) In the first case,
part (2) of Proposition 12.20 implies that Φ
(
j, T
) factors into linear factors
in
F
p
,and
a
2
−
4
p ≡
0(mod
), which is a square. This is the case
r
=1in
Case (2). In the other case, an easy induction shows that
λ
1
0
λ
k
=
λ
k
kλ
k−
1
0
.
λ
k
This is nondiagonal when
k<
and diagonal when
k
=
. Therefore, the
smallest
r
such that (
φ
)
r
has two independent eigenvectors is
r
=
,and(
φ
)
is
scalar. The reasoning used in Case (2) shows that Φ
(
j, T
) has an irreducible
factor of degree
. This yields Case (1). Since
F
(
T
) has a repeated root,
a
2
0(mod
).
Finally, suppose
F
(
T
) is irreducible over
F
.Then
a
2
−
4
p
≡
−
4
p
is not a square
mod
. There are no nontrivial eigenspaces over
F
, so there are no linear
factors of Φ
(
j, T
)over
F
.Let
λ
and
μ
be the two roots of
F
(
T
). They lie
in
F
2
and are quadratic conjugates of each other. The eigenvalues of (
φ
)
k
are
λ
k
and
μ
k
.Let
k
be the smallest exponent so that
λ
k
∈
F
. This is the
smallest
k
such that (
φ
)
k
has an eigenvalue in
F
p
, and therefore
F
p
k
is the
Search WWH ::
Custom Search