primitive_root.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#pragma once

#include "binpow.h"

template <typename Mod> struct FiniteField {
  static constexpr Mod primitive_root() {
    int g = 2;
    while (!is_primitive_root(Mod{g})) {
      g++;
    }
    return Mod{g};
  }

private:
  static constexpr bool is_primitive_root(Mod g) {
    for (int d = 2; d * d <= Mod::mod() - 1; ++d) {
      if ((Mod::mod() - 1) % d == 0 &&
          (binpow(g, d).get() == 1 ||
           binpow(g, (Mod::mod() - 1) / d).get() == 1)) {
        return false;
      }
    }
    return true;
  }
};