離散対数問題 (discrete logarithm problem)
(include/emthrm/math/mod_log.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/math/mod_log.hpp"

$g^x \equiv y \pmod{p}$ ($g = \text{const.},\ y \in \mathbb{Z},\ p \in \mathbb{P}$) を満たす $x$ を求める問題である。

時間計算量

$O(\sqrt{P} \log{P})$

仕様

baby-step giant-step

名前	戻り値
int mod_log(long long g, long long y, const int m);	$g^x \equiv y \pmod{m}$ を満たす最小の非負整数 $x$。ただし存在しないときは $-1$ を返す。

参考文献

• Daniel Shanks: Class number, a theory of factorization, and genera, Proceedings of Symposia in Pure Mathematics, Vol. 20, pp. 415–440 (1969).
• http://sonickun.hatenablog.com/entry/2016/11/20/192743

TODO

• 一般化
  • https://maspypy.com/%e3%83%a2%e3%83%8e%e3%82%a4%e3%83%89%e4%bd%9c%e7%94%a8%e3%81%ab%e9%96%a2%e3%81%99%e3%82%8b%e9%9b%a2%e6%95%a3%e5%af%be%e6%95%b0%e5%95%8f%e9%a1%8c
  • https://twitter.com/kotatsugame_t/status/1640549382658605056
• Pohlig–Hellman algorithm
  • http://sonickun.hatenablog.com/entry/2016/11/20/192743
  • https://yukicoder.me/problems/no/950
  • https://twitter.com/nuo_chocorusk/status/1205509988912783360
  • https://twitter.com/maspy_stars/status/1205499459993362432

Submissons

https://judge.yosupo.jp/submission/3457

Depends on

• 繰り返し二乗法 / 二分累乗法 / バイナリ法 (include/emthrm/math/mod_pow.hpp)

Verified with

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

Code

#ifndef EMTHRM_MATH_MOD_LOG_HPP_
#define EMTHRM_MATH_MOD_LOG_HPP_

#include <map>

#include "emthrm/math/mod_pow.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

#endif  // EMTHRM_MATH_MOD_LOG_HPP_

#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

Back to top page