Cryptography Reference
In-Depth Information
2
√
m
.
Therefore, if
m
is fixed,
q
occurs as the value of one of finitely many
quadratic polynomials.
(b) Use Hasse's theorem in the form
a
2
≤
4
q
to show that
|
k
|≤
(c) The prime number theorem implies that the number of prime pow-
ers less than
x
is approximately
x/
ln
x
. Use this to show that most
prime powers do not occur as values of the finite list of polynomials
in (b).
(d) Use Hasse's theorem to show that
mn ≥
√
m
(
√
q −
1).
(e) Show that if
m
≥
17 and
q
is su
ciently large (
q
≥
1122 su
ces),
then
E
(
F
q
) has a point of order greater than 4
√
q
.
(f) Show that for most value
s
of
q
, an elliptic curve over
F
q
has a point
of order greater than 4
√
q
.
(a) Let
E
be defined by
y
2
+
y
=
x
3
+
x
over
F
2
. Show that #
E
(
F
2
)=
5.
(b) Let
E
be defined by
y
2
=
x
3
4.7
x
+2 over
F
3
. Show that #
E
(
F
3
)=1.
(c) Show that the curves in (a) and (b) are supersingular, but that, in
each case,
a
=
p
+1
−
−
#
E
(
F
p
)
= 0. This shows that the restriction
to
p
≥
5 is needed in Corollary 4.32.
4.8 Let
p
5 be prime. Use Theorem 4.23 to prove Hasse's theorem for the
elliptic curve given by
y
2
=
x
3
≥
−
kx
over
F
p
.
4.9 Let
E
be a
n
elliptic curve over
F
q
with
q
=
p
2
m
. Suppose that #
E
(
F
q
)=
q
+1
2
√
q
.
−
p
m
)
2
=0.
(a) Let
φ
q
be the Frobenius endomorphism. Show that (
φ
q
−
(b) Show that
φ
q
− p
m
=0(
Hint:
Theorem 2.22).
(c) Show that
φ
q
acts as the identity on
E
[
p
m
−
1], and therefore that
E
[
p
m
E
(
F
q
).
(d) Show that
E
(
F
q
)
Z
p
m
−
1
⊕
Z
p
m
−
1
.
−
1]
⊆
4.10 Let
E
be an elliptic curve over
F
q
with
q
odd. Write #
E
(
F
q
)=
q
+1
−a
.
Let
d ∈
F
q
and let
E
(
d
)
be the twist of
E
, as in Exercise 2.23. Show
that
d
F
q
a.
#
E
(
d
)
(
F
q
)=
q
+1
−
(
Hint:
Use Exercise 2.23(c) and Theorem 4.14.)
4.11 Let
F
q
be a finite field of odd characteristic and let
a, b
∈
F
q
with
a
=
±
2
b
and
b
= 0. Define the elliptic curve
E
by
y
2
=
x
3
+
ax
2
+
b
2
x.
Search WWH ::
Custom Search