math/primitive_root.cpp

• View this file on GitHub
• Last update: 2022-01-28 13:07:07+09:00

Depends on

• internal/barret_reduction.cpp
• math/mod_pow.cpp
• math/rem_euclid.cpp
• utility/int_alias.cpp

Required by

• algorithm/convolution_arbitrary_mod.cpp
• algorithm/convolution_int.cpp
• algorithm/convolution_mod.cpp
• internal/modulo_transform.cpp

Verified with

• test/convolution_arbitrary_mod.test.cpp
• test/convolution_mod.test.cpp

Code

#pragma once
#include <array>
#include "../utility/int_alias.cpp"
#include "mod_pow.cpp"

constexpr u32 primitive_root(const u32 mod) {
    std::array<u32, 32> exp{};
    u32 cur = mod - 1;
    int size = 0;
    for (u32 i = 2; i * i <= cur; ++i) {
        if (cur % i == 0) {
            exp[size++] = (mod - 1) / i;
            while (cur % i == 0) cur /= i;
        }
    }
    if (cur != 1) exp[size++] = (mod - 1) / cur;
    for (u32 check = 1; check < mod; ++check) {
        for (const u32 e : exp) {
            if (e == 0) return check;
            if (mod_pow(check, e, mod) == 1) break;
        }
    }
    return mod;
}

#line 2 "math/primitive_root.cpp"
#include <array>
#line 2 "utility/int_alias.cpp"
#include <cstdint>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 2 "math/mod_pow.cpp"
#include <cassert>
#include <type_traits>
#line 3 "internal/barret_reduction.cpp"

namespace proconlib {

class BarretReduction {
    u32 mod;
    u64 near_inv;

  public:
    explicit constexpr BarretReduction(const u32 mod) noexcept : mod(mod), near_inv((u64)(-1) / mod + 1) {}
    constexpr u32 product(const u32 a, const u32 b) const noexcept {
        const u64 z = (u64)a * b;
        const u64 x = ((u128)z * near_inv) >> 64;
        const u32 v = z - x * mod;
        return v < mod ? v : v + mod;
    }
    constexpr u32 get_mod() const noexcept { return mod; }
};

}  // namespace proconlib
#line 3 "math/rem_euclid.cpp"

template <class T> constexpr T rem_euclid(T value, const T& mod) {
    assert(mod > 0);
    return (value %= mod) >= 0 ? value : value + mod;
}
#line 7 "math/mod_pow.cpp"

template <class T> constexpr u32 mod_pow(T x, u64 exp, const u32 mod) {
    assert(mod > 0);
    if (mod == 1) return 0;
    const proconlib::BarretReduction bt(mod);
    u32 ret = 1, mul = rem_euclid<std::common_type_t<T, i64>>(x, mod);
    for (; exp > 0; exp >>= 1) {
        if (exp & 1) ret = bt.product(ret, mul);
        mul = bt.product(mul, mul);
    }
    return ret;
}
#line 5 "math/primitive_root.cpp"

constexpr u32 primitive_root(const u32 mod) {
    std::array<u32, 32> exp{};
    u32 cur = mod - 1;
    int size = 0;
    for (u32 i = 2; i * i <= cur; ++i) {
        if (cur % i == 0) {
            exp[size++] = (mod - 1) / i;
            while (cur % i == 0) cur /= i;
        }
    }
    if (cur != 1) exp[size++] = (mod - 1) / cur;
    for (u32 check = 1; check < mod; ++check) {
        for (const u32 e : exp) {
            if (e == 0) return check;
            if (mod_pow(check, e, mod) == 1) break;
        }
    }
    return mod;
}

Back to top page