大佬教程收集整理的这篇文章主要介绍了二次剩余，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
(text{Problem}:)【模板】二次剩余
(text{Solution}:)
本文介绍 (text{Cipolla}) 算法，下面默认模数 (p) 为奇质数。
定义：
非零数 (n) 是模 (p) 的二次剩余，当且仅当模 (p) 意义下方程 (x^{2}equiv n) 有解。无解情况对应的 (n) 称为非二次剩余。
解的数量：
模 (p) 意义下的二次剩余有 (dfrac{p-1}{2}) 个，非二次剩余有 (dfrac{p-1}{2}) 个。
证明：
显然，如果模 (p) 意义下 (x^{2}equiv n) 有解，那么当 (xin[1,dfrac{p-1}{2}]) 时可以取到所有 (n)。现在只需证明当 (xin[1,dfrac{p-1}{2}]) 时，(x^{2}text{ mod }p) 互不相同。
假设存在 (x,yin[1,dfrac{p-1}{2}],xnot=y) 满足 (x^{2}equiv y^{2}pmod p)，则有 ((x+y)(x-y)equiv 0pmod p)。而 (x-ynot=0,x+ynot=0)，故假设不成立，原命题得证。
欧拉判别准则：
若 (n) 是模 (p) 意义下的二次剩余，当且仅当 (n^{frac{p-1}{2}}equiv1pmod p)。
若 (n) 是模 (p) 意义下的非二次剩余，当且仅当 (n^{frac{p-1}{2}}equiv -1pmod p)。
证明：
由费马小定理，有 (n^{p-1}equiv 1pmod p)，即 ((n^{frac{p-1}{2}}-1)(n^{frac{p-1}{2}}+1)equiv 0 pmod p)。故有：
若 (n) 是模 (p) 意义下的二次剩余，有 (n^{frac{p-1}{2}}equiv (x^{2})^{frac{p-1}{2}}equiv x^{p-1}equiv 1pmod p)。
若 (n^{frac{p-1}{2}}equiv 1pmod p)，设 (a) 是 (p) 的一个原根，则存在 (kin[1,p-1])，使得 (nequiv a^{k}pmod p)，有：
即 (p-1mid dfrac{k(p-1)}{2})，得出 (k) 为偶数。令 (j=dfrac{k}{2},jin z)，满足 ((a^{j})^2equiv npmod p)，即 (n) 是模 (p) 意义下的二次剩余。
由以上证明，(n) 是模 (p) 意义下的二次剩余，与 (n^{frac{p-1}{2}}equiv 1pmod p) 等价。原命题得证。
(text{Cipolla}) 算法：
随机一个数 (a) 满足 (a^{2}-n) 是模 (p) 意义下的非二次剩余。期望约 (2) 次即可找到满足条件的 (a)。
定义 (i^{2}equiv a^{2}-npmod p)，使得所有数可以用 (A+Bi) 的形式表达（可以借助复数域理解）。
引理 (1)：
证明：
引理 (2)：
证明：
现在开始推导 (n) 的变换，有：
由于 (p+1) 是偶数，所以存在 (X)，满足 (x^2equiv nequiv (a+i)^{p+1}pmod p)。利用快速幂即可在 (O(log p)) 的时间复杂度内求解。
#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#definE int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_BACk
#define eb emplace_BACk
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std;
inlinE int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,P,I2;
inlinE int ksc(int x,int p) { int res=1; for(;p;p>>=1, x=1ll*x*x%p) if(p&1) res=1ll*res*x%P; return res; }
struct Node
{
int x,y;
};
inline Node operator + (Node a,Node b) { return (NodE){a.x+b.x,a.y+b.y}; }
inline Node operator - (Node a,Node b) { return (NodE){a.x-b.x,a.y-b.y}; }
inline Node operator * (Node a,Node b) { return (NodE){(1ll*a.x*b.x%P+1ll*a.y*b.y%P*I2%p)%P,(1ll*a.x*b.y%P+1ll*a.y*b.x%p)%P}; }
inline bool check(int X)
{
return ksc(x,(P-1)/2)==1;
}
inlinE int Rand()
{
int w=1ll*rand()*rand()%P;
w+=rand()-rand();
w=(w%P+p)%P;
return w;
}
inline Node KSC(Node x,int p)
{
Node res=(NodE){1,0};
for(;p;p>>=1, x=x*X) if(p&1) res=res*x;
return res;
}
inline void Solve()
{
n%=P;
int a=0;
if(!n) { puts("0"); return; }
if(!check(n)) { puts("Hola!"); return; }
while(check((1ll*a*a%P-n+p)%p)) a=Rand();
I2=(1ll*a*a%P-n+p)%P;
int X1=KSC((NodE){a,1},(P+1)/2).x;
int X2=P-X1;
if(X1>x2) swap(X1,x2);
if(X1==x2) printf("%dn",X1);
else printf("%d %dn",X1,x2);
}
signed main()
{
srand(time(NULL));
for(ri int T=read();T;T--)
{
n=read(), P=read();
Solve();
}
return 0;
}
以上是大佬教程为你收集整理的二次剩余全部内容，希望文章能够帮你解决二次剩余所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。