The Discrete Logarithm Problem - Elliptic Curves: Number Theory and Cryptography - page 166

(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 = x 3

14 x + 17 (which is defined over Q ).
(c) Show that 2(1 , 2) = (1 ,

−

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.

− 2) and 3(1 , 2) = ∞

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 find 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 F p such

that E ( F p ) contains a point of order p ,then# E ( F p )= p .

≥

5.6 Show that if E is anomalous over F q then it is not anomalous over F q 2 .

5.7 Show that if E is anomalous over F 2 then it is anomalous over F 16 .

5.8 Suppose E is anomalous over F 2 ,so φ 2 − φ 2 + 2 = 0. Show that

(a) 4 = −φ 2 − φ 2
(b) 8 = −φ 2 + φ 2
(c) 16 = φ 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 finite field 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 defined over F q .

(a) Show that a map from E ( F q ) to itself is injective if and only if it
is surjective.

(b) Show that if E ( F q )hasnopointoforder n ,then E ( F q ) /nE ( F q )=
0 (in which case, the Tate-Lichtenbaum pairing is trivial).

5.10 (a) Let ψ be a homomorphism from a finite group G to itself. Show

that the index of ψ ( G )in G equals the order of the kernel of ψ .