11.2 Shanks' Baby step-Giant step

Now suppose that we know that we are given bounds L₁, L₂, ... L_r with the assurance that there is a relation $\prod_{i}^{}$q_i^a_i with 0 $\leq$ a_i < L_i. (We will see below how such a collection of bounds can be constructed inductively given a bound L on the order of G).

Let h(x) be a collision free function for x $\in$ G (for example h is a ``hash function''). Let (a₁,..., a_r) be a sequence with a_i an integer not larger than n_i = $\lceil$$\sqrt{L_i}$$\rceil$. We compute the terms

($$\prod_{i}^{}$$g_i^a_i;a₁,..., a_r;h($$\prod_{i}^{}$$g_i^a_i))

for all a_i in this range and store them sorted according the final entry. This allows us to perform a search operation in a time proportional to the logarithm of the length of the list. Now, for each sequence (b₁,..., b_r) where b_i is an integer not larger than $\lfloor$$\sqrt{L_i}$$\rfloor$ + 1, we compute the expression h($\prod_{i}^{}$(g_i^-n_i)^b_i) and try to find it in the given sorted list. Clearly, if it is found then we have a relation of the form

$$\prod_{i}^{}$$g_i^{a_i + n_ib_i} = 1

By the given assertion on L_i, such relation will eventually be found.

One way to approach this algorithm given only a bound on the size of the group G is to go inductively. First find a relation involving g₁ alone (in other words find the order of g₁) by using L₁ = L. For the remainder of the algorithm we put L₁ = o(g₁) as found in this step. In the second iteration we work with g₁ and g₂ with L₂ = L/L₁. Iteratively, we would have computed L_i which is the order of g_i in the group G/ < g₁,..., g_{i - 1} >. We now work with g₁, ..., g_{i + 1} and take L_{i + 1} = L/($\prod_{k=1}^{i}$L_i). Using the above algorithm we obtain the order of g_{i + 1} in the group G/ < g₁,..., g_i >. For the remainder of the iterations we take L_{i + 1} to be this order. Thus, at the end we would have found a minimal relation among the g_i's rather than just one relation.