Cryptography Reference
In-Depth Information
(b) Let
E
be defined over
F
q
and let
n
1. Show that
E
(
F
q
)[
n
]and
E
(
F
q
)
/nE
(
F
q
) have the same order. (When
n
≥
1, this can be
proved from the nondegeneracy of the Tate-Lichtenbaum pairing;
see Lemma 11.28. The point of the present exercise is to prove it
without using this fact.)
|
q
−
5.11 This exercise gives a way to attack discrete logarithms using the Tate-
Lichtenbaum pairing, even when there is a point of order
2
in
E
(
F
q
)
(cf. Lemma 5.4). Assume
is a prime such that
|
#
E
(
F
q
)and
|q −
1,
and suppose that the
-power torsion in
E
(
F
q
) is cyclic of order
i
,with
i ≥
1. Let
P
i
have order
i
and let
P
have order
.
(a) Show that
τ
(
P, P
i
) is a primitive
th root of unity.
(b) Suppose
Q
=
kP
. Show how to use (a) to reduce the problem of
finding
k
to a discrete logarithm problem in
F
q
.
(c) Let
N
=#
E
(
F
q
). Let
R
be a random point in
E
(
F
q
). Explain
why (
N/
i
)
R
is very likely to be a point of order
i
. This shows
that finding a suitable point
P
i
is not dicult.
5.12 Let
E
be defined by
y
2
+
y
=
x
3
+
x
over
F
2
. Exercise 4.7 showed that
#
E
(
F
2
)=5,so
E
is supersingular and
φ
2
+2
φ
2
+2=0.
(a) Show that
φ
2
=
−
4.
(b) Show that
E
[5]
E
(
F
16
).
(c) Show that #
E
(
F
4
)=5and#
E
(
F
16
) = 25.
⊆
This example shows that Proposition 5.3 can fail when
a
=0.
Search WWH ::
Custom Search