【二次剩余】Cipolla（模意义下开根）

【二次剩余】Cipolla（模意义下开根）

在学多项式求逆的时候顺便就推了一下多项式的开根，
结果毫无疑问的要用到二c次剩余，顺路就学了一下，

二次剩余

给出 n , P n,P n,P(P为奇质数)，如果存在一个 a a a 使得 a 2 ≡ n ( m o d P ) a^2equiv n pmod{P} a2≡n(modP) ，那么n在模P的意义下就是二次剩余，

CTY大佬的方法

因为这个问题是由二次开方引起的，自然，模数有已知原根 r r r，那么：
r 2 I n d r ( a ) ≡ r I n d r ( n ) ( m o d P ) r^{2Ind_r(a)}equiv r^{Ind_r(n)} pmod{P} r2Indr​(a)≡rIndr​(n)(modP)

I n d Ind Ind是离散对数里面的东西，定义为 r I n d r ( x ) ≡ x ( m o d P ) r^{Ind_r(x)}equiv x pmod{P} rIndr​(x)≡x(modP)

• 定理1：方程 a 2 ≡ n ( m o d P ) a^2equiv n pmod{P} a2≡n(modP)，只有 P − 1 2 frac{P-1}{2} 2P−1​个n使方程有解（0除外）
• 证明：可以发现，如果 I n d r ( n ) Ind_r(n) Indr​(n)为奇数的话，这个方程就无解，因为 I n d r ( n ) Ind_r(n) Indr​(n)相当于是在模P-1的意义下的，而P-1必为偶数，也就是不存在2的逆元； I n d r ( n ) Ind_r(n) Indr​(n)的取值范围为0~P-2，共有 p − 1 2 frac{p-1}{2} 2p−1​为偶数，所以只有这么多个n使方程有解。

回归主题，要求出 I n d r ( a ) Ind_r(a) Indr​(a)，也就是要求出 I n d r ( n ) Ind_r(n) Indr​(n)，

那么如何快速求出 I n d r ( n ) Ind_r(n) Indr​(n)呢？
设一个阈值 ω omega ω，那么 I n d r ( n ) Ind_r(n) Indr​(n)一定可以被表示成 a ω + b aomega+b aω+b，
也就是：
r a ω ∗ r b ≡ n ( m o d P ) r^{aomega}*r^{b}equiv n pmod{P} raω∗rb≡n(modP)
r b ≡ n ∗ ( r a ω ) − 1 ( m o d P ) r^{b}equiv n*(r^{aomega})^{-1} pmod{P} rb≡n∗(raω)−1(modP)
显然，所有的 r b r^b rb可以预处理出来，
那么，剩下的只要枚举a了，判断是否有对应的b即可，
如果 ω = n omega=sqrt{n} ω=n ​，复杂度即为： O ( n log ⁡ ( n ) ) O(sqrt{n}log(n)) O(n ​log(n))（还有求逆元）

.

对于上面的定理1，其实还有一种证明：

• 定理1：方程 a 2 ≡ n ( m o d P ) a^2equiv n pmod{P} a2≡n(modP)，只有 P − 1 2 frac{P-1}{2} 2P−1​个n使方程有解（0除外）
• 证明：考虑对于所有的a，可以平方出多少个不同的n，
  如果两个数 a , b a,b a,b他们满足 a 2 ≡ b 2 ( m o d P ) a^2equiv b^2 pmod{P} a2≡b2(modP)，那么 a 2 − b 2 ≡ 0 ( m o d P ) a^2-b^2equiv 0 pmod{P} a2−b2≡0(modP)也就是 ( a 2 − b 2 ) ∣ P (a^2-b^2)|P (a2−b2)∣P， ( a − b ) ( a + b ) ∣ P (a-b)(a+b)|P (a−b)(a+b)∣P，显然(a-b)不可能是P的倍数，所以(a+b)就肯定是P的倍数，也就是a,b也满足： a + b = P a+b=P a+b=P，
  所以能组合出的不同的n就只有 P − 1 2 frac{P-1}{2} 2P−1​个

Cipolla

介绍一个东西：勒让德符号(Legendre symbol)

