Discrete Logarithm in $\mathbb{F}_p$: Shank's Baby-Step Giant-Step

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.