【学习笔记】二次剩余（Quadratic Residue）
前言
本来是为了多项式来学学，结果被震惊了......
正题
给定 $n,p$，保证 $p$ 是奇质数，求解 $x^2\equiv n\ (\bmod\ p)$。
模意义开根
以下运算都在模 $p$ 的意义下。
首先称使得 $x^2\equiv n\ (\bmod\ p)$ 有解的 $n$ 是二次剩余，无解的是非二次剩余。
解的数量
对于二次剩余 $n$，假设方程有多个解，取出其中两个 $x_0,x_1$。
有：$x_0^2\equiv x_1^2\ (\bmod\ p)$
移项得到：
$$(x_0-x_1)(x_0+x_1)\equiv 0\ (\bmod\ p)$$
但是 $x_0\ne x_1$，所以 $x_0+x_1=0$。也就是他们一定互为相反数。又模奇质数 $p$，所以 $x_0,x_1$ 在模 $p$ 意义下不等。所以该方程仅有 $2$ 个解，且两个解互为相反数。
反过来，任意一对相反数，都对应着一个二次剩余，且这些二次剩余显然两两不同。所以二次剩余的个数是 $\lfloor \dfrac{p}{2}\rfloor=\dfrac{p-1}{2}$。
欧拉准则
用于判定 $n$ 是否是模 $p$ 意义下的二次剩余。
由费马小定理 $n^{p-1}\equiv 1\ (\bmod\ p)$，可以得到：
$$n^{2(\frac{p-1}{2})}\equiv 1\ (\bmod\ p)$$
也就是 $n^{\frac{p-1}{2}}$ 是 $1$ 开根的解。又 $1$ 开根的结果只能是 $1$ 和 $-1$，所以 $n^{\frac{p-1}{2}}$ 只能同余于 $1$ 或者 $-1$。
下面证明：$n$ 是二次剩余 $\iff$ $n^{\frac{p-1}{2}}\equiv 1\ (\bmod\ p)$。
如果 $n$ 是二次剩余，则存在 $x$ 使得 $x^2\equiv n\ (\bmod\ p)$。费马小定理可知 $x^{p-1}\equiv 1\ (\bmod\ p)$，所以：$n^{\frac{p-1}{2}}\equiv 1\ (\bmod\ p)$。
如果 $n^{\frac{p-1}{2}}\equiv 1\ (\bmod\ p)$，考虑模 $p$ 意义下的原根 $g$，$n=g^k$。那么有 $g^{k\times \frac{p-1}{2}}\equiv 1\ (\bmod\ p)$，又费马小定理有：$g^{p-1}\equiv 1\ (\bmod\ p)$，那么有 $p-1|k\times \dfrac{p-1}{2}$，也就是 $k$ 必是偶数。那么 $x^2\equiv n\ (\bmod\ p)$ 一定有解 $x=g^{\frac{k}{2}}$。
因此 $n$ 是二次剩余 $\iff$ $n^{\frac{p-1}{2}}\equiv 1\ (\bmod\ p)$。
那么就有 $n$ 是非二次剩余 $\iff$ $n^{\frac{p-1}{2}}\equiv -1\ (\bmod\ p)$
$\text{Cipolla}$ 算法
解方程 $x^2\equiv n\ (\bmod\ p)$。
找到一个 $a$ 使得 $a^2-n$ 是非二次剩余，而非二次剩余的数量接近 $\dfrac{p}{2}$，所以随机一下，期望 $2$ 次就可以得到一个。
定义 $i$ 使得 $i^2\equiv a^2-n\ (\bmod\ p)$
可以考虑用类似复数的表示方法，把所有数表示为 $A+Bi$ 的形式，与实部，虚部类似。
那么有 $(a+i)^{p+1}\equiv n\ (\bmod\ p)$。
先证明两个引理：
$i^p\equiv i\ (\bmod\ p)$
证明：
$$i^p\equiv i\times (i^2)^{\frac{p-1}{2}}\equiv i\times (a^2-n)^{\frac{p-1}{2}}\equiv -i\ (\bmod\ p)$$
$(x+y)^p\equiv x^p+y^p\ (\bmod\ p)$
证明：
二项式定理拆开之后，由于 $p$ 是质数，所以除 $\binom{p}{0},\binom{p}{p}$ 之外的组合数，都会因为阶乘上有消不掉的 $p$ 而被模成 $0$，所以最后 $(x+y)^p\equiv \binom{p}{0}x^p y^0+\binom{p}{p}x^0 y^p\equiv x^p+y^p\ (\bmod\ p)$。
接着证明 $(a+i)^{p+1}\equiv n\ (\bmod\ p)$。
$$(a+i)^{p+1}\equiv (a+i)^p(a+i)\equiv (a^p+i^p)(a+i)\equiv (a-i)(a+i)\equiv a^2-i^2\equiv n\ (\bmod\ p)$$
因此 $(a+i)^{\frac{p+1}{2}}$ 和其相反数是方程 $x^2\equiv n\ (\bmod\ p)$ 的两个解。
证明 $(a+i)^{\frac{p+1}{2}}$ 的“虚部” 为 $0$。
设 $(a+i)^{\frac{p+1}{2}}=A+Bi$，则 $B\ne 0$。
那么先要满足 $(A+Bi)^2\equiv n\ (\bmod\ p)$。
拆掉括号有：
$$A^2+2ABi+B^2i^2\equiv n\ (\bmod\ p)$$
移项：
$$A^2+B^2i^2-n\equiv -2ABi\ (\bmod\ p)$$
不难发现左边“虚部”为 $0$，那右边“虚部”就需要也是 $0$。也就是 $AB=0$，又设了 $B\ne 0$，所以 $A=0$。
也就是 $(Bi)^2\equiv n\ (\bmod\ p)$，把 $B^2$ 求逆元乘过去可得：$i^2\equiv n\times B^{-2}\ (\bmod\ p)$，又 $n,B^{-2}$ 都是二次剩余，那么他们的乘积必是二次剩余。又 $i^2$ 不是二次剩余，所以与之前的设定矛盾。
也就是 $B=0$！
板子：
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
//#define ull unsigned long long
#define LL long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define scd second
#define inv(x) qpow((x),mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define vec vector
const int MAXN = 1;
const int INF = 2e9;
const double PI = acos(-1);
const double eps = 1e-6;
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int T, n, m, ans1, ans2;
int i2, mod;
struct Complex {
int real, imag;
Complex(int R = 0, int I = 0) : real(R), imag(I) {}
Complex operator * (const Complex &b) const {
return Complex((real * b.real % mod + i2 * imag % mod * b.imag % mod) % mod, (imag * b.real % mod + real * b.imag % mod) % mod);
}
};
template<typename T> inline void read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
a *= f;
}
int qpow(int x, int b) {
int res = 1;
for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod;
return res;
}
Complex qpow(Complex x, int b) {
Complex res = Complex(1, 0);
for(; b; b >>= 1, x = x * x) if(b & 1) res = res * x;
return res;
}
bool chk(int x) {
return qpow(x, (mod - 1) >> 1) == 1 ? true : false;
}
int randint(int l, int r) {
return rand() % (r - l + 1) + l;
}
void Solve(int n, int p, int &x0, int &x1) {
mod = p;
int a = randint(0, mod - 1);
while(!a || chk(((a * a % mod - n) % mod + mod) % mod)) a = randint(0, mod - 1);
i2 = ((a * a % mod - n) % mod + mod) % mod;
Complex tmp = qpow(Complex(a, 1), (mod + 1) >> 1);
assert(!tmp.imag);
x0 = (qpow(Complex(a, 1), (mod + 1) >> 1).real % mod + mod) % mod;
x1 = ((mod - x0) % mod + mod) % mod;
}
signed main () {
#ifdef FILE
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
srand(5224999);
read(T);
while(T--) {
read(n); read(m);
mod = m;
if(!n) {
puts("0");
continue;
}
if(!chk(n)) {
puts("Hola!");
continue;
}
Solve(n, m, ans1, ans2);
if(ans1 == ans2) printf("%lld\n",ans1);
else printf("%lld %lld\n",min(ans1, ans2), max(ans1, ans2));
}
return 0;
}
神
！
神
！