Cryptography Reference
In-Depth Information
It remains to express
A
p
as a polynomial in
λ
. The coe
cient
A
p
of
x
p−
1
in (
x
(
x
λ
))
(
p−
1)
/
2
is the coe
cient of
x
(
p−
1)
/
2
in
−
1)(
x
−
((
x −
1)(
x − λ
))
(
p−
1)
/
2
.
By the binomial theorem,
(
p
x
i
(
−
1)
(
p−
1)
/
2
−i
(
x −
1)
(
p−
1)
/
2
=
i
−
1)
/
2
i
(
p
x
(
p−
1)
/
2
−j
(
−λ
)
j
.
(
x − λ
)
(
p−
1)
/
2
=
j
−
1)
/
2
j
The coe
cient
A
p
of
x
(
p−
1)
/
2
in (
x −
1)
(
p−
1)
/
2
(
x − λ
)
(
p−
1)
/
2
is
(
p −
1)
/
2
k
2
(
p
−
1)
/
2
1)
(
p−
1)
/
2
λ
k
=(
1)
(
p−
1)
/
2
H
p
(
λ
)
.
(
−
−
k
=0
Therefore,
E
is supersingular if and only if
H
p
(
λ
) = 0. This completes the
proof of Theorem 4.34.
It is possible to use the method of the preceding proof to determine when
certain curves are supersingular.
PROPOSITION 4.37
Let
p ≥
5
be prime.Thenthe ellipticcurve
y
2
=
x
3
+1
over
F
p
is supersin-
gular ifand onlyif
p ≡
2(mod3)
,and the ellipticcurve
y
2
=
x
3
+
x
over
F
p
is supersingular ifand onlyif
p ≡
3(mod4)
.
The coecient of
x
p−
1
in (
x
3
+1)
(
p−
1)
/
2
PROOF
is 0 if
p ≡
2(mod3)
(since we only get exponents that are multiples of 3), and is
(
p−
1)
/
2
(
p
1)
/
3
≡
0(mod
p
)when
p ≡
1 (mod 3) (since the binomial coecient contains no
factors of
p
). Since the coecient of
x
p−
1
is zero mod
p
if and only if the
curve is supersingular, this proves the first part.
The coe
cient of
x
p−
1
−
in (
x
3
+
x
)
(
p−
1)
/
2
is the coe
cient of
x
(
p−
1)
/
2
in
(
x
2
+1)
(
p−
1)
/
2
.
All exponents appearing in this last expression are even,
so
x
(
p−
1)
/
2
doesn't appear when
p
≡
3(mod4). When
p
≡
1(mod4),
the coe
cient is
(
p−
1)
/
2
1)
/
4
≡
0(mod
p
). This proves the second part of the
(
p
−
proposition.
If
E
is an elliptic curve defined over
Z
with complex multiplication (see
Chapter 10) by a subring of
Q
(
√
−d
), and
p
is an odd prime number not
dividing
d
for which
E
(mod
p
) is an elliptic curve, then
E
(mod
p
)issuper-
singular if and only if
−d
is not a square mod
p
. Therefore, for such an
E
,
Search WWH ::
Custom Search