Cryptography Reference
In-Depth Information
(this is the same process as used to construct the
p
-adic (
=
l
-adic) numbers
Z
l
as the inverse
/l
i
limit of the rings
Z
Z
). More precisely, for each
i
∈ N
fix a pair
{
P
i,
1
,P
i,
2
}
of generators
for
E
[
l
i
] such that
P
i
−
1
,j
=
[
l
]
P
i,j
for
i>
1 and
j
∈{
1
,
2
}
. Via this basis, we can identify
E
[
l
i
] with (
/l
i
)
2
. Indeed, this is an isomorphism of (
/l
i
Z
Z
Z
Z
)-modules. It follows that
l
as a
T
l
(
E
)isa
Z
l
-module that is isomorphic to
Z
Z
l
-module. Hence, the set End
Z
l
(
T
l
(
E
))
of
Z
l
-linear maps from
T
l
(
E
)toitselfisisomorphicasa
Z
l
-module to
M
2
(
Z
l
). We refer to
Section III.7 of Silverman [
505
] for the details.
An isogeny
φ
:
E
→
E
gives rise to a linear map from
E
[
l
i
]to
E
[
l
i
] for each
i
. Writing
[
a
]
P
i,
1
+
[
b
]
P
i,
2
and
φ
(
P
i,
2
)
[
c
]
P
i,
1
+
[
d
]
P
i,
2
(where
{
P
i,
1
,P
i,
2
}
φ
(
P
i,
1
)
=
=
is a basis for
E
[
l
i
]) we can represent
φ
as a matrix (
ab
∈
Z
/l
i
Z
cd
)
M
2
(
). It follows that
φ
corresponds to
an element
φ
l
∈
Z
l
).
Write Hom
Z
l
(
T
l
(
E
1
)
,T
l
(
E
2
)) for the set of
M
2
(
Z
l
-module homomorphisms from
T
l
(
E
1
)to
T
l
(
E
2
). Since
T
l
(
E
) is isomorphic to
M
2
(
Z
l
) it follows that Hom
Z
l
(
T
l
(
E
1
)
,T
l
(
E
2
)) is a
Z
l
-module of rank 4. An important result is that
Hom
Z
l
(
T
l
(
E
1
)
,T
l
(
E
2
))
is injective (Theorem III.7.4 of [
505
]). It follows that Hom
k
(
E
1
,E
2
)isa
Hom
k
(
E
1
,E
2
)
⊗ Z
l
−→
Z
-module of rank
at most 4.
The map
φ
→
φ
is an involution in End
k
(
E
) and
φ
◦
φ
[
d
] where
d>
0. This con-
strains what sort of ring End
k
(
E
) can be (Silverman [505] Theorem III.9.3). The result is as
follows (for the definitions of orders in quadratic fields see Section
A.12
, and for quaternion
algebras see Vigneras [
558
]).
=
Theorem 9.9.1
Let E be an elliptic curve over a field
k
. Then
End
k
(
E
)
is either
Z
,an
order in an imaginary quadratic field, or an order in a definite quaternion algebra.
Proof
See Corollary III.9.4 of [
505
].
When
k
is a finite field then the case End
(
E
)
= Z
is impossible (see Theorem V.3.1
k
of [
505
]).
Let
E
:
y
2
x
3
Example 9.9.2
=
+
x
over
F
p
where
p
≡
3(mod4) is prime. Then
=
−
∈ F
p
2
satisfies
i
2
=−
ξ
(
x,y
)
(
x,iy
) is an isogeny where
i
1. One can verify that
ξ
2
=
◦
=
−
F
p
)
=
+
ξ
ξ
[
1]. One can show that #
E
(
p
1 (Exercise
9.10.5
) and then Theo-
rem
9.10.3
implies that the Frobenius map
π
p
(
x,y
)
=
(
x
p
,y
p
) satisfies
π
p
=
[
−
p
]. Finally,
we have
ξ
F
p
(
E
)isisomorphictoa
subring of the quaternion algebra (be warned that we are recycling the symbol
i
here)
Q
◦
π
p
(
x,y
)
=
(
−
x
p
,iy
p
)
=−
π
p
◦
ξ
(
x,y
). Hence, End
[
i,j
] with
i
2
1
,j
2
=−
=−
p,ij
=−
ji
. Note that End
F
p
(
E
) is isomorphic to
an
order,
[
√
−
(
√
−
containing
Z
p
], in the ring of integers of the imaginary quadratic field
Q
p
).
Every endomorphism on an elliptic curve satisfies a quadratic characteristic polynomial
with integer coefficients.
Theorem 9.9.3
Let E be an elliptic curve over
k
and φ
∈
End
k
(
E
)
be a non-zero isogeny.
deg(
φ
)
. Then there is an integer t such that φ
2
Let d
=
−
tφ
+
d
=
0
in
End
k
(
E
)
. In other