Primitive root
(Mylib/Number/Prime/primitive_root.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

Requirements

• pは素数

Notes

Problems

References

Depends on

• Mod pow (Mylib/Number/Mod/mod_pow.cpp)

Required by

• Convolution (Index multiplication mod P) (Mylib/Convolution/convolution_multiply.cpp)

Verified with

• test/yosupo-judge/bernoulli_number/main.test.cpp
• test/yosupo-judge/convolution_mod/main.test.cpp
• test/yosupo-judge/exp_of_formal_power_series/main.montgomery.test.cpp
• test/yosupo-judge/exp_of_formal_power_series/main.test.cpp
• test/yosupo-judge/inv_of_formal_power_series/main.test.cpp
• test/yosupo-judge/kth_term_of_linearly_recurrent_sequence/main.test.cpp
• test/yosupo-judge/log_of_formal_power_series/main.test.cpp
• test/yosupo-judge/multipoint_evaluation/main.test.cpp
• test/yosupo-judge/partition_function/main.fps.test.cpp
• test/yosupo-judge/polynomial_taylor_shift/main.test.cpp
• test/yosupo-judge/pow_of_formal_power_series/main.test.cpp
• test/yosupo-judge/sharp_p_subset_sum/main.test.cpp
• test/yosupo-judge/sqrt_of_formal_power_series/main.test.cpp
• test/yosupo-judge/stirling_number_of_the_first_kind/main.test.cpp
• test/yosupo-judge/stirling_number_of_the_second_kind/main.test.cpp
• test/yukicoder/931/main.test.cpp

Code

#pragma once
#include "Mylib/Number/Mod/mod_pow.cpp"

namespace haar_lib {
  constexpr int primitive_root(int p) {
    int pf[30] = {};
    int k      = 0;
    {
      int n = p - 1;
      for (int64_t i = 2; i * i <= p; ++i) {
        if (n % i == 0) {
          pf[k++] = i;
          while (n % i == 0) n /= i;
        }
      }
      if (n != 1)
        pf[k++] = n;
    }

    for (int g = 2; g <= p; ++g) {
      bool ok = true;
      for (int i = 0; i < k; ++i) {
        if (mod_pow(g, (p - 1) / pf[i], p) == 1) {
          ok = false;
          break;
        }
      }

      if (not ok) continue;

      return g;
    }
    return -1;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/Mod/mod_pow.cpp"
#include <cstdint>

namespace haar_lib {
  constexpr int64_t mod_pow(int64_t n, int64_t p, int64_t m) {
    int64_t ret = 1;
    while (p > 0) {
      if (p & 1) (ret *= n) %= m;
      (n *= n) %= m;
      p >>= 1;
    }
    return ret;
  }
}  // namespace haar_lib
#line 3 "Mylib/Number/Prime/primitive_root.cpp"

namespace haar_lib {
  constexpr int primitive_root(int p) {
    int pf[30] = {};
    int k      = 0;
    {
      int n = p - 1;
      for (int64_t i = 2; i * i <= p; ++i) {
        if (n % i == 0) {
          pf[k++] = i;
          while (n % i == 0) n /= i;
        }
      }
      if (n != 1)
        pf[k++] = n;
    }

    for (int g = 2; g <= p; ++g) {
      bool ok = true;
      for (int i = 0; i < k; ++i) {
        if (mod_pow(g, (p - 1) / pf[i], p) == 1) {
          ok = false;
          break;
        }
      }

      if (not ok) continue;

      return g;
    }
    return -1;
  }
}  // namespace haar_lib

Back to top page