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

代码

这里会返回一个较小的根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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);
}

启示

没有

0%