2023.1.16 二次剩余
问题叙述
给出 N,p，求解方程
$x^2 \equiv N $ (\(mod p\))
且保证 p 是奇素数。
算法流程
解的数量
首先，探究$x^2 \equiv N $ 这个方程解的数量，假设我们取这个方程的两个解\(x_0\)和\(x_1\)
可以得到\({x_0}^2 \equiv {x_1}^2\) ，移项得(\(x_0 - x_1\))(\(x_0 + x_1\))\(\equiv 0 (mod p)\)
因为 \(x_0 \neq x_1\)，且p是奇素数，所以\(x_0 - x_1\)在模p意义下不等于0
所以\(x_0 = -x_1\)，此方程有两个互为相反数的解
在模p意义下有\(\frac {p-1}2\)个不同的二次剩余
判断二次剩余
怎样快速判断一个数是否是模p的二次剩余？
假设n不为0
因为p是质数，可以得到\(n^{p-1} \equiv 1\)，即\((n^2)^{\frac {p-1}2} \equiv 1\)，\(\frac 12\) 次方得到\(n^{\frac {p-1}2} \equiv 1或-1\)
若$ n^{\frac{p-1}{2}} \equiv 1$ ，将 n 表示为\(g^k\)， 其中 g 是模 p 意义下的原根。
那么有 \(g^{k\frac{p-1}{2}} \equiv 1\) 由于 g 是原根，必有 \(p-1|k\frac{p-1}{2}\)，
也就是说 k 一定是偶数，那么令 \(x \equiv g^{\frac{k}{2}}\) 即是 n 开根的结果，这说明 n 是二次剩余。
反推也可以得到，所以\(n^{\frac {p-1}2} \equiv 1\)等价于是二次剩余，而-1等价于不是
Cipolla
我们随机化得到一个a，使得\(a^2 - n\)不为二次剩余。由于模p意义下有\(\frac {p-1}2\)个二次剩余，所以随机找到a的期望是2次。
定义\(i^2 = a^2-n\)，但是\(a^2 - n\)并不是二次剩余，并不能找到这样的正整数i
所以仿照复数域对实数域的定义，我们将数表示成A + Bi的形式，以下有两个引论:
引论
1 . \(i^p \equiv -i\)
\(i^p \equiv i*(i^2)^{\frac {p-1}2} \equiv i*(a^2 - n)^{\frac {p-1}2}\)，而\((a^2-n)^{\frac {p-1}2} \equiv -1\)，所以$ i*(a^2 - n)^{\frac {p-1}2} \equiv -i$
2 . \((A + B)^p \equiv (A^p + B^p)\)
对于\((A + B)^p\)，由二项式定理展开可得，C(i,p)在i = 1~p-1时都含有p因数，在模p时已经消去，所以只留下首项和末项\(A^p\)和\(B^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\)
Q1：为什么\(a^p \equiv a\)? A1:费马小定理得\(a^{p-1} \equiv 1\)，同乘以a得到
Q2：为什么\(a^2 - i^2 \equiv n\)? A2:将\(i^2 = a^2 - n\)代入可得
这样，答案为n开根，就是\((a + i)^{\frac {p+1}2}\)
对于a + i，我们采用复数乘法的方式进行快速幂，将其当成一个多项式进行乘方，记录下\(i^2 mod p\)的值w
（xa + yi) * (za + ri) = (xz + yrw) + (yz + rx)i
可得此乘法的“单位元”是1 + 0i
得到a后直接初始化为(a + 1i)代入快速幂计算即可，最后取实数部分
Q3：为什么快速幂后的复数部分一定为0？
A3：使用反证法，设存在\((A + Bi)^2 \equiv n\)且\(B\neq0\)
那么\(A^2 + 2ABi + B^2 \equiv n\)，即\(A^2 + B^{2}(a^2 - n) - n \equiv -2ABi\)
式子左侧复数为0，则右侧复数也为0，\(-2ABi \equiv 0\)
B \(\neq\) 0，所以A \(\equiv\) 0，由假设式得到\((Bi)^2 \equiv n\)，\(i^2 \equiv nB^{-2}\)
由于\(B^{-2}\)和n都是二次剩余，二次剩余的积一定是二次剩余，而i不是二次剩余，所以相互矛盾，不成立
终于完了qwq
Code
（代码实现时注意时刻取模，必要时正数处理）
#include<bits/stdc++.h>
using namespace std;
int w;
struct Inum{//复数
int a,b;
inline Inum mul(Inum x,Inum y,int p)
{
Inum z;
z.a = (1ll * x.a * y.a % p + (1ll * x.b * y.b % p) * w % p) % p;
z.a = (z.a + p) % p;
z.b = (1ll * x.a * y.b % p + 1ll * x.b * y.a % p) % p;
z.b = (z.b + p) % p;
return z;
}
};
int p,n;
inline int ksm(int base,int pts,int p)
{
int ans = 1;
for(;pts > 0;pts >>= 1,base = 1ll * base * base % p)
if(pts & 1)
ans = 1ll * ans * base % p;
return ans;
}
inline Inum ksmI(Inum base,int pts,int p)
{
Inum ans;ans.a = 1;ans.b = 0;
for(;pts > 0;pts >>= 1,base = base.mul(base,base,p))
if(pts & 1)
ans = base.mul(ans,base,p);
return ans;
}
inline bool judge(int x,int p)//检验x是不是二次剩余
{
if(ksm(x,(p - 1) >> 1,p) == 1) return 1;
return 0;
}
int main()
{
srand(time(NULL));
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&p);
if(ksm(n,(p - 1) >> 1,p) == p - 1)
{
printf("Hola!\n");//无解
continue;
}
int s = rand() % p;
while(judge(((1ll * s * s % p - n) % p + p) % p,p))
s = rand() % p;
w = ((1ll * s * s % p - n) % p + p) % p;
Inum x;
x.a = s;x.b = 1;
Inum ans = ksmI(x,(p + 1) >> 1,p);
int ret = ans.a;
if(ret != 0)
printf("%d %d\n",min(ret,-ret + p),max(ret,-ret + p));//按照模后从小到大的顺序输出
else
printf("0\n");
}
return 0;
}