二次剩余二次剩余

很早就听说过二次剩余的概念了，但由于没有一直碰到过相关的题目加上学不太明白，所以一直拖啊拖没去认真学，最近终于碰到了要用到二次剩余相关知识的题，然后滚去认真学习了一波，现写篇博客记录下所学所想。不然过几天又忘了

二次剩余在数论的研究和实际上好像有很广泛的运用，但在算法竞赛中用的不多，一般是用来求解二次同余式俗称模意义开根 \(or\)???? 判断一些有关多次同余式的解的存在性问题。
考虑到高次剩余和模数 \(p\)???? 为合数的情况比较少见我不会，这里就不多加讨论，我们只讨论 \(p\)??? 为奇素数和 \(n\neq0\)??? 的情况，\(p=1、p=2、n=0\)??? 的情况显然很好特判。
为了方便描述，我们约定，以下运算都是在模 \(p\)?????? 意义下进行的，即同余符号 \(\equiv\)??? 都省略了后面的 \({\rm mod}\ p\)???，且 \(n,x\in[1,p-1]\)?????。
定义给定一个正整数 \(p\)?????，若对于一个正整数 \(n\)????，存在整数 \(x\)??? 满足 \(x^2\equiv n\pmod p\)???，则称 \(n\)??? 是模 \(p\)??? 的二次剩余，否则称 \(n\)??? 为模 \(p\)??? 的二次非剩余（或者说非二次剩余）。
例如 \(4^2\equiv 1\pmod 5\)，因此 \(1\) 是模 \(5\) 的二次剩余。
性质性质 1???：模 \(p\)? 意义下的二次剩余 \(n\)? 一共有 \(\displaystyle\frac{p-1}2\)? 个（不包括 \(0\)??）。

