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

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

Finally

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

Trial multiplication

The brute force algorithm consists in computing all possible $a^i(\mathrm{mod}n)$, where $i\ge 0<n$ until one matches $b$

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

$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\le i<m$ and $0\le j<m$ so

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

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 $(\mathrm{mod}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;
}