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;
}