证明：
直接讨论 \(n\)?????? 的数量的话感觉没啥头绪，但注意到这里的每个 \(n\)?????? 都对应着一个 \(x^2\)??????，我们可以来试试讨论 \(x^2\)??????。
显然有 \(x^2\equiv(-x)^2\)??????，而在模 \(p\)?????? 意义下，\(-x\iff p-x\)??????，因此只需讨论 \(x\in[1,\displaystyle\frac{p-1}2]\)??????，便可覆盖到所有可能的 \(n\)，既然只有 \(\displaystyle\frac{p-1}2\) 个不同的 \(x\)，那么显然最多只有 \(\displaystyle\frac{p-1}2\) 个对应的 \(n\)，接下来我们只需证明这些 \(x\) 的平方模 \(p\) 两两不相等，即可得证。
证明这种取模两两不相等的套路一般都是反证法，可以参考这篇博客对于完全剩余系的性质的证明。
假设存在不同的两个数 \(x,y\in[1,\displaystyle\frac{p-1}2]\) 且 \(x^2\equiv y^2\)，则有 \((x+y)(x-y)\equiv 0\)，显然根据 \(x,y\) 的取值范围，有 \(-p

性质 2????：两个二次剩余相乘、或者两个二次非剩余相乘，得到的仍是一个二次剩余。
性质 3?：一个二次剩余和一个二次非剩余相乘，得到的是一个二次非剩余。
性质 4：一个二次剩余的逆元也是二次剩余。

性质 2、3、4 都可由欧拉准则轻松证出，故此处证明略。

勒让德符号（Legendre Symbol）为了方便描述，我们定义勒让德符号 \(\left(\displaystyle\frac np\right)\)?????，它满足：

\[\left(\frac np\right)=\begin{cases} 1\qquad \text{n 是模 p 的二次剩余}\\ -1\quad\ \text{n 是模 p 的二次非剩余}\\ 0\qquad \text{n 是0} \end{cases} \]
欧拉准则当你要判断一个数 \(n\)?? 是不是模 \(p\)? 的二次剩余时，有：\(n\) 是模 \(p\) 的二次剩余，当且仅当 \(n^{\frac {p-1}2}\equiv 1\)????????? 。

证明：
充分性：当 \(n\) 是二次剩余时，根据费马小定理，我们有 \(n^{\frac{p-1}2}\equiv (x^2)^{\frac{p-1}2}\equiv x^{p-1}\equiv1\)，充分性得证。
必要性：假设 \(g\) 为模 \(p\) 的一个原根，则一定有某个正整数 \(k\) 满足 \(g^k\equiv n\)，我们只需要取 \(x=g^{\frac k2}\)，即可使得 \(x^2\equiv n\)，接下来只需要证明 \(k\) 是偶数即可。
当 \(n^{\frac {p-1}2}\equiv 1\) 时，我们有 \(n^{\frac{p-1}2}\equiv (g^k)^\frac{p-1}2\equiv 1\)，因为 \(g\) 是一个原根，所以当 \((g^k)^\frac{p-1}2\equiv 1\) 时一定有 \(p-1\mid k*\frac{p-1}2\)，因此 \(k/2\) 一定是个整数，即 \(k\) 一定是偶数。
也就是说，当 \(n^{\frac {p-1}2}\equiv 1\) 时，一定存在某个数 \(x\) 使得 \(x^2\equiv n\)，即 \(n\) 是一个二次剩余，必要性得证。

同时由于 \(n^{\frac {p-1}2}\)?? 不是 \(1\)?? 就是 \(-1\)??、\(n\)?? 不是二次剩余就是二次非剩余，所以 \(n\)?? 是二次非剩余和 \(n^{\frac {p-1}2}\equiv -1\)?? 也是等价的，发现这刚好符合我们上面对勒让德符号的定义，因此又有 \(n^{\frac {p-1}2}\equiv\left(\dfrac np\right)\)???。
有了欧拉准则，上面的性质 \(2\)?? 和性质 \(3\)?? 也非常好证了，这里简单地证明一下性质 \(3\)?：

证明：设 \(n_1\)? 是二次剩余，\(n_2\)? 是二次非剩余，则有 \((\frac {n_1}p)\equiv1,\ (\frac{n_2}p)\equiv-1\iff n_1^{\frac{p-1}2}\equiv1,\ n_2^{\frac{p-1}2}\equiv-1\)?，那么 \((n_1*n_2)^{\frac{p-1}2}\equiv n_1^{{\frac{p-1}2}}*n_2^{\frac{p-1}2}\equiv -1\)?，即 \(n1*n2\)? 是一个二次非剩余，得证。

Cipolla 算法可以在 \(O(\log p)\)???? 的时间内求解二次同余方程 \(x^2\equiv n\pmod p\)?????。感觉有点玄学，涉及到复数域的推广，并没有理解的很明白，但总之先记录下来吧。
算法思路
1、找到一个数 \(a\) 满足 \(a^2-n\) 是二次非剩余????。
2、定义 \(i^2\equiv a^2-n\)?????????，由于 \(a^2-n\)??????? 是二次非剩余，显然这样的 \(i\)???????? 并不存在，但我们可以像实数推广到复数域一样，把模 \(p\)??? 的实数域扩张为复数域，用 \(A+Bi\)??? 来表示这个域中的所有数（虚数单位 \(i=\sqrt{a^2-n}\)），\(A,B\) 都是模 \(p\)????? 意义下的数。
3、则有 \((a+i)^{p+1}\equiv n\)，解 \(x\) 即为 \((a+i)^{\frac{p+1}2}\)????。
正确性证明
引理 1?：\(i^p\equiv-i\)

证明：\(i^p\equiv i*(i^2)^{\frac{p-1}2}\equiv i*(a^2-n)^{\frac{p-1}{2}}\equiv-i\)。

引理 2：\((a+b)^p\equiv a^p+b^p\)

证明：二项式定理展开后，共有 \(p+1\)???????? 项，每一项都是 \({\rm C}_p^ma^mb^{p-m},~m\in[0,p]\)??? 的形式?，因为 \(p\)??? 为质数，所以除了 \(m=0\)??? 和 \(m=p\)??? 的两项，其他项的 \({\rm C}_p^m\)??? 的分子都会有一个 \(p\)?? 约不掉，这些项模 \(p\)? 都为 \(0\)?，因此最后只剩下两项：\(a^p+b^p\) ，得证。

于是我们有：

\[\begin{aligned} (a+i)^{p+1}&\equiv(a+i)^p(a+i) \\ &\equiv (a^p+i^p)(a+i) \\ &\equiv (a^p-i)(a+i) \\ &\equiv (a-i)(a+i) \\ &\equiv a^2-i^2 \\ &\equiv n \end{aligned} \]
则 \((a+i)^{\frac {p+1}2}\)???? 为方程的解 \(x\)?????，其相反数是另一个解。
但这是拓展了数域的条件下所求得的答案，这个答案在原数域下也成立吗？显然如果要使答案在原数域下也成立，所求得的数的虚部就必须为 \(0\)????，接下来证明 \((a+i)^{\frac {p+1}2}\)? 的虚部一定为 \(0\)?。

证明：
反证法，假设 \((a+i)^{\frac {p+1}2}\equiv A+Bi\)??，且 \(B\neq0\)??。
那么我们有 \((A+Bi)^2\equiv A^2+2ABi+B^2i^2\equiv n\)??，移项并把 \(i^2=a^2-n\)?? 代入得 \(A^2+B^2(a^2-n)-n\equiv-2ABi\)??。
同余式左边是常数，右边肯定也是常数，所以 \(AB\equiv 0\)??，同时因为 \(B\neq0\)??，则 \(A\equiv 0\)??，从而有 \((Bi)^2\equiv n\iff i^2\equiv nB^{-2 }\)???，因为 \(n\)??? 是二次剩余，\(B^2\)?? 是二次剩余，所以 \(nB^{-2}\)? 也是二次剩余，这与 \(i^2\)? 是二次非剩余矛盾，所以 \(B\) 一定为 \(0\)，得证。?

时间复杂度分析
如何找到这样的 \(a\)??? 满足 \(a^2-n\)??? 是二次非剩余？很简单，我们只需随机生成一个数 \(a\)???，然后用欧拉准则判断 \(a^2-n\)??? 是否为二次非剩余即可，因为二次剩余的和二次非剩余的数量都为 \(\dfrac {p-1}2\)???，所以整数域里的某个数是二次非剩余的概率约为 \(50\%\)???，因此随机的期望次数是 \(2\)?? 次，每次都用欧拉准则 \(O(\log p)\)?? 判断一下，时间复杂度是 \(O(\log p)\)???。找到了 \(a\) 以后，只需用复数域上的快速幂即可求出解，时间复杂度 \(O(\log p)\)，总时间复杂度 \(O(\log p)\)?。
代码实现
【二次剩余】模板题看这里。

Code

#include using namespace std; long long n,p; long long i; struct td{ //自定义的复数 long long x,y; td(long long xx=0,long long yy=0){ x=xx,y=yy; } td operator * (td a){ //等价于复数相乘 return td( (x*a.x+i*y%p*a.y)%p, (y*a.x+x*a.y)%p); } }; long long qsm(long long a,long long b){ a%=p; long long ret=1; while(b){ if(b&1) ret*=a,ret%=p; b>>=1,a*=a,a%=p; } return ret; } td t_qsm(td a,long long b){ td ret(1,0); while(b){ if(b&1){ ret=ret*a; } b>>=1,a=a*a; } return ret; } bool legendre(long long n){ return qsm(n,(p-1)/2)==1; } int main(){ int t; cin >> t; mt19937 mt_rand(time(0)); //随机性更好一些的随机 while(t--){ cin >> n >> p; if(n==0){ //特判0 cout <<"0\n"; continue; } if(legendre(n)){ long long a=mt_rand()%p; while(legendre(a*a-n)){ a=mt_rand()%p; } i=(a*a+p-n)%p; //相当于复数的单位根 td ans=t_qsm(td(a,1),(p+1)/2); //答案即为 (a,1)^{(p+1)/2} ans.x=min(ans.x,p-ans.x); //显然有两个答案 (x)^2 ≡ (p-x)^2 cout << ans.x << " " << p-ans.x << endl; } else cout << "Hola!\n"; } }

参考资料

二次剩余 - OI Wiki (oi-wiki.org)
https://www.luogu.com.cn/blog/zhang-xu-jia/qian-tan-er-ci-sheng-yu
https://www.luogu.com.cn/blog/Vectory/er-ci-sheng-yu
https://blog.csdn.net/acdreamers/article/details/10182281
https://blog.csdn.net/Estia_/article/details/88789451
https://baike.baidu.com/item/%E4%BA%8C%E6%AC%A1%E5%89%A9%E4%BD%99/3990744?fr=aladdin
https://kewth.github.io/2019/10/21/%E4%BA%8C%E6%AC%A1%E5%89%A9%E4%BD%99/