Cryptography Reference
In-Depth Information
Br oker [
100
] has given an algorithm to construct supersingular elliptic curves over
finite fields using the CM method. The method has expected polynomial-time, assuming a
generalisation of the Riemann hypothesis is true.
Property 4 of Theorem
9.11.2
implies that if
E
is a supersingular curve then
π
q
=
[
p
M
]
. In other words,
π
q
∈ Z
. In examples we have seen
π
2
for some
m,M
∈ N
=
[
−
q
]. A
natural question is how large the integer
m
can be.
Lemma 9.11.8
Let E be a supersingular elliptic curve over
F
q
and let P
(
T
)
be the
characteristic polynomial of Frobenius. Then every non-square factor of
q
P
(
T
√
q
)
divides
1
m
(
T
2
)
in
R
[
x
]
for somem
∈{
1
,
2
,
3
,
4
,
6
}
, where
m
(
x
)
is themth cyclotomic polynomial
(see Section
6.1
).
Proof
Waterhouse's theorem gives the possible values for the characte
ri
stic p
oly
nom
ial
P
(
T
)
±
√
2
q
±
√
q
,
2
√
q
,
T
2
=
−
tT
+
q
of Frobe
nius
. The possible values for
t
are 0,
±
±
√
3
q
(when
q
is a power of 3).
By part 4 of Theorem
9.11.2
, every root
α
of
P
(
T
) is such that
α/
√
q
is a root of unity.
If
P
(
T
)
(when
q
is a power of 2) or
=
−
−
(
T
α
)(
T
β
) then
α/
√
q
)(
T
β/
√
q
)
q
P
(
T
√
q
)
.
1
(
T
−
−
=
P
(
T
√
q
)
/q
So, write
Q
(
T
)
=
∈ R
[
T
]. The first three values for
t
in the above list give
Q
(
T
) equal to
T
2
1)
2
respectively. The result
clearly holds in these cases (the condition about “non-square factors” is needed since
(
T
1,
T
2
1 and
T
2
+
±
T
+
±
2
T
+
1
=
(
T
±
1) divides
1
(
T
2
)
1)
2
±
=
(
T
−
1)(
T
+
1), but (
T
±
does not divide any cyclotomic
polynomial.
We now deal
w
ith the remaining two cases. Let
t
2
(
m
+
1)
/
2
2
m
. Then
=±
where
q
=
±
√
2
T
T
2
Q
(
T
)
=
+
1 and we have
√
2
T
√
2
T
(
T
2
1)(
T
2
T
4
4
(
T
2
)
.
+
+
−
+
1)
=
+
1
=
±
√
3
T
3
(
m
+
1)
/
2
3
m
then
Q
(
T
)
T
2
Similarly, when
t
=±
and
q
=
=
+
1 and
√
3
T
√
3
T
(
T
2
1)(
T
2
T
4
T
2
6
(
T
2
)
.
+
+
−
+
1)
=
−
+
1
=
F
q
. Then there is an integer
Corollary 9.11.9
Let E be a supersingular elliptic curve over
∈{
}
such that π
q
∈ Z
F
q
)
divides
(
q
m
−
m
1
,
2
,
3
,
4
,
6
and the exponent of the group E
(
1)
.
Furthermore, the cases m
=
3
,
4
,
6
only occur when q is a square, a power of
2
, or a power
of
3
respectively.
Exercise 9.11.10
Prove Corollary
9.11.9
.
In general, the endomorphism ring of a supersingular elliptic curve is generated over
Z
by the Frobenius map and some “complex multiplication” isogeny. However, as seen
in Example
9.10.12
, the Frobenius can lie in
, in which case two independent “complex
multiplications” are needed (though, as in Example
9.10.12
, one of them will be very
closely related to a Frobenius map on a related elliptic curve).
Z
