原始根
$ \bmod p上において、$ p-1乗してはじめて$ 1になるような数を原始根という。
たとえば、$ \bmod 17では、$ \{3, 5, 6, 7, 10, 11, 12, 14\}が原始根となる。
原始根でない数、たとえば$ 2についていえば、$ 2^8\equiv 1 \pmod{17}のように、$ p-1より小さい数で累乗しても$ 1になる。
原始根の個数
これは原始根の周期が$ p-1であるので、どの原始根も$ p-1と互いに素な数乗するとやはり原始根になると考えるとわかりやすい。
これは結構多くて、例えば$ \bmod 998244353だと$ 402653184個あり、半分よりちょっと少ないくらい。
この事実を利用すると、例えば$ 2以上$ p-1以下の数を乱択して原始根判定することで高速に原始根を得ることができる。
原始根判定
事前に$ p-1を素因数分解し、$ p-1の素因数$ P_1, P_2, \ldotsを求めておく。
$ aが原始根かを判定するには、$ \forall i, a^{\frac{p-1}{P_i}} \not\equiv 1 \pmod pであることを判定すればよい。
参考