定义为： ( n P ) = { 1 n在模P意义下是二次剩余 − 1 n在模P意义下是非二次剩余 0 , n ≡ 0 ( m o d P ) left(frac{n}{P}right)=begin{cases} 1& text{n在模P意义下是二次剩余}\ -1& text{n在模P意义下是非二次剩余}\ 0,&nequiv0pmod{P} end{cases} (Pn​)=⎩⎪⎨⎪⎧​1−10,​n在模P意义下是二次剩余n在模P意义下是非二次剩余n≡0(modP)​

求值也很简单：（当然你用上边的方法判定没人拦…）

• 定理2： ( n P ) ≡ n P − 1 2 ( m o d P ) left(frac{n}{P}right)equiv n^{frac{P-1}{2}} pmod{P} (Pn​)≡n2P−1​(modP)
• 证明：先证明 n P − 1 2 n^{frac{P-1}{2}} n2P−1​在模P的意义下一定为0或-1或1，
• 等于0显然，对于对于1/-1，根据费马小定理，一定有 n P − 1 ≡ 1 ( m o d P ) n^{P-1}equiv 1 pmod{P} nP−1≡1(modP)，也就是设方程 x 2 ≡ 1 ( m o d P ) x^2equiv 1pmod{P} x2≡1(modP)，x只能是1/-1，这个可以把左边的方程移项解得；
• 接下来是正确性的证明：如果 n P − 1 2 ≡ 1 ( m o d P ) n^{frac{P-1}{2}}equiv 1 pmod{P} n2P−1​≡1(modP)，令 a 2 ≡ n ( m o d P ) a^2equiv n pmod{P} a2≡n(modP)，那么 ( a 2 ) P − 1 2 ≡ n P − 1 2 ( m o d P ) (a^{2})^{frac{P-1}{2}}equiv n^{frac{P-1}{2}} pmod{P} (a2)2P−1​≡n2P−1​(modP)，也就是 a P − 1 ≡ 1 ( m o d P ) a^{P-1}equiv 1 pmod{P} aP−1≡1(modP)，显然存在至少一个a满足；
• 如果 n P − 1 2 ≡ − 1 ( m o d P ) n^{frac{P-1}{2}}equiv -1 pmod{P} n2P−1​≡−1(modP)，依旧令 a 2 ≡ n ( m o d P ) a^2equiv n pmod{P} a2≡n(modP)，那么 ( a 2 ) P − 1 2 ≡ n P − 1 2 ( m o d P ) (a^{2})^{frac{P-1}{2}}equiv n^{frac{P-1}{2}} pmod{P} (a2)2P−1​≡n2P−1​(modP)，也就是 a P − 1 ≡ − 1 ( m o d P ) a^{P-1}equiv -1 pmod{P} aP−1≡−1(modP)，显然没有a满足；

接下来，开始脑洞…（遇到看不懂的没关系继续往下看先）

首先我们先开始不停的随机，直到找到一个t，使得 ( t 2 − n n ) = − 1 left( frac{t^2-n}{n} right)=-1 (nt2−n​)=−1，（先别管为什么）找出t的期望随机次数为2，（因为有 P − 1 2 frac{P-1}{2} 2P−1​个是无解的，即每次有0.5的概率找到）

$ frac{t^2-n}{n}$是不能被开方的，那么我们就强行让它可以开方；设 ω = t 2 − n omega=sqrt{t^2-n} ω=t2−n ​（类似于 i = − 1 i=sqrt{-1} i=−1 ​），

最终的答案就是： a ≡ ( t + ω ) P + 1 2 ( m o d P ) aequiv(t+omega)^{frac{P+1}{2}}pmod{P} a≡(t+ω)2P+1​(modP)
要证明还要有两个结论：

• 定理3： ω P ≡ − ω ( m o d P ) omega^P equiv -omegapmod{P} ωP≡−ω(modP)

• 证明： ω P = ω ∗ ω P − 1 = ω ∗ ( ω 2 ) P − 1 2 = ω ∗ ( t 2 + n ) P − 1 2 = − ω omega^P=omega*omega^{P-1}=omega*(omega^2)^{frac{P-1}{2}}=omega*(t^2+n)^{frac{P-1}{2}}=-omega ωP=ω∗ωP−1=ω∗(ω2)2P−1​=ω∗(t2+n)2P−1​=−ω

• 定理4： ( a + b ) P ≡ a P + b P ( m o d P ) (a+b)^Pequiv a^P+b^P pmod{P} (a+b)P≡aP+bP(modP)

• 证明： ( a + b ) P = ∑ i = 1 P C P i a i b P − i (a+b)^P=sum_{i=1}^P C_P^ia^ib^{P-i} (a+b)P=i=1∑P​CPi​aibP−iC公式里面的质数P是无法消掉的，所以除了 C p 1 C_p^1 Cp1​和 C P P C_P^P CPP​其他的C公式都是P的倍数，会被模掉。

有了这俩，就可以证明了：（还有一个显然的结论： t P ≡ t ( m o d P ) t^Pequiv tpmod{P} tP≡t(modP)）

最后把过程写上，

• 找到t使得 ( t 2 − n n ) = − 1 left( frac{t^2-n}{n} right)=-1 (nt2−n​)=−1，设 ω = t 2 − n omega=sqrt{t^2-n} ω=t2−n ​
• 方程 a 2 ≡ n ( m o d P ) a^2equiv n pmod P a2≡n(modP)的解为 a ≡ ( t + ω ) P + 1 2 ( m o d P ) aequiv(t+omega)^{frac{P+1}{2}} pmod{P} a≡(t+ω)2P+1​(modP)

给出一道例（裸）题：
【Timus Online Judge 1132】 Square Root