浅谈二次剩余

## 写在前面 由于作者是一个初一蒟蒻，有一些地方可能存在问题，请多指教。~~喷轻点~~ 这次我将会讲的是二次剩余，目测难度提高+\~省选，不过先别怕。~~毕竟我是普及蒟蒻~~ 你以为我会先讲二次剩余吗？ ~~好吧真的会~~ # 前置芝士 ## ~~0.加 减 乘 除~~ ## 1.同余的基本芝士 右转[同余定理——百度百科](https://baike.baidu.com/item/同余定理/1212360?fromtitle=同余&fromid=1432545&fr=aladdin#3) 几句话描述，如果 $a\equiv b\pmod{p},c\equiv d\pmod{p}$，那么 $a\pm c\equiv b\pm d\pmod{p},ac\equiv bd\pmod{p},a^n\equiv b^n \pmod{p},b\equiv a\pmod{p}$ 如果$ac\equiv bc\pmod{p}$，那么 $a\equiv b\pmod{\frac{p}{\gcd(c,p)}}$ 如果$a\equiv b\pmod{m_i}$，那么 $a\equiv b\pmod{\operatorname{lcm}(m_1,m_2\cdots,m_k)}$ $a\equiv a+kp\pmod{p}(k\text{ 是整数})\text{ 所以}-1\equiv p-1\pmod{p}$ ## 2.欧拉定理 左转[欧拉定理——百度百科](https://baike.baidu.com/item/欧拉定理#2) 其实就是当$\gcd(a,p)=1$时，$a^{\varphi(p)}\equiv 1\pmod{p}$ 而费马小定理就是它的特例，因为当 $p$ 是质数时，$\varphi(p)=p-1$。 ## 3.原根 直走[原根——百度百科](https://baike.baidu.com/item/原根#1) 简单地说就是$g^i \not\equiv g^j\pmod{p},\forall 1\leqslant i,j\leqslant p-1$ 还有一些必记的原根 | $p$ | $g$ | | :-----------: | :-----------: | | $3$ | $2$ | | $5$ | $2$ | | $998244353$ | $3$ | | $1004535809$ | $3$ | | $4179340454199820289$ | $3$ | # $\text{Part\ 1}$ 基本定义 ## 二次剩余 二次剩余，就是当存在某个 $x$，式子 $x^2\equiv a\pmod{p}$ 成立时，称“$a$ 是模 $p$ 的二次剩余”，否则就称“$a$ 是模 $p$ 的二次非剩余”。 ## 勒让德符号（二次特征） 勒让德符号，写作 $(\frac{a}{p})$，定义如下： $$\left(\frac{a}{p}\right)=\left\{\begin{matrix}0 & \text{如果}a\equiv 0\pmod{p}\\ 1 & \text{如果存在整数 }x\text{，使得 }x^2\equiv a\pmod{p}\\ -1 & \text{如果不存在整数 }x\text{，使得 }x^2\equiv a\pmod{p}\end{matrix}\right.$$ 所以$a$ 是模 $p$ 的二次剩余时，$(\frac{a}{p})=1$。 拓展到 $p$ 是整数的定义是：$(\frac{a}{p})=a^{\frac{\varphi(p)}{2}}$。 ## 欧拉准则 欧拉准则，就是 $x^2\equiv a\pmod{p}\text{有解}\Leftrightarrow a^{\frac{p-1}{2}}\equiv 1\pmod{p}$。 ### 证明 ------------ $$a^{\frac{p-1}{2}}\equiv (x^2)^{\frac{p-1}{2}}\equiv x^{p-1}\pmod{p}\text{，由费马小定理可得 }x^{p-1}\equiv 1\pmod{p}\text{，所以 }a^{\frac{p-1}{2}}\equiv 1\pmod{p}$$ 定义结束！！！ # $\text{Part\ 2}$ 最基本解法 爆搜就算了吧…… 以下推理都是在 $p$ 为奇质数的前提下讨论，特判一下 $p=2$ 或 $a=0$ 的情况就好了。 $$\begin{matrix}\text{设 }g\text{ 为模 }p\text{ 意义下的原根，}g^i\equiv a\pmod{p}\\ \text{有 }g^{\frac{i(p-1)}{2}}\equiv 1\pmod{p}\\ \because g\text{ 为模 }p\text{ 意义下的原根}\\ \therefore (p-1)\mid(\frac{i(p-1)}{2})\end{matrix}$$ 此时 $i$ 一定是偶数，用 $\text{Shank's BSGS}$求解。 解完 $i$ 代入 $x=g^{\frac{i}{2}}$ 就是答案了。 $\text{Shank's BSGS}$ 的时间复杂度为$\text{O}(\sqrt{p})$，预处理原根，总复杂度$\text{O}(\sqrt{p})$。 # $\text{Part\ 3}$ 再快一点？？？ 以下推理都是在 $p$ 为奇质数的前提下讨论，特判一下 $p=2$ 或 $a=0$ 的情况就好了。 $$\text{设 }p-1=2^tk,\left(\frac{w}{p}\right)=-1,a^{-1}\text{为 }a\text{ 在}\bmod{p}\text{ 意义下的乘法逆元，由欧拉准则可得 }a^{2^tk}\equiv 1\pmod{p}$$ $$\text{解 }x^2\equiv a\pmod{p}\text{，即 }a^{-1}x^2\equiv 1\pmod{p}$$ $$\text{设 }\varepsilon_q=a^{-1}x^2_q\text{，}x_{t-1}=a^{\frac{k+1}{2}}\text{，要求 }x=x_0\text{，则 }\varepsilon_q^{2^q}\equiv 1\pmod{p}\text{，则}\varepsilon_q^{2^{q-1}}\equiv \pm1\pmod{p}$$ $$\text{若 }\varepsilon_q^{2^{p-1}}\equiv1\pmod{p}\text{，则令 }x_{q-1}=x_q$$ $$\text{否则设 }\lambda x_q=x_{q-1}$$ $$\because\varepsilon_{q-1}^{2^{q-1}}=(a^{-1}x_{q-1}^2)^{2^{q-1}}\equiv 1 \pmod{p}$$ $$\therefore \varepsilon_{q-1}^{2^{q-1}}=(a^{-1}x^2_q\lambda^2)^{2^{q-1}}\equiv1\pmod{p}$$ $$\text{又}\because\varepsilon_q^{q-1}=(a^{-1}x_{q-1}^2)^{2^{q-1}}\equiv -1\pmod{p}$$ $$\therefore \lambda^{2^q}\equiv -1\pmod{p}\text{，则 }w^{2^{t-1}k}\equiv-1\pmod{p}$$ $$\text{令 }\lambda=w^{2^{t-q-1}k}\text{即可构造出一组解}$$ $$\text{直接随机选择，时间复杂度O}(\log^2 p)$$ # $\text{Part 4}$ 扩展——$x^2\equiv a\pmod{p^n}$ 的情况 有欧拉准则 $x^2\equiv a\pmod{p^n}\text{有解}\Leftrightarrow a^{\frac{\varphi(p^n)}{2}}\equiv 1\pmod{p^n}$，方法同上。 # $\text{Part 5}$ 最快？？？——$\text{Cipolla算法}$ 以下推理都是在 $p$ 为奇质数的前提下讨论，特判一下 $p=2$ 或 $a=0$ 的情况就好了。 $$\text{设 }b^2-a=w\text{ 满足 }w\text{ 是 }p\text{ 的二次非剩余系}$$ $$\text{设 }i=\sqrt{w}\text{，定义代数系统}\left<G,+,\cdot\right>\text{，定义于此代数系统的数可以用二元组 }(r,d)\text{ 表示}$$ $$(r_1,d_1)+(r_2,d_2)=(r_1+r_2,d_1+d_2),(r_1,d_1)\cdot(r_2,d_2)=(r_1r_2+wd_1d_2,r_1d_2+r_2d_1)$$ $$\text{可以证明 }\left<G,+,\cdot\right>\text{ 为环}$$ $$\text{所以 }pi\equiv0\pmod{p}$$ $$x\equiv(b+i)^{\frac{p+1}{2}}\text{ 就是答案了}$$ $$\text{证明如下：}$$  $$\text{所以我们可以随机出一个 }b\text{，期望随机次数为 }2\text{ 次}$$ $$\text{使用快速幂求 }x\equiv(b+i)^{\frac{p+1}{2}}\text{，另一个解为 }p-x\text{，时间复杂度O}(\log p)$$ $$\text{这个就是Cipolla算法}$$ 标程： ```cpp #include<cstdio> #include<cstdlib> using namespace std; long long w; struct num{long long r,i;}; num mul(num a,num b,long long p) { return (num){((a.r*b.r%p+a.i*b.i%p*w%p)%p+p)%p,((a.r*b.i%p+a.i*b.r%p)%p+p)%p}; } long long pow(long long a,long long b,long long p) { long long ans(1); while (b) { if(b%2) ans=ans*a%p; a=a*a%p; b/=2; } return ans%p; } long long pow_complex(num a,long long b,long long p) { num ans={1,0}; while (b) { if (b%2) ans=mul(ans,a,p); a=mul(a,a,p); b/=2; } return ans.r;//此时“虚部”为0 } long long solve(long long a,long long p) { a%=p; if (p==2) return a; if (pow(a,(p-1)/2,p)==p-1) return -1;//无解（欧拉准则） long long b; do { b=rand()%p; w=((b*b-a)%p+p)%p; } while (pow(w,(p-1)/2,p)!=p-1);//循环结束后w是二次非剩余（欧拉准则） return pow_complex((num){b,1},(p+1)/2,p); } int main() { long long a,p; scanf("%lld %lld",&a,&p); if (!a) puts("0"); else { long long ans1(solve(a,p)),ans2(p-ans1); if (ans1==-1) puts("Unsolvable!"); else { if (ans1>ans2) { long long t=ans1; ans1=ans2; ans2=t; } if (ans1==ans2) printf("%lld\n",ans1); else printf("%lld %lld\n",ans1,ans2); } } } ``` # $\text{EXPart 5}$ 一般二次方程 $$\text{对于形如 }ax^2+bx+c\equiv0\pmod{p}\text{ 的方程}$$ $$\text{先配方化为 }(ax+b)^2\equiv b^2-4ac\pmod{p}$$ $$\text{可通过换元得到 }X^2\equiv b^2-4ac\pmod{p}$$ $$\text{用Cipolla算法解出 }X\text{ 的取值，然后用 }2ax+b\text{ 回带}$$ $$\text{用扩展欧几里得解线性同余方程就可以得到方程本来的解}$$ # $\text{Part 6}$ 三次剩余——$\text{Peralta Method Extension}$ $$\text{类比 Part 5 二次剩余，我们可以使用类似的方法}$$ $$\text{对于三次剩余，同样有欧拉准则}x^3\equiv a\pmod{p}\text{有解}\Leftrightarrow a^{\frac{\varphi(p)}{3}}\equiv 1\pmod{p}$$ $$\text{如果 }p\equiv -1\pmod{3}\text{，则 }x\equiv a^{\frac{2p-1}{3}}\pmod{p}\text{ 是唯一解。}$$ $$\text{先随机出一个 }b\text{ 使得 }b^3-a \text{ 是三次非剩余，即 }(b^3-a)^\frac{\varphi(p)}{3}\not\equiv 1\pmod{p}\text{ 期望次数为 }9$$ $$\text{设 }w=b^3-a,i=\sqrt[3]{w}\text{，}\bmod p\text{意义下的原根为 }g$$ $$\text{则三次单位根 }\epsilon=g^{\frac{p-1}{3}}$$ $$\text{则 }x_1\equiv(b+i)^{\frac{p^2+p+1}{3}}\pmod{p},x_2=x_1\epsilon,x_3=x_2\epsilon$$ $$\text{证明类似}$$ $$\text{记住特判 }a=0\text{ 或 }p\leq 3\text{ 的情况}$$ # $\text{Part 7}$ $k$次剩余？ $$\text{类比 Part 6，我们可以将它拓展至 }k\text{ 次剩余}$$ $$\text{先随机出一个 }b\text{ 使得 }b^k-a \text{ 是三次非剩余，即 }(b^k-a)^\frac{\varphi(p)}{k}\not\equiv 1\pmod{p}$$ $$\text{设 }i=\sqrt[k]{b^k-a}$$ $$\text{则 }x\equiv(b+i)^{\frac{\sum_{i=0}^{k-1}p^i}{k}}\pmod{p}$$ $$\text{记住特判 }a=0\text{ 或 }p\leq k\text{ 的情况}$$ 好像是对的，但我不会证明……~~反正没错过~~ # $\text{Part 8}$ $k$次剩余$\times 2$？ 这个是对的…… $$x^k\equiv a\pmod{p}$$ $$\text{设 }p\text{ 的原根是 }g,x\equiv g^y\pmod{p}$$ $$x^k\equiv(g^y)^k\equiv g^{yk}\equiv a\equiv g^{\operatorname{in}\!\operatorname d_g a}\pmod{p}$$ $$ky\equiv\operatorname{in}\!\operatorname d_g a\pmod{\varphi(p)}$$ $$\operatorname{in}\!\operatorname d_g a\text{ 就是以 }g\text{ 为底，}a\text{ 的离散对数，使用(ex)Shank's BSGS解出}$$ $$\text{化为 }ky+f\varphi(p)=\operatorname{in}\!\operatorname d_g a\text{，使用exGCD解出 }y$$ $$x\equiv g^y\pmod{p}$$ $$\Huge\color{purple}\text{完结撒花！！！}$$ # 参考资料 - [求解模奇质数意义下的二次同余方程——DZYO](https://blog.csdn.net/qq_35649707/article/details/78922508) - [寻找模质数意义下的二次剩余与三次剩余——skywalkert](https://blog.csdn.net/skywalkert/article/details/52591343) - [二次同余方程模合数的一般解法——Quack_quack](https://blog.csdn.net/Quack_quack/article/details/50189111) - [二次剩余和三次剩余相关](http://hzq84621.is-programmer.com/posts/208648.html) - [ [Note] 高次剩余 [Cipolla][Peralta][BSGS]——ukii_](https://blog.csdn.net/Estia_/article/details/88789451)