二次剩余

这是一个二次剩余的基本概念：

关于 $n$ 的二次剩余个数不会超过 $(n+1)/2$ ,因为$(a^2 equiv (n-a)^2 space mod space n)$。

接下来我们先讨论质数的二次剩余

对于质数2，所有的数均为它的二次剩余。

以下讨论p为奇质数的情况：

每一个奇质数都有$(p+1)/2$ 个二次剩余，有 $(p-1)/2$ 个二次非剩余，其二次剩余非别为：
$$
0^2,1^2,cdots ,(frac{p-1}{2}-1)^2,(frac{p-1}{2})^2
$$
证明过程如下：

假设$a,b(0 leq a < b leq frac{p-1}{2})$ ,$a^2 equiv b^2 equiv x space mod space p$, $c=a-b$.则：
$$
b^2 equiv (a+c)^2 equiv a^2+2ac+c^2 space mod space p \
because a^2 equiv x space mod space p \
therefore 2ac+c^2 equiv 0 space mod space p \
c(2a+c) equiv 0 space mod space p \
c(a+b) equiv 0 space mod space p \
because a+b<p ,c<p \
therefore c(a+b) equiv 0 space mod space p 不成立 \
therefore a^2 equiv b^2 equiv x space mod space p 不成立\
$$

这样就可以证明上面$frac{p+1}{2}$ 个二次剩余均不相同，且一定将所有的二次剩余全部枚举出来了。

对于一个数d是不是奇质数p的二次剩余，可以用欧拉准则来判断。

欧拉准则在此处的应用为：

如果$d^{frac{p-1}{2}} equiv 1 space mod space p$ ,则$d$是$p$的二次剩余；
如果$d^{frac{p-1}{2}} equiv -1 space mod space p$，则$d$是$p$的二次非剩余。

（具体证明我也不会）

对于式子$x^2space equiv d space (modspace p)$ ，已知$d,p$,如何求$x$ ？

具体过程为：

1. 随机一个整数 $t(1leq t <p)$ ，使得 $t^2-d$ 是 $p$ 的二次非剩余，由于二次剩余个数和二次非剩余个数五五开，因此求解出来 $t$ 的期望次数很少。

2. 令$omega=sqrt{t^2-d}$ ,则$x={(t+sqrt{omega})}^{frac{p+1}{2}}$ 。

证明如下：

对于$(t+sqrt{omega})^p$ ,当p为奇素数，根据二项式定理$(t+sqrt{omega})^p equiv (t^p+sqrt{omega} ^p) space mod space p$ ,根据费马小定理，$t^p equiv t space mod space p$，根据之前的判断方法，可知$omega^frac{p-1}{2} equiv -1 space mod space p$, 所以$sqrt{omega}^p equivomega^{frac{p-1}{2}}*sqrt{omega} equiv -sqrt{omega} space mod space p$ ，因此$(t+sqrt{omega})^p equiv (t-sqrt{omega}) space mod space p$。
此时：
$$
(t+sqrt{omega})^{p+1} equiv (t-sqrt{omega})(t+sqrt{omega}) \
equiv t^2-omega \
space space space equiv d space mod space p
$$
即：
$$
x^2 equiv (t+sqrt{omega})^{p+1} space mod space p \
x equiv (t+sqrt{omega})^{frac{p+1}{2}} space mod space p
$$

但是可以发现的一点是，$omega^{p-1}equiv (sqrt{t^2-d})^{p-1}equiv (t^2-d)^{frac{p-1}{2}} equiv -1 space mod space p$ ,$omega^pequiv -omega space mod space p$ ,这在实数域是不能实现的，换句话说，$omega$ 是复数域的一个值。因此我们不能用实数的方法去求解，需要利用复数来求解（口胡过去了，我其实也不会写，以后慢慢填坑）。

代码实现（返回较小的解）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

ll (ll x,ll y)
{
    ll res=1;
    x%=mod;
    for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;
    return res;
}
ll Quadratic_residue(const ll d)
{
    if(d==0)return 0;
    
    ll b=(rand()<<14^rand())%mod;
    while(pow(b,(mod-1)>>1)!=mod-1)b=(rand()<<14^rand())%mod;
    
    ll s=mod-1,t=0,x,inv=pow(d,mod-2),f=1;
    while(!(s&1))s>>=1,t++,f<<=1;
    t--,x=pow(d,(s+1)>>1),f>>=1;
    while(t){
        f>>=1;
        if(pow((inv*x%mod*x%mod),f)!=1)x=x*pow(b,s)%mod;
        t--,s<<=1;
    }
    return min(x,mod-x);
}