二次剩余
定义
对于同余方程 \(x^2 \equiv n \pmod p\) 有解，则称 \(n\) 为二次剩余，否则 \(n\) 为非二次剩余，其中 \(p\) 为奇素数。
欧拉准则
用于判断一个数 \(n\) 是否为二次剩余。
当 \(n^{\frac{p-1}{2}} \equiv 1\) 时，\(n\) 为二次剩余；否则为非二次剩余。
由费马小得 \(n^{p - 1} \equiv 1\pmod p\)，所以 \(n^{\frac{p-1}{2}} \equiv\) \(1\)或\(-1\)。
设 \(n \equiv g^k\)，\(g\) 为 \(p\) 的原根，那么 \(g^{k * \frac{p - 1}{2}} \equiv 1\)，所以必有\(p-1|k*\frac{p-1}{2}\)，所以 \(k\) 为偶数，有\(g^{\frac{k}{2}}\)存在，所以\(n\)为二次剩余。
若\(n\)为二次剩余，那么带入解得\(n^{\frac{p-1}{2}}\equiv (x^2)^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1\)。
所以二者等价。
Cipolla
用于求解方程，我们找到一个\(x\)使得\(x^2 - n\)是非二次剩余，设 \(i^2 \equiv x^2 - n\)，类似于复数的定义。
由定义得 \(i^p\equiv i (i^2)^{\frac{p - 1}{2}}\equiv -i\)，\((a+b)^p\equiv a^p + b^p\)
则\((x + i)^{p+1} \equiv (x+i)(x^p + i^p)\equiv x^2 - i^2 \equiv n\)
所以\((x+i)^{\frac{p+1}{2}}\)和其相反数为方程两解。
Code
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<ctime>
#define IN inline
#define LL long long
using namespace std;
int n, P, T; LL C;
IN int read() {
int t = 0,res = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) t |= (ch == '-');
for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
return t ? -res : res;
}
struct CP{
LL x, y;
CP operator * (const CP &z) const{
return CP{(x * z.x % P + y * z.y % P * C % P) % P, (x * z.y % P + y * z.x % P) % P};
}
};
LL fpow(int x, CP y) {
CP res = CP{1, 0};
for (; x; x >>= 1, y = y * y)
if (x & 1) res = res * y;
return res.x;
}
bool check(LL x){return fpow(P - 1 >> 1, CP{x, 0}) == 1;}
int main() {
srand(time(NULL)), T = read();
for (; T; T--) {
n = read(), P = read();
if (!n){puts("0"); continue;}
if (!check(n)){puts("Hola!"); continue;}
LL x = rand() % P;
while (!x || check((x * x % P - n + P) % P)) x = rand() % P;
C = (x * x % P - n + P) % P;
LL ans = fpow(P + 1 >> 1, CP{x, 1});
if (P - ans < ans) ans = P - ans;
printf("%lld %lld\n", ans, P - ans);
}
}