给定n和奇素数p，求x满足$x^2 \equiv n ($mod$\ p)$
首先考虑有没有解，有解的n称为二次剩余，无解的n称为非二次剩余根据费马小定理，当p为质数时，满足$n^p \equiv n ($mod$\ p)$由于p是奇质数，则$n^{2\frac{p-1}{2}} \equiv 1 ($mod$\ p)$即$n^{\frac{p-1}{2}}$为1在模p意义下开根的结果，只有1和-1两种可能有欧拉准则，当$n^{\frac{p-1}{2}} \equiv 1$时，n是二次剩余，否则是非二次剩余。当n是二次剩余时，易得$x^{2\frac{p-1}{2}} \equiv x^{p-1} \equiv 1$成立，必要性得到。充分性以及非二次剩余的证明鸽了。
再考虑有解时有几个解，设两个不同的解$x_1,x_2$，则满足$x_1^2 \equivx_2^2$，即$x_1^2-x_2^2 \equiv (x_1+x_2)(x_1-x_2)\equiv 0$，由于$x_1 \neq x_2$，只有可能$x_1$和$x_2$互为相反数，由于$p$是奇数，$x_1$和$x_2$的奇偶性一定不同，因此值一定不同。所以除0外每个二次剩余都对应两个解，且这两个解互为相反数。同样的，两个相反数对应了一个二次剩余，因此在$[1,p-1]$中总共有$\frac{p-1}{2}$个二次剩余
最后考虑有解时怎么求。先找到一个a，满足$a^2-n$是非二次剩余，随机找即可，一次有$\frac{1}{2}$的概率找到令$i^2 \equiv a^2-n$有$(a+i)^{p+1} \equiv n$
- $i^p \equiv i(a^2-n)^{\frac{p-1}{2}} \equiv -i$
- $(a+b)^p \equiv a^p+b^p$ 考虑二项式定理$(a+i)^{p+1} \equiv (a^p+i^p)(a+i) \equiv (a-i)(a+i) \equiv n$那么$(a+i)^{\frac{p+1}{2}}$就是一个解由于$a^2-n$是非二次剩余，因此$i$实际不存在，但是我们可以类似复数一样定义，然后定义乘法即可计算快速幂了，定义形如$a+bi$，则$a+i$就是$a+1i$$(a+bi)(c+di) \equiv (ac+bdi^2+adi+bci)$，把$i^2$用$a^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
| ll w, n, p;
struct Complex
{
ll x, y;
Complex(int _x,int _y) : x(_x), y(_y) {}
Complex operator * (const Complex &b) const {
return Complex(((x*b.x%p+y*b.y%p*w%p)%p+p)%p,((x*b.y%p+y*b.x%p)%p+p)%p);
}
};
ll powcp(Complex a,ll b,ll p)
{
Complex ans(1,0);
while(b)
{
if(b&1) ans = ans*a;
a = a*a;
b >>= 1;
}
return ans.x;
}
ll solve(ll n,ll p)
{
n %= p;
if(p==2) return n;
if(powmod(n,(p-1)/2,p)==p-1) return -1;
ll a;
while(1)
{
a = rand()%p;
w = ((a*a%p-n)%p+p)%p;
if(powmod(w,(p-1)/2,p)==p-1) break;
}
Complex x(a,1);
return powcp(x,(p+1)/2,p);
}
srand(int(time(NULL)));
ll ans1 = solve(n,p), ans2;
if(ans1==-1) printf("Hola!\n");
else
{
ans2 = p - ans1;
if(ans1>ans2) swap(ans1,ans2);
if(ans1==ans2) printf("%lld\n",ans1);
else printf("%lld %lld\n",ans1,ans2);
}
|
上述做法由于要手写一个复数类，比较麻烦，而且常数也大，还有一种ToneLLi_Shanks算法原理鸽了
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
| ll TS(ll n, ll p)
{
if(n==0) return 0;
if(p==2) return (n&1) ? 1 : -1;
if(Pow(n, p>>1, p)!=1) return -1;
if(p&2) return Pow(n, (p+1)>>2, p);
int s = __builtin_ctzll(p^1);
ll q = p>>s, z = 2;
for(; Pow(z, p>>1, p)==1; z++);
ll c = Pow(z, q, p);
ll r = Pow(n, (q+1)>>1, p);
ll t = Pow(n, q, p), tmp;
for(int m=s, i; t!=1; )
{
for(i=0, tmp=t; tmp!=1; i++) tmp = tmp*tmp%p;
for(; i<--m; ) c = c*c%p;
r = r*c%p;
c = c*c%p;
t = t*c%p;
}
return r;
}
void solve()
{
scanf("%d%d", &n, &p);
ll ans = TS(n, p);
if(ans==-1) puts("Hola!");
else if(!ans) puts("0");
else
{
ll ans2 = p - ans;
if(ans>ans2) swap(ans, ans2);
printf("%lld %lld\n", ans, ans2);
}
}
|
补充：对于三次剩余若$p % 3 = 2$，则每个数都是三次剩余，并且有唯一解$n^{\frac{2p-1}{3}}$若$p % 3 = 1$，则有$\frac{p-1}{3}$个数是三次剩余，且每个数有三个解