原始根 (primitive root) 判定
(include/emthrm/math/is_primitive_root.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/math/is_primitive_root.hpp"

原始根 (primitive root)

$n \in \mathbb{N}^+,\ g \in \mathbb{Z}$ に対して $\mathrm{ord}_n(g) = \varphi(n)$ が成り立つとき、$g \bmod n$ を「$n$ を法とする原始根」と呼ぶ。

$n = 2, 4, p^k, 2p^k$ ($p \in \mathbb{P} \setminus \lbrace 2 \rbrace,\ k \in \mathbb{N}^+$) のときのみ $\varphi(\varphi(n))$ 個原始根が存在する。

位数 (multiplicative order)

$a \perp n$ を満たす $a \in \mathbb{Z},\ n \in \mathbb{N}^+$ に対して $a^k \equiv 1 \pmod{n}$ を満たす最小の $k \in \mathbb{N}^+$ である。

指数 (index)

$n$ を法とする原始根を $g$ とすると、任意の $a \in \mathbb{Z}$ に対して $g^e \equiv a \pmod{n}$ を満たす $0 \leq e < \varphi(n)$ がただ一つ存在する。この $e$ を「$g$ を底とする $a$ の指数」と呼び、$\mathrm{Ind}_g(a)$ と表す。

時間計算量

	時間計算量
原始根判定	$O(\sqrt{M})$

仕様

原始根判定

名前	戻り値
bool is_primitive_root(long long root, const int m);	$\mathrm{root}$ は $m$ を法とする原始根であるか。

参考文献

• Carl Friedrich Gauss: Disquisitiones Arithmeticae (1801).
• https://ja.wikipedia.org/wiki/%E6%8C%87%E6%95%B0_(%E5%88%9D%E7%AD%89%E6%95%B4%E6%95%B0%E8%AB%96)
• https://37zigen.com/primitive-root/

原始根判定

• https://lumakernel.github.io/ecasdqina/math/general
• https://hackmd.io/@qLethon/SJV41ERNL

TODO

• 高速化
  • https://twitter.com/noshi91/status/1317022141599002624
• 原始根を求める。
  • https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp#L142
  • https://github.com/drken1215/algorithm/blob/master/MathNumberTheory/primitive_root.cpp
  • https://judge.yosupo.jp/problem/primitive_root
• 位数
  • https://github.com/beet-aizu/library/blob/e480647072b3a5cb2016e9137c024ccc043a897f/mod/order.cpp
  • 問題例 “Discrete Logarithm Problems”
    • https://twitter.com/laycrs/status/1743628521358926023
    • https://twitter.com/SSRS_cp/status/1743628563146760264
    • https://twitter.com/205_series/status/1743628597686882598

Submissons

• 原始根判定

Depends on

• オイラーの $\varphi$ 関数 (Euler's totient function) (include/emthrm/math/euler_phi.hpp)
• 繰り返し二乗法 / 二分累乗法 / バイナリ法 (include/emthrm/math/mod_pow.hpp)
• 素因数分解 (prime factorization) (include/emthrm/math/prime_factorization.hpp)

Verified with

• 数学/原始根判定 (test/math/is_primitive_root.test.cpp)

Code

#ifndef EMTHRM_MATH_IS_PRIMITIVE_ROOT_HPP_
#define EMTHRM_MATH_IS_PRIMITIVE_ROOT_HPP_

#include <algorithm>
#include <map>
#include <numeric>
#include <ranges>
#include <utility>
#include <vector>

#include "emthrm/math/euler_phi.hpp"
#include "emthrm/math/mod_pow.hpp"
#include "emthrm/math/prime_factorization.hpp"

namespace emthrm {

bool is_primitive_root(long long root, const int m) {
  if ((root %= m) < 0) root += m;
  if (std::gcd(root, m) > 1) return false;
  static std::map<int, int> phi;
  if (!phi.contains(m)) phi[m] = euler_phi(m);
  const int phi_m = phi[m];
  static std::map<int, std::vector<int>> primes;
  if (!primes.contains(phi_m)) {
    // GCC 12 adopted P2415.
    const std::vector<std::pair<int, int>> pf = prime_factorization(phi_m);
    const auto ev = pf | std::views::keys;
    // const auto ev = prime_factorization(phi_m) | std::views::keys;
    primes[phi_m] = std::vector<int>(ev.begin(), ev.end());
  }
  return std::none_of(primes[phi_m].begin(), primes[phi_m].end(),
                      [root, phi_m, m](const int p) -> bool {
                        return mod_pow(root, phi_m / p, m) == 1;
                      });
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_IS_PRIMITIVE_ROOT_HPP_

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



#include <algorithm>
#include <map>
#include <numeric>
#include <ranges>
#include <utility>
#include <vector>

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



#include <cassert>

namespace emthrm {

long long euler_phi(long long n) {
  assert(n >= 1);
  long long res = n;
  for (long long i = 2; i * i <= n; ++i) {
    if (n % i == 0) [[unlikely]] {
      res -= res / i;
      while (n % i == 0) n /= i;
    }
  }
  return n > 1 ? res - res / n : res;
}

}  // namespace emthrm


#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 1 "include/emthrm/math/prime_factorization.hpp"



#line 6 "include/emthrm/math/prime_factorization.hpp"

namespace emthrm {

template <typename T>
std::vector<std::pair<T, int>> prime_factorization(T n) {
  std::vector<std::pair<T, int>> res;
  for (T i = 2; i * i <= n; ++i) {
    if (n % i == 0) [[unlikely]] {
      int exponent = 0;
      for (; n % i == 0; n /= i) {
        ++exponent;
      }
      res.emplace_back(i, exponent);
    }
  }
  if (n > 1) res.emplace_back(n, 1);
  return res;
}

}  // namespace emthrm


#line 14 "include/emthrm/math/is_primitive_root.hpp"

namespace emthrm {

bool is_primitive_root(long long root, const int m) {
  if ((root %= m) < 0) root += m;
  if (std::gcd(root, m) > 1) return false;
  static std::map<int, int> phi;
  if (!phi.contains(m)) phi[m] = euler_phi(m);
  const int phi_m = phi[m];
  static std::map<int, std::vector<int>> primes;
  if (!primes.contains(phi_m)) {
    // GCC 12 adopted P2415.
    const std::vector<std::pair<int, int>> pf = prime_factorization(phi_m);
    const auto ev = pf | std::views::keys;
    // const auto ev = prime_factorization(phi_m) | std::views::keys;
    primes[phi_m] = std::vector<int>(ev.begin(), ev.end());
  }
  return std::none_of(primes[phi_m].begin(), primes[phi_m].end(),
                      [root, phi_m, m](const int p) -> bool {
                        return mod_pow(root, phi_m / p, m) == 1;
                      });
}

}  // namespace emthrm

Back to top page