math/ModLog.h

• View this file on GitHub
• Last update: 2025-11-18 17:42:34+07:00

Verified with

• tests/Discrete_Logarithm.test.cpp

Code

i64 modLog(i64 a, i64 b, i64 m) {
  i64 n = (i64) sqrt(m) + 1, e = 1, f = 1, j = 1;
  unordered_map<i64, i64> A;
  while (j <= n && (e = f = e * a % m) != b % m) A[e * b % m] = j++;
  if (e == b % m) return j;
  if (gcd(m, e) == gcd(m, b)) {
    for (int i = 2; i < n + 2; ++i) {
      if (A.count(e = e * f % m)) return n * i - A[e];
    }
  }
  return -1;
}

#line 1 "math/ModLog.h"
i64 modLog(i64 a, i64 b, i64 m) {
  i64 n = (i64) sqrt(m) + 1, e = 1, f = 1, j = 1;
  unordered_map<i64, i64> A;
  while (j <= n && (e = f = e * a % m) != b % m) A[e * b % m] = j++;
  if (e == b % m) return j;
  if (gcd(m, e) == gcd(m, b)) {
    for (int i = 2; i < n + 2; ++i) {
      if (A.count(e = e * f % m)) return n * i - A[e];
    }
  }
  return -1;
}

Back to top page