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