Cryptography Reference
In-Depth Information
It is known that the endomorphism ring End
(
E
) of a supersingular elliptic curve
E
over
k
k
is a
maximal order
in a quaternion algebra (see Theorem 4.2 of Waterhouse [
561
]) and
that the q
ua
ternion algebra is ramified at exactly
p
and
∞
. Indeed, [
561
] shows that when
2
√
q
then all endomorphisms are defined over
t
=±
F
q
and every maximal order arises. In
other cases not all endomorphisms are defined over
F
q
and the maximal order is an order
that contains
π
q
and is maximal at
p
(i.e., the index is not divisible by
p
).
We now present some results on the number of supersingular curves over finite fields.
Theorem 9.11.11
Let
F
q
be a field of characteristic p and E/
F
q
a supersingular elliptic
curve. Then j
(
E
)
∈ F
p
2
. Furthermore:
1. The number of
F
q
-isomorphism classes of supersingular elliptic curves over
F
p
2
is
1
if p
=
2
,
3
and
p/
12
+
p
where
p
=
0
,
1
,
1
,
2
respectively if p
≡
1
,
5
,
7
,
11 (mo
d 1
2)
.
2. The number of
F
q
-isomorphism classes of supersingular elliptic curves over
F
p
is
1
if
p
=
2
,
3
and is equal to the Hurwitz class number H
(
−
4
p
)
if p>
3
. Furthermore
1
2
h
(
−
4
p
)
if p
≡
1(mod4)
,
H
(
−
4
p
)
=
−
≡
h
(
p
)
if p
7(mod8)
,
2
h
(
−
p
)
if p
≡
3(mod8)
(
√
d
)
.
where h
(
d
)
is the usual ideal class number of the quadratic field
Q
Proof
The claim that
j
(
E
)
∈ F
p
2
is Theorem 3.1(iii) of [
505
] or Theorem 5.6 of [
272
]. The
formula for the number of supersingular
j
-invariants in
F
p
2
is Theorem 4.1(c) of [
505
]or
Section 13.4 of [
272
]. The statement about the number of supersingular
j
-invariants in
F
p
is given in Theorem 14.18 of Cox [
145
] (the supersingular case is handled on page 322).
The precise formula for
H
(
4
p
) is equation (1.11) of Gross [
244
]. (Gross also explains
the relation between isomorphism classes of supersingular curves and Brandt matrices.)
−
Lemma 9.11.12
Let E
1
,E
2
be elliptic curves over
F
q
. Show that if E
1
andE
2
are ordinary,
#
E
1
(
F
q
)
=
#
E
2
(
F
q
)
and j
(
E
1
)
=
j
(
E
2
)
then they are isomorphic over
F
q
.
Proof
(Sketch) Since
j
(
E
1
)
=
j
(
E
2
) the curves are isomorphic over
F
q
.If#
E
1
(
F
q
)
=
q
+
1
−
t
and
E
2
is not isomorphic to
E
1
over
F
q
, then
E
2
is a non-trivial twist of
E
1
.If
j
(
E
1
)
=
0
,
1728 then #
E
2
(
F
q
)
=
q
+
1
+
t
=
#
E
1
(
F
q
), since
t
=
0 (this is where we use
the fact that
E
1
is ordinary). In the cases
j
(
E
1
)
0
,
1728, one needs to use the formulae of
Example
9.10.20
and Exercise
9.10.22
and show that these group orders are distinct when
t
=
0.
An alternative proof, using less elementary methods, is given in Proposition 14.19
(page 321) of Cox [
145
].
=
Exercise 9.11.13
Give an example of supersingular curves
E
1
,E
2
over
F
p
such that
j
(
E
1
)
=
j
(
E
2
), #
E
1
(
F
p
)
=
#
E
2
(
F
p
) and
E
1
is not isomorphic to
E
2
over
F
p
.