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

Note that the index calculus depends heavily on the fact that integers can
be written as products of primes. An analogue of this is not available for
arbitrary groups.
There is a generalization of the index calculus that works for finite fields,
but it requires some algebraic number theory, so we do not discuss it here.
In Section 13.4, we show how an analogue of the index calculus can be
applied to groups arising from hyperelliptic curves.

5.2 General Attacks on Discrete Logs

In this section, we discuss attacks that work for arbitrary groups. Since our
main focus is elliptic curves, we write our group G additively. Therefore, we
are given P, Q ∈ G andwearetryingtosolve kP = Q (we always assume
that k exists). Let N be the order of G . Usually, we assume N is known. For
simplicity, it is usually assumed that P generates G .

5.2.1 Baby Step, Giant Step
This method, dev elo ped by D. Shanks [107], requires approximately √ N

steps and around √ N storage. Therefore it only works well for moderate
sized N . The procedure is as follows.

≥ √ N and compute mP . 1. Fix an integer m

2. Make and store a list of iP for 0 ≤ i<m .

3. Compute the points Q − jmP for j =0 , 1 , ··· m − 1 until one matches

an element from the stored list.

4. If iP = Q − jmP ,wehave Q = kP with k ≡ i + jm (mod N ).

Why does this work? Since m 2 >N ,wemayassumetheanswer k satisfies
0 ≤ k<m 2 .Write k = k 0 + mk 1 with k 0 ≡ k (mod m )and0 ≤ k 0 <m and
let k 1 =( k − k 0 ) /m .Then0 ≤ k 1 <m .When i = k 0 and j = k 1 ,wehave

Q − k 1 mP = kP − k 1 mP = k 0 P,

so there is a match.
The point iP is calculated by adding P (a “ baby step ”) to ( i − 1) P .The
point Q − jmP is computed by adding −mP (a “ giant step ”) to Q − ( j −
1) mP . The method was developed by Shanks for computations in algebraic
number theory.