二次剩余问题其实就是数论中的开方运算。
我们要解决这么一个问题，给定正整数 \(n\)，奇素数 \(p\)，求解
\[x^2 \equiv n \pmod p \]本文内认为模数 \(p\) 是一个奇素数。
定义
若存在 \(x^2 \equiv n \pmod p\)，则称 \(n\) 为模 \(p\) 的二次剩余，反之则称 \(n\) 为模 \(p\) 的非二次剩余。
可以用欧拉判定准则判断一个数是否为二次剩余。
若 \(n^{\frac{p-1}{2}} \equiv 1 \pmod p\)，则 \(n\) 为二次剩余。
若 \(n^{\frac{p-1}{2}} \equiv -1 \pmod p\)，则 \(n\) 为非二次剩余。
证明：
首先，由于 \(n^{p-1} \equiv 1 \pmod p\)，用平方差公式可得 \((n^{\frac{p-1}{2}} - 1)(n^{\frac{p-1}{2}}+1) \equiv 0 \pmod p\)。所以 \(n^{\frac{p-1}{2}} \bmod p\) 只有 \(1\)，\(-1\) 两种可能。
然后，由于 \(p\) 是奇素数，存在原根 \(g\)，设 \(n = g^i\)，则有
\[n^{\frac{p-1}{2}} \equiv g^{\frac{i(p-1)}{2}} \equiv \pm 1 \pmod p \]又因为 \(g^{\frac{p-1}{2}} \equiv -1 \pmod p\)，所以上式为 \(1\) 时，\(i\) 为偶数，存在 \(x=g^{\frac{i}{2}}\)，使得 \(x^2 \equiv n \pmod p\) 成立，反之不存在。
由证明过程我们可以知道，原根的偶数次方是二次剩余，奇数次方是非二次剩余，所以 \(1\dots p-1\) 中，二次剩余和非二次剩余个数均是 \(\frac{p-1}{2}\)。
求解——Cipolla 算法
由上面过程可知，我们只要知道原根 \(g\)，求解 \(g^i \equiv n \pmod p\)，就可以了。不过这里求解离散对数还是杀鸡用牛刀了（其实是有更简单复杂度更低的算法）。
Cipolla算法
为什么我第一眼看成了 Ciallo 算法了啊。
这个算法用了复数的定义，不过过程很简单。
- 找到一个 \(a\)，满足 \(a^2-n\) 为非二次剩余，令 \(i^2 \equiv a^2-n \pmod p\)。
- \(x=(a+i)^{\frac{p+1}{2}}\)。
- 由于平方抵消正负，二次剩余的解是 \(x_1=x\)，\(x_2=-x\)。
时间复杂度
由于非二次剩余和二次剩余个数五五开，check常数次就能找到 \(a\)，复杂度 \(O(\log_2p)\)。
快速幂计算 \(O(\log_2{p})\)，总复杂度就是 \(O(\log_2{p})\)。
没错，就这么结束了。要证明的话，其实也不是很难，主要是要理解一个复数的概念。
证明：
我们先定义 \(i^2 \equiv a^2-n \pmod p\)，当然，事实上是不存在一个整数 \(i\) 满足这个条件的。有点类似于代数中的虚数——是由负数开根得到的，实际上并不存在一个实数，它的平方是负数。
类比于复数，我们也能定义一个数论复数，它拥有实部和虚部，可以写成 \(a+bi\) 的形式。各种运算律对复数自然也是适用的。
引理 1:
\[(a+b)^p \equiv a^p+b^p \pmod p \]可以用二项式定理展开 \((a+b)^p\equiv \displaystyle\sum_{i=0}^{p}\frac{p!}{i!(p-i)!}a^ib^{p-i} \pmod p\)
当 \(i=0/n\) 时，组合数不存在 \(p\) 因子，所以就是 \(a^p+b^p\)。
引理 2：
\[i^p \equiv -i \pmod p \]还记得欧拉判别准则吗？\({(i^2)}^{\frac{p-1}{2}} \equiv i^{p-1} \equiv -1 \pmod p\)，所以 \(i^p \equiv -i \pmod p\)。
引理3（费马小定理）：
\[a^p \equiv a \pmod p \]接下来我们证明 \((a+i)^{p+1} \equiv n \pmod p\)。
\[\begin{aligned} (a+i)^{p+1} &= (a+i)^p(a+i) \\ &\equiv (a^p+i^p)(a+i) \\ &\equiv (a-i)(a+i) \\ &=a^2-i^2 \\ &\equiv n \pmod p \end{aligned}\]好了，接下来就是代码实现了（洛谷 P5491）
我们需要定义复数类来进行运算：
typedef long long ll;
ll w; // i^2
ll mult(ll x, ll y) {
return x * y % mod;
}
ll add(ll x, ll y) {
return ((x + y) % mod + mod) % mod;
}
struct Complex{
ll a, b;
Complex (ll aa, ll bb) {
a = aa, b = bb;
}
Complex operator * (const Complex &t) const {
return Complex(add(mult(a, t.a), mult(mult(b, t.b), w)), add(mult(a, t.b), mult(b, t.a))); //数论复数运算法则和代数复数一样
}
};
然后定义复数和整数的快速幂：
ll pow_mod(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
}
return res;
}
Complex pow_mod(Complex a, ll b) {
auto res = Complex(1, 0); //单位复数
while (b) {
if (b & 1) res = res * a;
a = a * a;
}
return res;
}
欧拉判别准则，检验一个数是否为二次剩余：
bool check(ll n) {
if (pow_mod(n, (mod - 1) / 2) == 1) return 1;
return 0;
}
Cipolla 算法主过程：
ll Cipolla(int n) { //已经判定过有解了
ll a = rand() % mod;
while (check(w = add(a * a, -n))) {
a = rand() % mod;
}
return pow_mod(Complex(a, 1), (mod + 1) / 2).a;
}
主函数，判别0，判别是否有解，计算第二个解。
cin >> n >> mod;
n %= mod;
if (n == 0) cout << "0\n";
else if (!check(n)) cout << "Hola!\n";
else {
ll x = Cipolla(n);
ll x2 = add(0, -x);
cout << min(x, x2) << ' ' << max(x, x2) << '\n';
}
这样，二次剩余的模版就结束了。
标签：剩余,frac,数论,模版,ll,pmod,mod,equiv From： https://www.cnblogs.com/Uuuuuur/p/18004788