本文转载（或修改）自 OI-Wiki
定义
令整数 \(a\)， \(p\) 满足 \(a \bot p\)，若存在整数 \(x\) 使得
\[
x^2\equiv a\pmod p
\]
则称 \(a\) 为模 \(p\) 的二次剩余，否则称 \(a\) 为模 \(p\) 的二次非剩余。
通俗一些，可以认为是求模意义下的 开平方 运算。对于更高次方的开方可参见 \(k\) 次剩余。
这里只讨论 \(p\) 为 奇素数 的求解方法。后文可能在模 \(p\) 显然的情况下简写成二次（非）剩余。
Euler 判别法
对奇素数 \(p\) 和满足 \(a \bot p\) 的整数 \(a\)，
\[
a^{\frac{p-1}{2}}\equiv\begin{cases}
1 \pmod p, & (\exists x\in\mathbf{Z}),~~a\equiv x^2\pmod p,\\
-1 \pmod p, & \text{otherwise}.\\
\end{cases}
\]
即对上述的 \(p\) 和 \(a\)，
- \(a\) 是 \(p\) 的二次剩余当且仅当 \(a^{\frac{p-1}{2}}\equiv 1 \pmod p\) .
- \(a\) 是 \(p\) 的二次非剩余当且仅当 \(a^{\frac{p-1}{2}}\equiv -1 \pmod p\) .
证明
首先由 Fermat 小定理，有 \(a^{p-1}\equiv 1\pmod p\)，故
\[
\left(a^{\frac{p-1}{2}}+1\right)\left(a^{\frac{p-1}{2}}-1\right)\equiv 0\pmod p
\]
从而对任意满足 \(a \bot p\) 的 \(a\) 均有 \(a^{(p-1)/2}\equiv \pm 1\pmod p\)
另外由 \(p\) 是奇素数，我们有：
\[
x^{p-1}-a^{\frac{p-1}{2}}={\left(x^2\right)}^{\frac{p-1}{2}}-a^{\frac{p-1}{2}}=(x^2-a)P(x)
\]
其中 \(P(x)\) 是某个整系数多项式，进而：
\[
\begin{aligned}
x^p-x&=x\left(x^{p-1}-a^{\frac{p-1}{2}}\right)+x\left(a^{\frac{p-1}{2}}-1\right)\\
&=(x^2-a)xP(x)+\left(a^{\frac{p-1}{2}}-1\right)x\\
\end{aligned}
\]
因此，\(a\) 是模 \(p\) 的二次剩余当且仅当 \(a^{(p-1)/2}\equiv 1\pmod p\) . 进而 \(a\) 是模 \(p\) 的非二次剩余当且仅当 \(a^{(p-1)/2}\equiv -1\pmod p\) .
Legendre 符号
定义
对奇素数 \(p\) 和整数 \(a\)，定义 Legendre 符号如下：
\[
\left(\frac{a}{p}\right)=\begin{cases}
0, & p\mid a,\\
1, & (p\nmid a) \land ((\exists x\in\mathbf{Z}),~~a\equiv x^2\pmod p),\\
-1, & \text{otherwise}.\\
\end{cases}
\]
性质
性质一
对任意整数 \(a\)，
\[
a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\pmod p
\]
进一步，我们有推论：
\[
\left(\frac{1}{p}\right)=1
\]
以及
\[
\begin{aligned}
\left(\frac{-1}{p}\right)&=(-1)^{\frac{p-1}{2}}\\
&=\begin{cases}
1, & p\equiv 1\pmod 4,\\
-1, & p\equiv 3\pmod 4.
\end{cases}
\end{aligned}
\]
证明
由 Legendre 符号的定义 和 Euler 判别法 易得。
性质二
\(a_1\equiv a_2\pmod p\implies \left(\frac{a_1}{p}\right)=\left(\frac{a_2}{p}\right)\)
证明
注意到
\[
a_1\equiv a_2\pmod p\implies \left(\frac{a_1}{p}\right)\equiv\left(\frac{a_2}{p}\right)\pmod p
\]
而 \(\left|\left(\frac{a_1}{p}\right)-\left(\frac{a_2}{p}\right)\right|\leq 2\) 且 \(p>2\) , 故：
\[
a_1\equiv a_2\pmod p\implies \left(\frac{a_1}{p}\right)=\left(\frac{a_2}{p}\right)
\]
性质三（完全积性）
对任意整数 \(a_1,a_2\)，
\[
\left(\frac{a_1a_2}{p}\right)=\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right)
\]
我们有推论：对整数 \(a,b\)， \(p\nmid b\) 有
\[
\left(\frac{ab^2}{p}\right)=\left(\frac{a}{p}\right)
\]
证明
由 1 得
\[
\left(\frac{a_1a_2}{p}\right)\equiv a_1^{\frac{p-1}{2}}a_2^{\frac{p-1}{2}}\equiv\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right)\pmod p
\]
而 \(\left|\left(\frac{a_1a_2}{p}\right)-\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right)\right|\leq 2\) 且 \(p>2\) , 故：
\[
\left(\frac{a_1a_2}{p}\right)=\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right)
\]
性质四
\[
\begin{aligned}
\left(\frac{2}{p}\right)&=(-1)^{\frac{p^2-1}{8}}\\
&=\begin{cases}
1, & p\equiv \pm 1\pmod 8 \\
-1, & p\equiv \pm 3\pmod 8 \\
\end{cases}
\end{aligned}
\]
证明
参见 二次互反律
二次互反律
二次互反律
设 \(p\)， \(q\) 是两个不同的奇素数，则
\[
\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}
\]
证明方式很多，一种证明方式是基于如下引理（Gauss 引理）：
Gauss 引理
设 \((n,p)=1\) , 对整数 \(k~\left(1\leq k\leq \frac{p-1}{2}\right)\)，令 \(r_k\) 为 \(nk\) 模 \(p\) 的最小非负剩余，设 \(m\) 为所有 \(r_k\) 中大于 \(\frac{p}{2}\) 的个数，则
\[
\left(\frac{n}{p}\right)=(-1)^m
\]
这个引理可以证明如下有用的结论：
结论
对奇素数 \(p\)，
\[
\begin{aligned}
\left(\frac{2}{p}\right)&=(-1)^{\frac{p^2-1}{8}}\\
&=\begin{cases}
1, & p\equiv \pm 1\pmod 8 \\
-1, & p\equiv \pm 3\pmod 8 \\
\end{cases}
\end{aligned}
\]
二次互反律不仅能用于判断数 \(n\) 是否是模 \(p\) 的二次剩余，还能用于确定使数 \(n\) 为二次剩余的模数的结构。
二次剩余的数量
对于奇素数 \(p\)，模 \(p\) 意义下二次剩余和二次非剩余均有 \(\frac{p-1}{2}\) 个。
证明
根据 Euler 判别法，考虑 \(a^{\frac{p-1}{2}}\equiv 1\pmod p\) .
注意到 \(\frac{p-1}{2}\mid (p-1)\)，这可知 \(a^{\frac{p-1}{2}}\equiv 1\pmod p\) 有 \(\frac{p-1}{2}\) 个解。所以模 \(p\) 意义下二次剩余和二次非剩余均有 \(\frac{p-1}{2}\) 个。
Cipolla 算法
P5491 【模板】二次剩余
给出 \(N,p\)，求解方程
\[
x^2 \equiv N \pmod{p}
\]
多组数据，且保证 \(p\) 是奇素数。
对于 \(100\%\) 的数据，\(1\leq T\leq 10^4,0\le N, p\leq 10^9+9\)。
这里介绍用爆搜 \(p\) 为奇素数的做法，也就是 Cipolla 算法。
对于二次剩余解方程 \(x^2 = n\)。找到一个 \(w\) 满足 \(w^2 - n\) 是非二次剩余（由于二次剩余的数量是 \(\frac{p - 1}{2}\)，通过随机检验的方式期望 \(2\) 次可以找到这样一个 \(w\)）。接下来定义 \(i^2 = w^2 - n\)（ \(i^2\) 不是二次剩余）。类似实数域复数域的定义，定义 \(i\)，所有数可表示为 \(A + Bi\) 的形式（\(A, B\) 是模 \(p\) 意义下的数，类似实部和虚部）。
引理 1
\[i^p \equiv -i\]
证明
\[i^p = i(i^2)^{\frac{p - 1}{2}} \equiv i(w^2 - n)^{\frac{p - 1}{2}} \equiv -i\]
引理 2
\[(A + B)^p \equiv A^p + B^p\]
证明
二项式定理展开，由于 \(p\) 是素数，除 \(C_p^0, C_p^p\) 外的组合数分子上的阶乘无法消去，模 \(p\) 都会为 \(0\)，剩下 \(C_p^0 A^p B^0 + C_p^p A^0 B^p\)。
利用上述结论：
\[ (a + i)^p = (a^p + i^p)(a + i) = (a - i)(a + i) = a^2 - i^2 = n\]
那么 \((a + i)^{\frac{p + 1}{2}}\) 是一个解，其相反数是另一个解。
验证 \((a + i)^{\frac{p + 1}{2}}\) 的虚部一定为 \(0\) ：假设存在 \((A + Bi)^{\frac{p + 1}{2}} \equiv n\) 且 \(B \neq 0\)，则 \((A + Bi)^p = A - Bi\)，乘上 \((A + Bi)\) 得 \(A^2 + B^2 = n\)， \(-2ABi = 0\)。式子左边虚部为 \(0\)，则 \(AB = 0\)。
若 \(B \neq 0\)，则 \(A = 0\)，即 \((Bi)^2 \equiv n\)，但 \(i^2\) 不是二次剩余，矛盾。
故 \(B = 0\)， \((A + Bi)^{\frac{p + 1}{2}}\) 是二次剩余，乘上二次剩余 \(n\) 后仍为二次剩余，不会产生矛盾。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65 | #include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
mt19937 rnd(time(0));
ll n, p, imag2;
struct cmpx
{
ll a, b;
cmpx(ll a = 0, ll b = 0) : a(a % p), b(b % p) {}
};
cmpx operator+(const cmpx x, const cmpx y)
{
return cmpx(x.a + y.a, x.b + y.b);
}
cmpx operator*(const cmpx x, const cmpx y)
{
return cmpx(x.a * y.a + x.b * y.b % p * imag2, x.b * y.a + x.a * y.b);
}
ll qpow(ll a, ll b)
{
static ll res;
for (res = 1; b; b >>= 1, a = a * a % p)
if (b & 1) res = res * a % p;
return res;
}
cmpx qpow(cmpx a, ll b)
{
static cmpx res;
for (res = 1; b; b >>= 1, a = a * a)
if (b & 1) res = res * a;
return res;
}
bool eularchk(ll x) { return qpow(x, (p - 1) >> 1) == 1; }
bool cipolla(ll n, ll &x1, ll &x2)
{
if (!eularchk(n)) return false;
ll a = rnd() % p;
while (!a || eularchk(imag2 = ((a * a % p - n) % p + p) % p)) a = rnd() % p;
x1 = qpow(cmpx(a, 1), (p + 1) >> 1).a;
x2 = p - x1;
return true;
}
void solve()
{
ll x1, x2;
cin >> n >> p;
if (!n)
cout << 0 << endl;
else if (!cipolla(n, x1, x2))
cout << "Hola!" << endl;
else
{
if (x1 > x2) swap(x1, x2);
cout << x1 << " " << x2 << endl;
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) solve();
return 0;
}
|