Motivation§

Given the DLP, $g^x \equiv_p h$, we can inspect the case when $\text{ord}_p(g) = q$ where $q \in \mathbb{P}$.

The Algorithm§

Shank’s Baby-Step Giant-Step Algorithm

Let $g \in \left(\mathbb{Z}_p\right)^\times$ be an element such that $N = \text{ord}_p(g) \geq 2$.

  1. Let $n = 1 + \left\lfloor\sqrt{N}\right\rfloor$.
  2. Create two lists, where all elements are in $\mathbb{Z}_N$.
    • List 1: $1, g, g^2, g^3, \dots, g^n$
    • List 2: $h, hg^{-n}, hg^{-2n}, \dots, hg^{-n^2}$
  3. Check for values that satisfy $g^i \equiv_N hg^{-jn}$.
  4. The value $x = i + jn$ is a sol’n to $g^x \equiv_p h$.

Shank’s runs in $\mathcal{O}\left(n\log n\right)$ time[^1] and in $\mathcal{O}\left(\sqrt{n}\right)$ space.