Cryptography Reference
In-Depth Information
Theorem 9.11.2
Let E be an elliptic curve over
F
p
m
where p is prime. The following are
equivalent:
p
m
1.
#
E
(
F
p
m
)
=
+
1
−
t where p
|
t;
={
O
E
}
2. E
[
p
]
;
3.
End
F
p
(
E
)
is not commutative (hence, by Theorem
9.9.1
, it is an order in a quaternion
algebra);
4. The characteristic polynom
ial
of Frobenius P
(
T
)
with
roots α
1
,α
2
such that α
i
/
√
p
m
are roots of unity. (Recall that a root of unity is a complex
number z such that there is some n
=
T
2
−
tT
+
p
m
factors over
C
with z
n
∈ N
=
1
.)
Proof
The equivalence of Properties 1, 2 and 3 is shown in Theorem 3.1 of Silverman [
505
].
Property 4 is shown in Proposition 13.6.2 of Husemoller [
272
].
Definition 9.11.3
An elliptic curve
E
over
F
p
m
is
supersingular
if it satisfies any of the
conditions of Theorem
9.11.2
. An elliptic curve is
ordinary
if it does not satisfy any of the
conditions of Theorem
9.11.2
.
We stress that a supersingular curve is not singular as a curve.
2(mod3) be prime and let
a
6
∈ F
p
. The elliptic curve
E
:
Example 9.11.4
Let
p
≡
y
2
x
3
1 points. Another way
to show supersingularity for this curve is to use the endomorphism
ρ
(
x,y
)
=
+
a
6
is supersingular since, by Exercise
9.10.4
, it has
p
+
=
(
ζ
3
x,y
)
as in Exercise
9.6.25
(where
ζ
3
∈ F
p
2
is such that
ζ
3
+
ζ
3
+
1
=
0). Since
ρ
does not
ρ
2
π
p
since
ζ
3
∈ F
p
)
commute with the
p
-power Frobenius map
π
p
(specifically,
π
p
ρ
=
the endomorphism ring is not commutative.
To determine the quaternion algebra, one can proceed as follows. First, show that
ρ
sa
tisfies the characteristic polynomial
T
2
+
+
=
0 (since
ρ
3
(
P
)
=
∈
T
1
P
for all
P
ρ
, which has dual
φ
E
(
F
p
)). Then consider the isogeny
φ
=
[1]
−
=
[1]
−
ρ
2
. The degree
φφ
d
of
φ
satisfies [
d
]
=
=
(1
−
ρ
)(1
−
ρ
2
)
=
1
−
ρ
−
ρ
2
+
1
=
3. Hence,
φ
has degree
3. The trace of
φ
is
t
=
1
+
deg(
φ
)
−
deg(1
−
φ
)
=
1
+
3
−
deg(
ρ
)
=
3. One can show
that (
ρφ
)
2
[
i,j
] with
i
2
3 and
j
2
=
[
−
3] and so the quaternion algebra is
Q
=−
=−
p
.
3(mod4)beprimeand
a
4
∈ F
p
.Exercise
9.10.5
implies that
Example 9.11.5
Let
p
≡
E
:
y
2
x
3
a
4
x
is supersingular. An alternative proof of supersingularity follows from
Example
9.9.2
; since
ξ
(
x,y
)
=
+
=
(
−
x,iy
) does not commute with the
p
-power Frobenius.
F
q
be a finite field of characteristic 2 and
F
(
x
)
∈ k
Example 9.11.6
Let
[
x
] a monic
polynomial of degree 3. Then
E
:
y
2
+
=
y
F
(
x
) is supersingular. This follows from the
fact that (
x,y
)
∈
E
(
F
q
n
) if and only if (
x,y
+
1)
∈
E
(
F
q
n
) and hence #
E
(
F
q
n
) is odd for
all
n
. It follows that there are no points of order 2 on
E
(
F
2
) and so
E
is supersingular.
Exercise 9.11.7
Use Waterhouse's theorem to show that, for every prime
p
and
m
∈ N
,
there exists a supersingular curve over
F
p
m
.
