Cryptography Reference
In-Depth Information
For the last part of the proposition, note that
#
E
(
F
q
)
≡ q
+1
− a ≡
1
− a
(mod
p
)
,
so #
E
(
F
q
)
≡
1(mod
p
) if and only if
a
≡
0(mod
p
).
COROLLARY 4.32
Suppose
p
5
isaprimeand
E
is defined over
F
p
.Then
E
is supersingular
ifand onlyif
a
=0
,which isthe case ifand onlyif
#
E
(
F
p
)=
p
+1
.
≥
PROOF
If
a
=0,then
E
is supersingular, by the proposition. Conversely,
suppose
E
is supersingular but
a
=0. Then
a
≡
0(mod
p
)
implies that
2
√
p
,sowehave
p
2
√
p
. This means
|
a
|≥
p
. By Hasse's theorem,
|
a
|≤
≤
that
p
≤
4.
When
p
=2or
p
= 3, there are examples of supersingular curves with
a
= 0. See Exercise 4.7.
For general finite fields
F
q
,itcanbeshownthatif
E
defined over
F
q
is
supersingular, then
a
2
is one of 0
,q,
2
q,
3
q,
4
q
. See [98], [80], or Theorem 4.3.
In Section 3.1, we saw that the elliptic curve
y
2
+
a
3
y
=
x
3
+
a
4
x
+
a
6
in characteristic 2 is supersingular. Also, in characteristic 3, the curve
y
2
=
x
3
+
a
2
x
2
+
a
4
x
+
a
6
is supersingular if and only if
a
2
=0. Hereisawayto
construct supersingular curves in many other characteristics.
PROPOSITION 4.33
Suppose
q
is odd and
q ≡
2(mod3)
.Let
B ∈
F
q
.Thenthe ellipticcurve
E
given by
y
2
=
x
3
+
B
is supersingular.
PROOF
Let
ψ
:
F
q
→
F
q
be the homomorphism defined by
ψ
(
x
)=
x
3
.
Since
q −
1 is not a multiple of 3, there are no elements of order 3 in
F
q
,so
the kernel of
ψ
is trivial. Therefore,
ψ
is injective, hence must be surjective
since it is a map from a finite group to itself. In particular, every element of
F
q
has a unique cube root in
F
q
.
For each
y
F
q
such that (
x, y
) lies on the
curve, namely,
x
is the unique cube root of
y
2
∈
F
q
, there is exactly one
x
∈
−
B
. Since there are
q
values
of
y
,weobtain
q
points. Including the point
∞
yields
#
E
(
F
q
)=
q
+1
.
Therefore,
E
is supersingular.
Later (Theorem 4.34), we'll see how to obtain all supersingular elliptic
curves over an algebraically closed field.
Search WWH ::
Custom Search