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

[@square10011](https://twitter.com/square10011)さんと[@noshi91](https://twitter.com/noshi91)さんに教えてもらったので，メモ

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">Z/pZでの原始根を効率的に見つけるアルゴリズム、存在しないのか…？</p>&mdash; 真紅色に染まるぷーん (@pu__Ne) <a href="https://twitter.com/pu__Ne/status/1235455872068775937?ref_src=twsrc%5Etfw">March 5, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

### 方針
$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$のすべての原始根は$r^m (m \perp p - 1)$とかける．
逆に，原始根ではない$\mathbb{Z}/p\mathbb{Z}$の要素は$r^m (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 r^n \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](https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%CF%86%E9%96%A2%E6%95%B0)/[en](https://en.wikipedia.org/wiki/Euler%27s_totient_function))をみると，数分の一くらいはありそうな気がする．
$\frac{6n^2}{\pi^2 \sigma(n)} \lt \phi(n)$らしく($\sigma(n)$は約数関数)，$\sigma(n) < e^{\gamma}n\log \log n$らしいので，$\frac{6n}{\pi^2 e^{\gamma}\log \log n}$．よって，原始根を見つけるまでにかかる判定の回数の期待値の下限は，$\frac{\pi^2 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{\pi^2 e^{\gamma}\log \log n}{6} \approx 10.54$で，実質定数!w