更新日志：
- 2023/10/15：发布文章
一、前置芝士
- 勒让德符号：
介绍
\((\frac n p) = \begin{cases} 1 & n为二次剩余 & 记作QR\\ 0&n\equiv0(mod\ p) &记作0\\-1&n不为二次剩余&记作NR\end{cases}\)
- \((n-p)^2\equiv n \mod p\)
证明
\((n-p)^2 = n^2 - 2np+p^2 = n^2+p(p-2n)\equiv n^2(mod\ p)\)
反映在表上即上下对称
- \(n^{p-1}\equiv 1\mod\ p~~~(p,n)\) 互质——
费马小定理
\({(n^2)}^{p-1} \equiv 1(mod\ p)\\ (n^{p-1})^2 - 1^2\equiv0(mod\ p)\\(n^{\frac{p-1}2}+1)(n^{\frac{p-1}2}-1)\equiv 0 \mod p\)
- 欧拉准则
介绍
若 \(p\) 为奇素数，则 \(a^{\frac{p-1}2} = (\frac{a}{p})\)
证明：不会，没学原根QaQ~
- 二项式定理
拓展 & 证明
\[(a+b)^p \mod p = a^p + b^p \]证明：
\((a+b)^n = \sum_{i=1}^{n} C_n^i\times a^i\times b^{n-i}\)
又因为：
\(\forall i\in (0,n) 且i \in\Z,C_n^i\mod n = 0\)
所以说:
\((a+b)^p \mod p = C_p^0\times a^p + C_p^p\times b^p = a^p + b^p\)
二、应用范围
二次剩余常用来求解 \(x^2 \equiv n\mod p\)，给出 \(n,p(p\in \{奇素数\})\) 求 \(x\) 的问题中
即对 \(p\) 进行 \(\bmod p\) 意义下的开根
如果说
\(\begin{cases}\exists x\in \mathbb{N^*},x^2\equiv n \mod p& n\text{为二次剩余} \\ \not\exists x\in\mathbb{N^*},x^2\equiv n \mod p & n\text{不为二次剩余}\end{cases}\)
举个栗子
在 \(\bmod 7\) 意义下
| \(a\) | \(a^2\) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 4 |
| 3 | 2 |
| 4 | 2 |
| 5 | 4 |
| 6 | 1 |
\(\therefore \sqrt 0 = 0\ \ \ \ \ \ \sqrt 1=1,6 \ \ \ \ \ \ \sqrt 2 = 3,4\ \ \ \ \ \ \sqrt 4 = 2,5\)
其他的没有
三、算法流程
首先随机 \(a\in \mathbb{Z}\),
然后我们使用 欧拉准则 \(_{声明4}\) 验证 \((\frac{a^2-n}{p})\) 是否等于 \(-1\)。
**注：期望为 \(O(2)\)，因为 \((\frac {i} {p}) = -1\) 的数量为 \(\frac{p}{2}\) **（证明？后面补，逃）
我们令 \(i = \sqrt{a^2-n}\)，（此处的 \(i\) 类似于复数 \(\mathbb{C}\)，但并不是！）
可以求出答案即为：
\[\begin{cases}x_1 = (a+i)^{\frac{p+1}2} \\ x_2 = -(a+i)^{\frac{p+1}2}\end{cases} \]证明
\((a+i)^{p+1}\)
$ = (a+i)(a+i)^p$
\(=(a+i)(a^p+i^p)\)……二项式定理\(_{声明5}\)
\(=(a+i)(a - i)\)……费马小定理\(_{声明3}\)+\((\frac{a^2-n}{p}) = {(i^2)}^{\frac{p-1}{2}} = i^{p-1}=-1\)
\(= a^2 - i^2\)
\(= a^2-(a^2-n) = n\)
最后：如何把 \(i\) 这个可恶的东西计算进去？
可以像复数计算一样计算 \(a+i\) ,只需要建一个虚数类即可
可以证明最后的最后计算出来的数不包含 \(i\) 又不会，QAQ
四、代码实现
typedef long long ll;
ll t,n,p,w;
struct Num{
ll x,y;
Num operator * (const Num &b) const{
Num res;
res.x=((x*b.x%p+y*b.y%p*w%p)%p+p)%p;// x = a.x*b.x + a.y*b.y*w
res.y=((x*b.y%p+y*b.x%p) %p+p)%p;// y = a.x*b.y + a.y*b.x
return res;
}
};
ll qpow_r(ll x,ll k){
ll res = 1,c = x;
while(k){
if(k&1)res = res * c % p;
c = c * c % p;
k >>= 1;
}
return res;
}
ll qpow_i(Num a,ll b,ll p){
Num res = {1,0};
while(b){
if(b&1) res = res * a;
a = a * a;
b >>= 1;
}
return res.x % p;
}
ll cipolla(ll n,ll p){
n %= p;
if(qpow_r(n,(p-1)/2)==p-1) return -1;
ll a;
while(1){
a = rand()%p;
w = (((a*a)%p-n)%p+p)%p;
if(qpow_r(w,(p-1)/2) == p-1)break;
}//找一个类复数
Num res = {a,1};
return qpow_i(res,(p+1)/2,p);
}
int main(){
srand(time(0));
t = read();
while(t--){
n = read(); p = read();
if(!n){
printf("0\n");continue;
}
ll ans1 = cipolla(n,p),ans2 = -ans1 + p;
if(ans1 == -1)puts("Hola!");
else{
if(ans1 > ans2)swap(ans1,ans2);
if(ans1 == ans2)printf("%lld\n",ans1);
else printf("%lld %lld\n",ans1,ans2);
}
}
}