Let $a$, $b$ and $x$ be positive real numbers such that

$$a^x = b$$

And we want to find the value of $x$, applying logarithms

$$x \cdot log(a) = log(b)$$

Finally

$$x = \frac{log(b)}{log(a)}$$

The discrete logarithm problem is an analogue of this problem with the condition that all the numbers exist in the ring of integers modulo $n$

Let $a$, $b$ and $n$ be integers, where $a$ and $n$ are coprime, find the value of $x$ in

$$a^x \equiv b \pmod{n}$$

## Trial multiplication

The brute force algorithm consists in computing all possible $a^i \pmod{n}$, where $i \geq 0 < n$ until one matches $b$

Example: given $n = 11$, $a = 2$, $b = 9$ find the value of $x$ in $a^x \equiv b \pmod{n}$

\begin{align*} a^0 &\equiv 1 \pmod{11} \\ a^1 &\equiv 2 \pmod{11} \\ a^2 &\equiv 4 \pmod{11} \\ a^3 &\equiv 8 \pmod{11} \\ a^4 &\equiv 16 \equiv 5 \pmod{11} \\ a^5 &\equiv 32 \equiv 10 \pmod{11} \\ a^6 &\equiv 64 \equiv 9 \pmod{11} \end{align*}

$x = 6$ is a solution to the problem

## Baby Step Giant Step

The idea of Shank’s baby step giant step algorithm is based on rewriting $x$ in the congruence above as $x = im + j$ where $m = \sqrt{n}$, $0 \leq i < m$ and $0 \leq j < m$ so

$$a^{im + j} \equiv b \pmod{n}$$

multiplying both sides by $a^{-im}$ (note that this is possible because $a$ and $n$ are coprime)

$$a^j \equiv b(a^{-m})^i \pmod{n}$$

If we find $i$ and $j$ so that this holds then we have found an exponent $x$

Note: $a^{-m}$ can be computed using the modular multiplicative inverse of $a$, then computing the $m$-th power of the inverse $\pmod{n}$

/**
* Let a, b and n be **integers**, where a and n are coprime,
* the following is an implementation of Shank's baby step giant step
* algorithm which attempts to find a solution for the congruence
*
*    a^x ≡ b (mod n)
*
* x can be represented as im + j then
*
*   a^j ≡ b(a^{-m})^i (mod n)
*
* NOTE: binary_exponentiation_modulo_m is a function which computes
*
*    a^x (mod n)
*
* @param {int} a
* @param {int} b
* @param {int} n
* @returns {int} An integer >= 0 which is the value of x, -1
* if no value was found
*/
int baby_step_giant_step(int a, int b, int n) {
int m = ceil(sqrt(n));

// values in the left side
map<int, int> M;

// store all possible a^j
int aj = 1;
for (int j = 0; j < m; j += 1) {
if (!M.count(aj)) {
M[aj] = j;
}
aj = (aj * a) % n;
}

// compute b(a^{-m})^i
// first compute the modular multiplicative inverse of a
int inverse;
if (!modular_multiplicative_inverse(a, n, inverse)) {
return -1;
}
int coef = binary_exponentiation_modulo_m(inverse, m, n);

// NOTE: the modular multiplicative inverse can also be computed
// using Euler's theorem only if n is prime
// - first compute a^-1 with the identity a^-1 ≡ a^{n - 2} (mod n)
// - compute inverse^m % n
//
// int coef = binary_exponentiation_modulo_m(a, n - 2, n);
// coef = binary_exponentiation_modulo_m(coef, m, n);

int gamma = b;
for (int i = 0; i < m; i += 1) {
if (M.count(gamma)) {
return i * m + M[gamma];
}
gamma = (gamma * coef) % n;
}
return -1;
}