k乗根 mod p

$ \sqrt[k]{a} \bmod p

存在する条件（必要十分条件）

$ a = 0なら常に存在する。

$ a\ne 0の場合

$ aがある原始根$ gを用いて$ a \equiv g^n \pmod pと表されるとき、$ \gcd(p - 1, k) | nでなければならない。

つまり、$ a^{(p-1)/\gcd(p - 1, k)} \equiv 1 \pmod pであること。

計算量

$ O(\log p)

個数

$ \frac{p - 1}{\gcd(p - 1, k)} + 1

求め方

$ k=2の場合はTonelli-Shanks法（ラスベガス法）によって$ O(\log^2 p)で求められる。

一般の$ kについては、Adleman-Manders-Miller法（ラスベガス法）によって$ O(\log^4 p + k \log^3 p)で求められる。