(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