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