<<

. 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 [63], 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[5] ⊆ 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)