IndDem

Shanks Discrete Logarithm Demonstration

Solve $g^x\equiv a\pmod p$ using baby steps and giant steps

Base $g$:

Target $a$:

Modulus $p$:

Shanks’ method

We seek $i$ and $j$ such that $g^{is+j}\equiv a\pmod p$.

1. 1Find $h$ such that $gh\equiv1\pmod p$.
2. 2Construct and sort the values $ah^j\pmod p$ for $0\leq j<s$.
3. 3Search the table for successive values $g^{is}\pmod p$.
4. 4A match gives $\operatorname{ind}_g a=is+j$.