Cryptography Reference
In-Depth Information
smallest field containing a root of Φ
(
j, T
), by Proposition 12.20. Since
λ
k
and
μ
k
are quadratic conjugates and lie in
F
, they are equal. Therefore, (
φ
)
k
is scalar, so all roots of Φ
(
j, T
) lie in
F
p
k
, but none lies in any smaller field.
It follows that all the irreducible factors of Φ
(
j, T
)havedegree
r
=
k
.This
is Case (3).
In all three cases, the eigenvalues (or diagonal elements in Case (1)) of
(
φ
)
are
λ
and
μ
=
p/λ
.Wehave
a
= Trace((
φ
)
)=
λ
+
μ
.Moreove ,
λ
r
=
μ
r
=
p
r
/λ
r
since (
φ
)
r
is scalar. Therefore,
λ
2
r
=
p
r
, hence
λ
2
=
pζ
for
an
r
th root of unity
ζ
.Thisimpliesthat
a
2
=
λ
+
p
λ
2
=
λ
2
+2
p
+
p
2
λ
2
=
p
ζ
+2+
ζ
−
1
.
Suppose we are in Case (2) or (3). If
ζ
k
= 1 for some
k<r
,then
λ
2
k
=
p
k
=
λ
k
μ
k
,so
λ
k
=
μ
k
. This means that (
φ
)
k
is scalar, which contradicts the fact
that
r
is the smallest
k
with this property. Therefore,
ζ
is a primitive
r
th root
of unity. (Note that in Case (1), we have
ζ
= 1 and there are no primitive
th
roots of unity in
F
.) This completes the proof of the theorem.
In Example 12.5, the factorization of Φ
3
had factors of degrees 1, 1, 2, which
is case (2) of the theorem with
r
=2.
The primes
corresponding to Cases (1) and (2) are called
Elkies primes
.
Those for Case (3) are called
Atkin primes
. Atkin primes put restrictions
on the value of
a
mod
, but they allow many more possibilities than the
Elkies primes, which, after some more work, allow a determination of
a
mod
. However, Atkin showed how to combine information obtained from the
Atkin primes with the information obtained from Elkies primes to produce an
e
cient algorithm for computing
a
mod
(see [12, Section VII.9]).
12.5 Complements
Isogenies occur throughout the theory of elliptic curves. In Section 8.6,
Fermat's infinite descent involved two elliptic curves that are 2-isogenous. In
fact, the descent procedure of Section 8.2 can sometimes be refined using an
isogeny and its dual isogeny. This is what is happening in Section 8.6. See
[109] for the general situation.
Let
E
1
,E
2
be elliptic curves over
F
q
. If they are isogenous over
F
q
,then
#
E
1
(
F
q
)=#
E
2
(
F
q
) (Exercise 12.12). The amazing fact that the converse is
true was proved by Tate. In other words, if #
E
1
(
F
q
)=#
E
2
(
F
q
)then
E
1
,E
2
are isogenous over
F
q
. The condition #
E
1
(
F
q
)=#
E
2
(
F
q
) can be interpreted
as saying that
E
1
and
E
2
have the same zeta function (see Section 14.1), so
we see that the zeta function uniquely determines the isogeny class over
F
q
of an elliptic curve.
Search WWH ::
Custom Search