# Comparing Shanks' Algorithm to Brute Force

I'm trying to understand how/why Shanks' algorithm solves the discrete log problem $$y=g^x \bmod p$$ faster than a brute force search does. Any explanation would be great.

Shanks' algorithm—also known as baby-step, giant-step, or BSGS, and known well before Shanks (English translation)—does not solve the discrete log problem faster than a brute force search, because it is an example of a generic or brute force search algorithm. Actually it's costlier than other generic algorithms like Pollard's $$\rho$$, in the standard area*time cost metric that serves as a good proxy for number of joules or number of rubles you would have to spend on the computation.

Fix a group $$G$$ and an element $$g \in G$$ of prime order $$\ell$$. Suppose you can compute the functions $$(a, b) \mapsto a \cdot b$$, $$a \mapsto a^{-1}$$, and $$(a, b) \mapsto [a = b]$$ on elements of $$G$$; that is, you can compute the group operation and inverse, and you can test elements for equality. If $$h = g^x$$ for a uniform random exponent $$x$$, how can we find $$x$$?

This setting—where you can compute products and test equality but you know nothing else about $$G$$—is the generic setting; attacks in this setting are sometimes called generic attacks or brute force attacks. If we had specific knowledge about $$G$$, like we do when $$G = (\mathbb Z/p\mathbb Z)^\times$$ for prime $$p$$, we might have better attacks, like index calculus with the NFS. But we are in the generic setting.

Naive approach. One option is to try $$x = 0$$ and check whether $$h$$ is $$1$$, then try $$x = 1$$ and check whether $$g$$ is $$h$$, then try $$x = 2$$ and check whether $$g^2$$ gives $$h$$, then try $$x = 3$$ and check whether $$g^3$$ gives $$h$$, etc. If $$x$$ is uniformly distributed, the expected number of trials is $$\ell/2 = O(\ell)$$. To save effort in each trial, rather than computing $$g^k$$ afresh each time, we can store state $$s_k = g^k$$ and update it by $$s_{k + 1} = s_k \cdot g$$ with a single multiplication. This is the naivest approach. Can we do a better brute force attack?

Pairwise grouping. Consider grouping the trials into pairs:

• Is $$h$$ either $$1$$ or $$g$$?
• Is $$h$$ either $$g^2$$ or $$g^3$$?
• Is $$h$$ either $$g^4$$ or $$g^5$$?
• Is $$h$$ either $$g^6$$ or $$g^7$$?

If we succeed on the $$k^{\mathit{th}}$$ trial, we need only determine whether $$x = 2k$$ or $$x = 2k + 1$$. The expected number of trials is $$\ell/4$$, plus a little extra work at the end. Of course, each trial costs twice as much as before, so this doesn't win anything yet.

Common criterion. Rather than compare $$h$$ to $$g^{2k}$$ and $$g^{2k + 1}$$, we can compare $$h g^{-2k}$$ to $$g^0 = 1$$ and $$g^1 = g$$, so that each trial performs the same test.

• Is $$h$$ either $$1$$ or $$g$$?
• Is $$h g^{-2}$$ either $$1$$ or $$g$$?
• Is $$h g^{-4}$$ either $$1$$ or $$g$$?
• Is $$h g^{-6}$$ either $$1$$ or $$g$$?

Once we have found $$k$$ and $$\alpha$$ so that $$h g^{-2k} = g^{x - 2k} = g^\alpha$$ and thus $$x - 2 k \equiv \alpha \pmod \ell$$, we can solve for $$x$$ as before. The expected number of trials is still $$\ell/4$$, but we can precompute $$g^{-2}$$, and then keep a running state $$s_k = h g^{-2k}$$ which we can update to $$s_{k + 1} = s_k \cdot g^{-2}$$ by a single multiplication. The expected number of trials is about half the naive algorithm, and the number of multiplications per trial is the same, so the expected number of multiplications is $$\ell/4$$, half that for the naive algorithm. Of course, we have to do two equality comparisons for each trial, but an equality comparison is probably cheaper than a multiplication.

Wider grouping. If a table lookup had the same cost as an equality comparison, we could make a table of $$m$$ different entries by precomputing $$1, g, g^2, g^3, \dots, g^{m - 1}$$, precomputing $$g^{-m}$$, and then searching as before:

• Is $$h$$ in the table $$\{1, g, g^2, \dots, g^{m - 1}\}$$?
• Is $$h g^{-m}$$ in the table $$\{1, g, g^2, \dots, g^{m - 1}\}$$?
• Is $$h g^{-2m}$$ in the table $$\{1, g, g^2, \dots, g^{m - 1}\}$$?
• Is $$h g^{-3m}$$ in the table $$\{1, g, g^2, \dots, g^{m - 1}\}$$?

Once we have found $$k$$ and $$\alpha$$ so that $$h g^{-k m} = g^{x - k m} = g^\alpha$$ and thus $$x - k m \equiv \alpha \pmod \ell$$, then we can solve for $$x$$ as before. Also as before, we can update the state $$s_k = h g^{-km}$$ with one multiplication $$s_{k + 1} = s_k \cdot g^{-m}$$. The expected number of trials is $$\ell/(2m)$$ and the cost of each trial is (a) one multiplication and (b) one table lookup. Thus the expected number of multiplications and table operations is $$O(m + \ell/m)$$, which is optimized by $$m = \sqrt\ell$$.

Caveat. In real computers, storing tables costs energy and table lookups cost more time and energy than equality comparisons. So BSGS's apparent ‘cost’ of $$O(\sqrt\ell)$$ multiplications, which seems to be an improvement on the naive algorithm's $$O(\ell)$$, is misleading in practical terms because it uses an unrealistic cost model where storage is free and an equality test costs the same as a table lookup. Pollard's $$\rho$$ is a generic brute force algorithm that actually improves the cost in realistic cost models to $$O(\sqrt\ell)$$: it too runs in $$O(\sqrt\ell)$$ computation time, but it has constant space requirements and no table lookups, and as a bonus it can be parallelized to take advantage of extra die area to speed it up without changing the net cost.