$\mathbb{Z}/p\mathbb{Z}$ での原始根を$O(\sqrt{p})$で求める

@square10011さんと@noshi91さんに教えてもらったので，メモ

方針

$2 \le k \lt p$をランダムに選んで，原始根がどうかを判定する．
1. p - 1を素因数分解 $O(\sqrt{p})$
2. p - 1の素因数$a_i$すべてに対して$k^{\frac{p - 1}{a_i}} \not\equiv 1 \pmod{p}$ならkは原始根 素因数の数を$d$とすると$O(d\log p)$
3. 原始根の数は$\phi(p - 1)$で，これはそんなに小さくならないから全体で$O(d\log p) + O(\sqrt{p}) = O(\sqrt{p})$

$p > 2$です．

正当性

2.について

$\mathbb{Z}/p\mathbb{Z}$での原始根は1つ以上存在する(原始根定理)． そのうちの1つを$r$と置くと，$p$のすべての原始根は$rm (m \perp p - 1)$とかける． 逆に，原始根ではない$\mathbb{Z}/p\mathbb{Z}$の要素は$rm (m \mid p - 1)$とかける． よって，$k$が原始根でなければ，$a_i \cdot n = m$なる$a_i$が存在して， $$k^{\frac{p - 1}{a_i}} \equiv (r^{m})^\frac{p - 1}{a_i} \equiv r^{n(p - 1)} \pmod{p}$$ となる．

フェルマーの小定理から，$r^{p - 1} \equiv 1 \pmod{p}$だから， $$k^{\frac{p - 1}{a_i}} \equiv r^{n(p - 1)} \equiv 1 \pmod{p}$$ となる．

逆に，原始根であれば$m \not\equiv 0 \pmod{p}$，$\frac{p - 1}{a_i} \not\equiv 0 \pmod{p}$なので，原始根の定義($n \not\equiv 0 \pmod{p - 1} \Rightarrow rn \not\equiv 1 \pmod{p}$)から， $$k^{\frac{p - 1}{a_i}} \equiv r^{m\frac{p - 1}{a_i}} \not\equiv 1 \pmod{p}$$ となる．

3.について

正確なことは何もわからないが，wikipedea(ja/en)をみると，数分の一くらいはありそうな気がする． $\frac{6n2}{\pi2 \sigma(n)} \lt \phi(n)$らしく($\sigma(n)$は約数関数)，$\sigma(n) < e^{\gamma}n\log \log n$らしいので，$\frac{6n}{\pi2 e^{\gamma}\log \log n}$．よって，原始根を見つけるまでにかかる判定の回数の期待値の下限は，$\frac{\pi2 e^{\gamma}\log \log n}{6}$．なので，乱択パートには$O(d\log p\log \log p) = O((\log p)2\log \log p)$くらいかかりそう．しかし結局は前処理の素因数分解が支配的で，全体として$O(\sqrt{p})$

ちなみに，$e^{\gamma} \approx 1.78$，$\log \log (10^{18}) \approx 3.72$なので，$n = 10^{18}$のときでも$\frac{\pi2 e^{\gamma}\log \log n}{6} \approx 10.54$で，実質定数!w