Comparing Shanks' Algorithm to Brute Force

Question

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.

Answer 1

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.