Discrete Logarithm in $\mathbb{F}_p$: Shank's Baby-Step Giant-Step
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$.
- Let $n = 1 + \left\lfloor\sqrt{N}\right\rfloor$.
- 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}$
- Check for values that satisfy $g^i \equiv_N hg^{-jn}$.
- 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.