math/primitive-root.hpp

View this file on GitHub
Last update: 2023-10-01 12:06:18+09:00
Include: #include "math/primitive-root.hpp"

Depends on

math/pow_mod.hpp

Required by

math/convolution/ntt.hpp

Verified with

test/library-checker/convolution/convolution-mod.test.cpp

Code

#pragma once

#include "pow_mod.hpp"

constexpr int primitive_root(int p) {
    if(p == 2) return 1;
    if(p == 998244353) return 3;
    int primes[31] = {};
    int sz = 0, t = p - 1;
    for(int i = 2; i * i <= t; i++) {
        if(t % i == 0) {
            primes[sz++] = i;
            while(t % i == 0) t /= i;
        }
    }
    if(t > 1) primes[sz++] = t;
    for(int g = 2;;g++) {
        bool f = true;
        for(int i = 0; i < sz; i++) {
            if(pow_mod(g, (p - 1) / primes[i], p) == 1) {
                f = false;
                break;
            }
        }   
        if(f) return g;
    }
}

#line 2 "math/primitive-root.hpp"

#line 2 "math/pow_mod.hpp"

constexpr long long pow_mod(long long x, long long k, long long m) {
    long long res = 1;
    long long mul = (x >= 0 ? x % m : x % m + m);
    while(k) {
        if(k & 1) res = (__int128_t)res * mul % m;
        mul = (__int128_t)mul * mul % m;
        k >>= 1;
    }
    return res;
}
#line 4 "math/primitive-root.hpp"

constexpr int primitive_root(int p) {
    if(p == 2) return 1;
    if(p == 998244353) return 3;
    int primes[31] = {};
    int sz = 0, t = p - 1;
    for(int i = 2; i * i <= t; i++) {
        if(t % i == 0) {
            primes[sz++] = i;
            while(t % i == 0) t /= i;
        }
    }
    if(t > 1) primes[sz++] = t;
    for(int g = 2;;g++) {
        bool f = true;
        for(int i = 0; i < sz; i++) {
            if(pow_mod(g, (p - 1) / primes[i], p) == 1) {
                f = false;
                break;
            }
        }   
        if(f) return g;
    }
}