二次剩余 Cipolla's algorithm

定义

当存在某个 $x$，式子 $x^2\equiv a\pmod p$ 成立时，称“$a$ 是模 $p$ 的二次剩余(Quadratic residue)”

Cipolla’s algorithm

只考虑 $p$ 是奇质数的情况

二次剩余的数量

在 $[0,p)$ 中是 $\frac{p+1}{2}$，包括 $0$

证明

考虑两个不同的数 $x,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$

所以除了 $0$ 以外的数恰好两两匹配

Legendre symbol

定义勒让德符号(Legendre symbol)

$$
\left(\frac{a}{p}\right)=
\begin{cases}
1,& \text{$a$ 是模 $p$ 的二次剩余} \
-1,& \text{$a$ 不是模 $p$ 的二次剩余} \
0,& a\equiv0 \pmod p
\end{cases}
$$

Euler’s criterion

根据欧拉准则(Euler’s criterion)

若 $p$是奇质数且 $p$ 不能整除 $d$，则：

$d$ 是模 $p$ 的二次剩余当且仅当：

$$d^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$$

$d$ 是模 $p$ 的非二次剩余当且仅当：

$$d^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$$

以勒让德符号表示，即为：

$$d^{\frac {p-1}{2}}\equiv \left({\frac {d}{p}}\right){\pmod {p}}$$

证明

参考这里

算法过程

我们需要求满足 $x^2\equiv a\pmod p$ 的一个 $x$

现在我们可以 $\mathcal O(\log p)$ 地判断一个数是否是模 $p$ 的二次剩余

1.

随机一个$t$，满足 $t^2-a$ 是非二次剩余，根据前面二次剩余的分布，期望次数很小..

2.

令 $\omega=\sqrt{t^2-a}$

需要求的$x=(t+\omega)^{\frac{p+1}{2}}$

这里存两个系数 $a+b\omega$ 就可以快速幂了

证明

定理1

$$(a+b)^p\equiv a^p+b^p \pmod{p} \tag{1}$$

证明

$$
(a+b)^p=\sum_{i=0}^p\binom{p}{i}a^ib^{p-i}
$$

当 $i\ne 0$ 且 $i\ne p$，$\binom{p}{i}\equiv 0 \pmod{p}$

定理2

$$\omega^p\equiv-\omega \pmod{p} \tag{2}$$

证明

因为$t^2-a$是非二次剩余，所以

$$\omega^{p-1}=(\omega^2)^{\frac{p-1}{2}}=(t^2-a)^{\frac{p-1}{2}}\equiv-1 \pmod{p}$$

定理3

$$(a+\omega)^p\equiv a-\omega \pmod{p} \tag{3}$$

由(1),(2)显然

结论

$$
\begin{align}
x^2&=(t+\omega)^{p+1} \
&=(t+\omega)(t+\omega)^p \
&\equiv (t+\omega)(t-\omega) \pmod{p}\
&=t^2-\omega^2 \
&=t^2-(t^2-a) \
&=a
\end{align}
$$

$\omega$前的系数

根据Lagrange’s theorem我们知道 $x^2-a=0$ 在任何域中都有两个根，并且我们前面得到了这两个根都在模 $p$ 的剩余系中，所以没有$\omega$

代码

这里会返回一个较小的根

inline int Pow(ll x, int y=P-2){
    int ans=1;
    for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
    return ans;
}
inline pair<int,int> pMul(pair<int,int> x, pair<int,int> y, int f){
    return make_pair(
        (int)(((ll)x.first*y.first+(ll)x.second*y.second%P*f)%P),
        (int)(((ll)x.second*y.first+(ll)x.first*y.second)%P)
    );
}
inline int Quadratic_residue(int a){
    if(Pow(a, (P-1)/2)!=1) return -1;
    int x, f;
    do x=(((ll)rand()<<15)^rand())%(a-1)+1; while(Pow(f=((ll)x*x-a+P)%P, (P-1)/2)==1);
    pair<int,int> ans=make_pair(1, 0), t=make_pair(x, 1);
    for(int i=(P+1)/2; i; i>>=1, t=pMul(t, t, f)) if(i&1) ans=pMul(ans, t, f);
    return min(ans.first, P-ans.first);
}

启示

没有