<< стр. 2(всего 2)СОДЕРЖАНИЕ
(a) Fix an integer m в‰Ґ N .
(b) Compute and store a list of the x-coordinates of iP for 0 в‰¤ i в‰¤ m/2.
(c) Compute the points Q в€’ jmP for j = 0, 1, 2, В· В· В· , m в€’ 1 until the
x-coordinate of one of them matches an element from the stored
list.
(d) Decide whether Q в€’ jmP = iP or = в€’iP .
(e) If В±iP = Q в€’ jmP , we have Q = kP with k в‰Ў В±i + jm (mod N ).
This requires a little less computation and half as much storage as the
baby step, giant step algorithm in the text. It is essentially the same as
the method used in Section 4.3.4 to п¬Ѓnd the order of E(Fq ).
5.2 Let G be the additive group Zn . Explain why the discrete logarithm
problem for G means solving ka в‰Ў b (mod n) for k and describe how
this can be solved quickly. This shows that the diп¬ѓculty of a discrete
logarithm problem depends on the group.
5.3 Let E be the elliptic curve y 2 = x3 + 3 over F7 .
(a) Show that 4(1, 2) = (4, 5) on E.

В© 2008 by Taylor & Francis Group, LLC
167
EXERCISES

(b) Show that the method of the proof of Proposition 5.6, with P = (1, 2)
Лњ Лњ
and Q = (4, 5), produces the points P = (1, 2) and Q = (4, 5) on
E : y 2 = x3 в€’ 14x + 17 (which is deп¬Ѓned over Q).
Лњ
Лњ
(c) Show that 2(1, 2) = (1, в€’2) and 3(1, 2) = в€ћ on E mod 73.
Лњ
(d) Show that there is no integer k such that k(1, 2) = (4, 5) on E.
This shows that lifting a discrete log problem mod p to one on an elliptic
curve over Q does not necessarily yield a discrete log problem that has
a solution.

5.4 Let G be a group and let p be a prime. Suppose we have a fast algorithm
for solving the discrete log problem for elements of order p (that is,
given g в€€ G of order p and h = g k , there is a fast way to п¬Ѓnd k). Show
that there is a fast algorithm for solving the discrete log problem for
elements of order a power of p. (This is essentially what the Pohlig-
Hellman method does. Since Pohlig-Hellman works with small primes,
the fast algorithm for elements of order p in this case is simply brute
force search.)

5.5 Let p в‰Ґ 7 be prime. Show that if E is an elliptic curve over Fp such
that E(Fp ) contains a point of order p, then #E(Fp ) = p.

5.6 Show that if E is anomalous over Fq then it is not anomalous over Fq2 .

5.7 Show that if E is anomalous over F2 then it is anomalous over F16 .

5.8 Suppose E is anomalous over F2 , so П†2 в€’ П†2 + 2 = 0. Show that
2

(a) 4 = в€’П†3 в€’ П†2
2 2

(b) 8 = в€’П†3 + П†5
2 2

(c) 16 = П†4 в€’ П†8
2 2

These equations were discovered by Koblitz , who pointed out that
multiplication by each of 2, 4, 8, 16 in E(Q) can be accomplished by
applying suitable powers of П†2 (this is п¬Ѓnite п¬Ѓeld arithmetic and is fast)
and then performing only one point addition. This is faster than suc-
cessive doubling for 4, 8, and 16.

5.9 Let E be deп¬Ѓned over Fq .

(a) Show that a map from E(Fq ) to itself is injective if and only if it
is surjective.
(b) Show that if E(Fq ) has no point of order n, then E(Fq )/nE(Fq ) =
0 (in which case, the Tate-Lichtenbaum pairing is trivial).

5.10 (a) Let П€ be a homomorphism from a п¬Ѓnite group G to itself. Show
that the index of П€(G) in G equals the order of the kernel of П€.

В© 2008 by Taylor & Francis Group, LLC
168 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

(b) Let E be deп¬Ѓned over Fq and let n в‰Ґ 1. Show that E(Fq )[n] and
E(Fq )/nE(Fq ) have the same order. (When n|q в€’ 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.)

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(Fq )
(cf. Lemma 5.4). Assume is a prime such that |#E(Fq ) and |q в€’ 1,
and suppose that the -power torsion in E(Fq ) is cyclic of order i , with
i в‰Ґ 1. Let Pi have order i and let P have order .
(a) Show that П„ (P, Pi ) is a primitive th root of unity.
(b) Suppose Q = kP . Show how to use (a) to reduce the problem of
п¬Ѓnding k to a discrete logarithm problem in FГ— .
q
(c) Let N = #E(Fq ). Let R be a random point in E(Fq ). Explain
why (N/ i )R is very likely to be a point of order i . This shows
that п¬Ѓnding a suitable point Pi is not diп¬ѓcult.
5.12 Let E be deп¬Ѓned by y 2 + y = x3 + x over F2 . Exercise 4.7 showed that
#E(F2 ) = 5, so E is supersingular and П†2 + 2П†2 + 2 = 0.
2

(a) Show that П†4 = в€’4.
2
(b) Show that E вЉ† E(F16 ).
(c) Show that #E(F4 ) = 5 and #E(F16 ) = 25.
This example shows that Proposition 5.3 can fail when a = 0.

В© 2008 by Taylor & Francis Group, LLC

 << стр. 2(всего 2)СОДЕРЖАНИЕ