首先是素数模同余方程的相关理论。
下设 $p\in $ 是质数，\(f(x)=\sum_{i=0}^n a_ix^i\)，\(x\in \Z_p,p\not\mid a_n\)。
引理 1
如果 \(f(x)\equiv 0\pmod p\) 具有解 \(x_1\sim x_k\)，且 \(k\le n\)。则
\[f(x)\equiv g(x)\prod (x-x_i)\pmod p \]其中 \(\deg g=n-k,[x^{n-k}]g(x)=a_n\)。
归纳法不难证明此命题。
可以推出威尔逊定理。
定理 1 Lagrange 定理
\[f(x)\equiv 0\pmod p \]至多具有 \(n\) 个不同解。
证明：
设其具有解 \(x_1\sim x_{n+1}\)，则有
\[f(x)\equiv a_n\prod_{i=1}^n (x-x_i)\pmod p \]取 \(x=x_{n+1}\)，右侧任何数都不整除 \(p\)。
推论：如果有超过 \(n\) 个解，那么所有系数整除 \(p\)。
定理 2
设 \(n\le p\)，则首一多项式 \(f(x)\equiv 0\pmod p\) 有 \(n\) 个解，当且仅当：
存在整系数多项式 \(q(x),r(x)\)，且 \(\deg r<n\)，满足：
\[x^p-x=f(x)q(x)+pr(x) \]证明：
首先证明必要性。若 \(f(x)\equiv 0\pmod p\) 有 \(n\) 个解，那么考虑 \(r_1(x)=x^p-x-f(x)q(x)\)，应该有 \(n\) 个解。而 \(n>\deg r_1\)，故 \(r_1\) 的系数整除 \(p\)。那么 \(r_1(x)=pr(x)\)。
充分性：首先 \(x^p-x=f(x)q(x)+pr(x)\equiv 0\pmod p\) 有 \(p\) 个解，根据费马小定理。设 \(f(x)\equiv 0\pmod p\) 有 \(s\) 个解，显然 \(s\le n\)。
而 \(q(x)\equiv 0\) 有至多 \(p-n\) 个解，又因为 \(\{x\mid f(x)q(x)\equiv 0\}=\{x\mid f(x)\equiv 0\}\cup \{x\mid q(x)\equiv 0\}\)，\(p\le (p-n)+s\)，即 \(s\ge n\)。则 \(s=n\)，证毕。
接下来依托定理 \(2\)，二（\(k\)）次剩余存在的条件可以被证明。
定理 3
设 \(n\not\mid p-1,p\not\in a\)。
\[x^n\equiv a\pmod p \]则此方程有解当且仅当
\[a^{\frac{p-1}n}\equiv 1\pmod p \]若有解，有 \(n\) 个解。
证明：
必要性显然。
充分性是某个 WF 选手不会的：
其中 \(P(x)\) 是整系数多项式。\(xP(x)\) 当然也是。根据以上定理，存在 \(n\) 个解。
对于二次剩余：
\[a^p-1=(a^{\frac{p-1}2}+1)(a^{\frac{p-1}2}-1)\equiv0\pmod p\\ \]所以 \(a\) 是非二次剩余当且仅当 \(a^{\frac{p-1}2}\equiv -1\pmod p\)。
Cipolla
不难发现 \(\dfrac{p-1}2\) 个数有二次剩余，同样多的数没有。
考虑求解
\[x^2\equiv c\pmod p \]所以，可以随机出 \(a\) 使得 \(a^2-c\) 不是二次剩余。此时有 \((a^2-c)^{\frac{p-1}2}\equiv -1\pmod p\)。
对 \(\Z_p\) 环进行代数扩张，变为 \(\C_p\)，虚根 \(\omega\) 认为是 \(\omega^2\equiv a^2-c\pmod p\)。
不难发现 \(\omega^p=-\omega\)。
下面证明：\(c=(a+\omega)^{p+1}\)。
根据升幂引理，\((a+\omega)^{p+1}=(a^p+\omega^p)(a+\omega)=(a-\omega)(a+\omega)=c\)。
证毕！
标签：剩余,frac,pmod,定理,算法,个解,Cipolla,omega,equiv From： https://www.cnblogs.com/british-union/p/17975207/cipolla