\(Cipolla\)好像是个很厉害的东西……虽然我觉得这东西直接用离散对数+\(bsgs\)艹过去也可以……

如无特殊说明，以下均默认\(p\)为模数，且\(p\)为奇素数

如无特殊说明，以下均认为运算在\(\mathbb{F}_p\)下进行（元素为\(0\)到\(p-1\)这\(p\)个元素，运算为模\(p\)意义下的加减乘除）

定义

二次剩余

对于\(P,n\)，若存在\(x\)，满足

\[x^2\equiv n\pmod{p}\]

则称\(n\)为模\(P\)意义下的二次剩余

用人话说就是\(n\)在模\(p\)意义下是否能开方

勒让德符号

定义如下

\[ \left(\frac{n}{p}\right)= \begin{cases} 1,&n\text{在模$p$意义下是二次剩余}\\ -1,&n\text{在模$p$意义下是非二次剩余}\\ 0,&n\equiv0\pmod p \end{cases} \]

欧拉判别准则

对于勒让德符号，有

\[\left({n\over p}\right)\equiv n^{p-1\over 2}\pmod{p}\]

证明：

若\(n\equiv 0\pmod{p}\)，显然该柿子成立

若\(n\)在模\(p\)意义下是二次剩余，即存在\(x^2\equiv n\pmod{p}\)，那么就有\(x^{p-1}\equiv 1\pmod{p}\)，根据费马小定理显然\(x\)存在

若\(n\)在模\(p\)意义下是二次非剩余，我们仍假设存在\(x^2\equiv n\pmod{p}\)，从而有\(x^{p-1}\equiv -1\pmod{p}\)，由费马小定理，显然\(x\)不存在

定理们

• 定理一：

\[n^2\equiv (p-n)^2\pmod{p}\]

• 证明：把后面的平方展开即可

• 定理二：\(p\)的二次剩余和二次非剩余的个数均为\({p-1\over 2}\)（不考虑\(0\)）的情况下

• 证明：我们只考虑所有的\(n^2\)，假设有\(x\neq y\)且\(x^2\equiv y^2\pmod{p}\)，则\(p\mid (x^2-y^2)\)，即\(p\mid (x-y)(x+y)\)，显然\(p\nmid(x-y)\)，则\(p\mid(x+y)\)，故\(x+y\equiv 0\pmod{p}\)，就是定理一的情况。也就是说不同的\(x^2\)共有\({p-1\over 2}\)，二次剩余也为\({p-1\over 2}\)，减一减就可知二次非剩余个数也是\({p-1\over 2}\)

算法流程

先写过程再来证明好了……

简单来说就是我们需要对一个数开方（根据定理\(1\)显然有解的情况下必定有\(2\)个解，下面算法求出的是其中随机一个解，另一个只要用\(p-n\)计算即可）

\(1.\)判断给定的数\(x\)是否是二次剩余，如果不是就返回\(-1\)表示无解（如果是\(0\)的话直接返回\(0\)）

\(2.\)随机一个\(a\)，使其满足\((a^2-x)\)是二次非剩余（根据定理\(2\)，期望随机次数\(2\)次）

\(3.\)令\(\omega\equiv (a^2-x)\pmod{p}\)，取\(y\equiv \left(a+{\omega}\right)^{p+1\over 2}\)即为其中一个可行解，返回即可

证明

虽然上面这个算法流程简直漏洞百出……但是神奇的是它的确是对的

第一个问题，你不是都说了\((a^2-x)\)是二次非剩余么？就是说\((a^2-x)\)在模\(p\)意义下是不能开方的，那\(\omega\)是个什么东西？

关于这个问题，我们可以类比一下虚数单位元\(i=\sqrt{-1}\)，即我们需要把这个域给扩充一下，将其扩充为\(\mathbb{F}_{p^2}\)，其中的每一个元素都形如\(a+b\omega\)

我们把复数域上的四则运算全都扔到\(\mathbb{F}_{p^2}\)上面，显然满足封闭性、交换律、结合律以及分配律，还存在加法零元和乘法逆元（貌似符合环的定义）（有兴趣的可以看看下面这张图）

所以理论上来说这个开方的确是没有问题的……

第二个问题，为什么\(y\)就是一个可行的解呢？

这个问题，我们先需要一些定理

• 定理三：

\[\omega^p\equiv -w\pmod{p}\]

• 证明：

\[\omega^p\equiv \omega\omega^{p-1}\equiv \omega(\omega^2)^{p-1\over 2}\equiv \omega(a^2-x)^{p-1\over 2}\equiv -\omega\pmod{p}\]

• 定理四：

\[(a+b)^n\equiv a^n+b^n\pmod{p}\]

• 证明：二项式定理展开，对于每一项前面的组合数\({p\choose i}\)，因为\(p\)是奇素数，所以只有当\(i=0\)或\(i=p\)时它没有\(p\)这个因子，化简之后可得

然后就是大力颓柿子的时间~~~

\[ \begin{aligned} x^2&\equiv(a+\omega)^{p+1}\\ &\equiv(a+\omega)^p(a+\omega)\\ &\equiv(a^p+\omega^p)(a+\omega)\\ &\equiv(a-\omega)(a+\omega)\text{（注意$a$是满足费马小定理的，即$a^{p-1}\equiv1\pmod p$）}\\ &\equiv a^2-\omega^2\\ &\equiv a^2-(a^2-n)\\ &\equiv n\pmod p \end{aligned} \]

最后一个问题，我们需要的解是在\(\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\)）

参考文献

https://blog.csdn.net/a_crazy_czy/article/details/51959546

https://en.wikipedia.org/wiki/Cipolla%27s_algorithm