数学/離散対数問題
(test/math/mod_log.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://judge.yosupo.jp/problem/discrete_logarithm_mod

Depends on

• 離散対数問題 (discrete logarithm problem) (include/emthrm/math/mod_log.hpp)
• 繰り返し二乗法 / 二分累乗法 / バイナリ法 (include/emthrm/math/mod_pow.hpp)

Code

/*
 * @title 数学/離散対数問題
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/discrete_logarithm_mod
 */

#include <iostream>

#include "emthrm/math/mod_log.hpp"

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int x, y, m;
    std::cin >> x >> y >> m;
    std::cout << emthrm::mod_log(x, y, m) << '\n';
  }
  return 0;
}

#line 1 "test/math/mod_log.test.cpp"
/*
 * @title 数学/離散対数問題
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/discrete_logarithm_mod
 */

#include <iostream>

#line 1 "include/emthrm/math/mod_log.hpp"



#include <map>

#line 1 "include/emthrm/math/mod_pow.hpp"



namespace emthrm {

long long mod_pow(long long x, long long n, const int m) {
  if ((x %= m) < 0) x += m;
  long long res = 1;
  for (; n > 0; n >>= 1) {
    if (n & 1) res = (res * x) % m;
    x = (x * x) % m;
  }
  return res;
}

}  // namespace emthrm


#line 7 "include/emthrm/math/mod_log.hpp"

namespace emthrm {

int mod_log(long long g, long long y, const int m) {
  if (m == 1) [[unlikely]] return 0;
  if ((g %= m) < 0) g += m;
  if ((y %= m) < 0) y += m;
  if (g == 0) [[unlikely]] {
    if (y == 1) return 0;
    if (y == 0) return 1;
    return -1;
  }
  int root = 1;
  while (root * root < m) ++root;
  std::map<long long, int> baby;
  long long p = 1;
  for (int i = 0; i < root; ++i) {
    if (p == y) return i;
    baby[p * y % m] = i;
    p = (p * g) % m;
  }
  long long brute_force = p;
  for (int i = root; i < 100; ++i) {
    if (i == m) return -1;
    if (brute_force == y) return i;
    brute_force = (brute_force * g) % m;
  }
  long long giant = p;
  for (int i = 1; i <= root; ++i) {
    if (const auto it = baby.find(giant); it != baby.end()) {
      const int ans = static_cast<long long>(i) * root - it->second;
      if (mod_pow(g, ans, m) == y) return ans;
    }
    giant = (giant * p) % m;
  }
  return -1;
}

}  // namespace emthrm


#line 10 "test/math/mod_log.test.cpp"

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int x, y, m;
    std::cin >> x >> y >> m;
    std::cout << emthrm::mod_log(x, y, m) << '\n';
  }
  return 0;
}

Back to top page