二次剩余

· · 题解

这篇题解还是经典的 Cipolla 算法，主要是本人结合了 3 篇题解后才弄懂该题，所以据我个人理解提供一个（也许）好懂的题解吧。
更好的阅读体验：blog

题目传送门
二次剩余，常被称为模意义开根，是求满足

n\equiv x^2\pmod p

的 x 的值。
当上面的方程有非 0 解时，我们称 n 是模 p 的二次剩余。如果方程无解，则称 n 是模 p 的二次非剩余。
为方便书写，引入勒让德符号：

(\frac{n}{p})=\begin{cases} 1, & \text {n是二次剩余} \\ 0, & n~\equiv0\pmod p \\ -1, & \text {n是二次非剩余} \end{cases}

欧拉准则

用于判定 n 是否是模 p 意义下的二次剩余。

当模数 p 为奇素数且与 n 互质时，据费马小定理有：n^{p-1}\equiv1 \pmod p。
则有：

n^{2(\frac{p-1}{2})}\equiv1 \pmod p (n^{\frac{p-1}{2}}+1)(n^{\frac{p-1}{2}}-1)\equiv0 \pmod p

所以，当 p 为奇素数且与 n 互质时，n^{\frac{p-1}{2}}在模 p 意义下就只可能等于 1 或 -1。
欧拉准则给出公式：

(\frac{n}{p})\equiv n^{\frac{p-1}{2}}\pmod p

也就是说，当 n^{\frac{p-1}{2}}\equiv 1 时，n 是模 p 的二次剩余，等于 -1 时则不是。
证明：我们来先来证“a 是模 p 的二次剩余”是“n^\frac{p-1}{2}\equiv1 \pmod p”的充要条件。

既然“a 是模 p 的二次剩余”是“n^\frac{p-1}{2}\equiv1 \pmod p”的充要条件，那么 n^{\frac{p-1}{2}}\equiv -1\pmod p 自然就对应着“a 是模 p 的非二次剩余”，剩下一种 n 整除 p 的情况也是正确的，所以说我们就证明了欧拉准则。

解的数量

对于方程 n\equiv x^2\pmod p 来说，取其不相等的两个解 x1 和 x2 ，那么对于 x1,x2 有：

x1^2\equiv x2^2\pmod p x1^2-x2^2\equiv 0\pmod p (x1+x2)(x1-x2)\equiv 0\pmod p

因为 x1\neq x2，(x1-x2) 在模奇素数 p 意义下不可能为 0。
所以 (x1+x2)\equiv 0，说明这个方程只有两个解且它们互为相反数。
那么，一个二次剩余对应一对模意义下不同的相反数（p 为奇素数所以相反数的奇偶性不同）。因为模 p 意义下可以找到 \frac{p-1}{2} 对非零的相反数，所以在模 p 意义下共有 \frac{p-1}{2} 个二次剩余。

Cipolla

解模数为奇素数的二次剩余方程 n\equiv x^2\pmod p 可以使用 Cipolla 算法。

算法流程：先找到一个 a 使得 a^2-n 是二次非剩余，令 i^2\equiv a^2-n\pmod p ,则 (a+i)^{\frac{p+1}{2}} 即是方程的一个解，其相反数则是另一个解。

你可能觉得上述过程有问题：既然 a^2-n 是非二次剩余，那怎么能够找到这个 i 满足 i^2\equiv a^2-n\pmod p 呢？
其实这是类似于复数的概念，这里的 i 就是我们这个复数域中的虚数单位。（如果您不会复数请点：这里）

我们对于 Cipolla 算法的结论进行证明（每一步变形的说明将写在式子后面）：

(a+i)^{p+1}=(a+i)(a+i)^p =(a+i)(a^p+i^p) =(a+i)(a-i) =a^2-i^2 =a^2-(a^2-n)=n

第一步变形：提出一个 (a+i)

第二步变形：(a+i)^p 据二项式定理展开后，其中的组合数只有 C_p^0 和 C_p^p 在模 p 意义下是有值的（其他项的阶乘上都含有 p），因此 (a+i)^p\equiv(a^p+i^p)\pmod p

第三步变形：据费马小定理 a^p\equiv a\pmod p，而i^p=i^{p-1}\times i=(a^2-n)^{\frac{p-1}{2}}\times i=-i（由 i 的定义可知）。

后面的变形都是较为自然的了。
既然有 (a+i)^{p+1}\equiv n\pmod p，那么 (a+i)^{\frac{p+1}{2}} 自然是方程的一个解了，据上述对于解的个数的分析可知其相反数就是另一个解。

实现过程中我们在 0~p 中随机一个 a 并用欧拉准则判定 a^2-n 是否为非二次剩余，因为非二次剩余的数大概是 \frac{p}{2} 的，所以期望 2 次找到。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll read() {
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}
    return x*f;
}

struct num {
    ll x;// 实部
    ll y;// 虚部(即虚数单位√w的系数)
};

ll t,w,n,p;

num mul(num a,num b,ll p) {// 复数乘法 
    num res;
    res.x=( (a.x*b.x%p+a.y*b.y%p*w%p) %p+p)%p;// x = a.x*b.x + a.y*b.y*w
    res.y=( (a.x*b.y%p+a.y*b.x%p) %p+p)%p;// y = a.x*b.y + a.y*b.x
    return res;
}
ll qpow_r(ll a,ll b,ll p) {// 实数快速幂 
    ll res=1;
    while(b) {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
ll qpow_i(num a,ll b,ll p) {// 复数快速幂  
    num res={1,0};
    while(b) {
        if(b&1) res=mul(res,a,p);
        a=mul(a,a,p);
        b>>=1;
    }
    return res.x%p;// 只用返回实数部分，因为虚数部分没了 
}
ll cipolla(ll n,ll p) {
    n%=p;
    if(qpow_r(n,(p-1)/2,p)==-1+p) return -1;// 据欧拉准则判定是否有解 

    ll a;
    while(1) {// 找出一个符合条件的a
        a=rand()%p;
        w=( ((a*a)%p-n) %p+p)%p;// w = a^2 - n，虚数单位的平方
        if(qpow_r(w,(p-1)/2,p)==-1+p) break;
    }

    num x={a,1};
    return qpow_i(x,(p+1)/2,p);
}
int main() {
    srand(time(0));
    t=read();
    while(t--) {
        n=read(); p=read();
        if(!n) {
            printf("0\n");
            continue;
        }

        ll ans1=cipolla(n,p),ans2=-ans1+p;// 另一个解就是其相反数 
        if(ans1==-1) printf("Hola!\n");
        else {
            if(ans1>ans2) swap(ans1,ans2);
            if(ans1==ans2) printf("%lld\n",ans1);
            else printf("%lld %lld\n",ans1,ans2);
        }
    }

    return 0;
}

如有讲解错误或是疑惑之处欢迎在评论区提出。