二次剩余
Contents
二次剩余用于解决在 模意义下开根 的问题：
题意
给定一个质数 $P$ 和一个非负整数 $N$，求 $x$ 使得
$$x^2 \equiv N (\text{mod } P)$$
本问题等价于求 $$\sqrt N ~(\text{mod } P)$$
性质
- 这个问题可能无解，如果有解，则有两个解，它们互为相反数。
模版
// 求 sqrt(a) 在 mod P 下的值
// 调用 solve(a, P, r1, r2)
// 若有解，r1, r2 分别为两个解，其中 r1 小，r2 大
// 若无解，r1 == -1
namespace Quadratic_residue {
ll qpow(ll a, ll b, ll P) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % P;
a = a * a % P;
b >>= 1;
}
return res;
}
bool check_if_residue(ll x, ll P) {
return qpow(x, (P - 1) >> 1, P) == 1;
}
void solve(ll a, ll P, ll& r1, ll& r2) {
if (a <= 1) {
r1 = a, r2 = P - a; return;
}
if (!check_if_residue(a, P)) {
r1 = -1; return;
}
ll x;
while (1) {
x = 1LL * rand() * rand() % P;
if (qpow((x*x-a+P)%P,(P-1)/2, P)!=1) break;
}
ll w = (x * x - a + P) % P;
pll res = {1,0}, t = {x,1};
auto Mul=[&](pll a,pll b){ // 复数乘法
ll x=(1LL * a.first * b.first + 1LL * a.second * b.second % P * w) % P;
ll y=(1LL * a.first * b.second + 1LL * a.second * b.first) % P;
return make_pair(x,y);
};
ll d = (P+1) / 2;
while (d) {
if(d & 1) res = Mul(res,t);
t = Mul(t,t);
d >>= 1;
}
ll r = (res.first % P + P) % P;
r1 = min(r, (P - r) % P);
r2 = max(r, (P - r) % P);
}
};