(Cipolla)好像是个很厉害的东西……虽然我觉得这东西直接用离散对数+(bsgs)艹过去也可以……
如无特殊说明，以下均默认(p)为模数，且(p)为奇素数
如无特殊说明，以下均认为运算在(mathbb{F}_p)下进行（元素为(0)到(p-1)这(p)个元素，运算为模(p)意义下的加减乘除）
定义
二次剩余
对于(P,n)，若存在(x)，满足
则称(n)为模(P)意义下的二次剩余
用人话说就是(n)在模(p)意义下是否能开方
勒让德符号
定义如下
欧拉判别准则
对于勒让德符号，有
证明：
若(nequiv 0pmod{p})，显然该柿子成立
若(n)在模(p)意义下是二次剩余，即存在(x^2equiv npmod{p})，那么就有(x^{p-1}equiv 1pmod{p})，根据费马小定理显然(x)存在
若(n)在模(p)意义下是二次非剩余，我们仍假设存在(x^2equiv npmod{p})，从而有(x^{p-1}equiv -1pmod{p})，由费马小定理，显然(x)不存在
定理们
- 定理一：
-
证明：把后面的平方展开即可
-
定理二：(p)的二次剩余和二次非剩余的个数均为({p-1over 2})（不考虑(0)）的情况下
-
证明：我们只考虑所有的(n^2)，假设有(x eq y)且(x^2equiv y^2pmod{p})，则(pmid (x^2-y^2))，即(pmid (x-y)(x+y))，显然(p mid(x-y))，则(pmid(x+y))，故(x+yequiv 0pmod{p})，就是定理一的情况。也就是说不同的(x^2)共有({p-1over 2})，二次剩余也为({p-1over 2})，减一减就可知二次非剩余个数也是({p-1over 2})
算法流程
先写过程再来证明好了……
简单来说就是我们需要对一个数开方（根据定理(1)显然有解的情况下必定有(2)个解，下面算法求出的是其中随机一个解，另一个只要用(p-n)计算即可）
(1.)判断给定的数(x)是否是二次剩余，如果不是就返回(-1)表示无解（如果是(0)的话直接返回(0)）
(2.)随机一个(a)，使其满足((a^2-x))是二次非剩余（根据定理(2)，期望随机次数(2)次）
(3.)令(omegaequiv (a^2-x)pmod{p})，取(yequiv left(a+{omega} ight)^{p+1over 2})即为其中一个可行解，返回即可
证明
虽然上面这个算法流程简直漏洞百出……但是神奇的是它的确是对的
第一个问题，你不是都说了((a^2-x))是二次非剩余么？就是说((a^2-x))在模(p)意义下是不能开方的，那(omega)是个什么东西？
关于这个问题，我们可以类比一下虚数单位元(i=sqrt{-1})，即我们需要把这个域给扩充一下，将其扩充为(mathbb{F}_{p^2})，其中的每一个元素都形如(a+bomega)
我们把复数域上的四则运算全都扔到(mathbb{F}_{p^2})上面，显然满足封闭性、交换律、结合律以及分配律，还存在加法零元和乘法逆元（貌似符合环的定义）（有兴趣的可以看看下面这张图）
所以理论上来说这个开方的确是没有问题的……
第二个问题，为什么(y)就是一个可行的解呢？
这个问题，我们先需要一些定理
- 定理三：
- 证明：
- 定理四：
- 证明：二项式定理展开，对于每一项前面的组合数({pchoose i})，因为(p)是奇素数，所以只有当(i=0)或(i=p)时它没有(p)这个因子，化简之后可得
然后就是大力颓柿子的时间~~~
最后一个问题，我们需要的解是在(mathbb{F}_p)意义下的，而你求出的解是(mathbb{F}_{p^2})意义下的。用人话说的话，就是你确定求出的解的虚部为(0)么？
这个问题的话，首先根据拉格朗日定理，我们知道在任意一个模(p)的数域下，一个(n)次多项式最多只有(n)个根。由于(mathbb{F}_{p^2})是对数域(mathbb{F}_p)的扩充，所以(mathbb{F}_p)的两根在数域(mathbb{F}_{p^2})也一定有效。并且我们知道这里根最多只有(2)个，1所以我们求出的解必定是(mathbb{F}_p)下的根，也就是虚部为(0)
然后没有然后了，问题解决
代码
int w,a;
struct cp{
int x,y;
inline cp(R int _x,R int _y):x(_x),y(_y){}
inline cp operator *(const cp &b)const{
return cp(add(mul(x,b.x),mul(w,mul(y,b.y))),add(mul(x,b.y),mul(y,b.x)));
}
};
int ksm(R cp x,R int y){
R cp res(1,0);
for(;y;y>>=1,x=x*x)if(y&1)res=res*x;
return res.x;
}
int Sqrt(int x){
if(!x)return 0;
if(ksm(x,(P-1)>>1)==P-1)return -1;
while(true){
a=mul(rand(),rand()),w=dec(mul(a,a),x);
if(ksm(w,(P-1)>>1)==P-1)return ksm(cp(a,1),(P+1)>>1);
}
}
如果要题目的话，可以去做一下这道（(bsgs+Cipolla)）
参考文献