二次剩余 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);
}

启示

没有