【Coel.做题笔记】【旁观者…】二次剩余- Cipolla 算法

题前闲语

这周末就是省选了，甚至考场就在这个机房，可惜我并没有参加的机会。
唉，今年得好好努力了！

题目简介

给出 /(N,p/)，求解方程

/[x^2 /equiv N(/bmod ~p)
/]

多组数据。

保证 /(p/) 是奇素数。

输入输出格式

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 /(T/) 行，每行两个整数，分别是 /(N/) 和 /(p/) 。

输出格式

输出共 $T$ 行。

对于每一行输出：

若有解，则按 /(/bmod ~p/) 后递增的顺序输出在 /(/bmod~ p/) 意义下的全部解。

若两解相同，只输出其中一个。

若无解，则输出 Hola! 。

前置知识

之前学习了很多模意义下的操作，比如说离散对数（/(BSGS/)），同余方程（扩展欧几里得），同余方程组（中国剩余定理）等等。接下来看看模意义下的开方运算：二次剩余。
什么是二次剩余？
当关于 /(x/) 的同余方程

/[x^2/equiv n/ (/bmod/ p)
/]

存在解时，则称 /(x/) 为模 /(p/) 意义下的二次剩余；反之则称为非二次剩余。
以下是几个二次剩余里用到的定理与符号：

勒让德符号

这是一个关于二次剩余的符号（以下的方程特指上文提到的同余方程）。

/[/left(/frac{n}{p} /right)=/begin{cases} 1,/text{同余方程有解}//-1,/text{同余方程无解} // 0 ,n/equiv 0 /pmod p/end{cases}
/]

欧拉判别准则

欧拉：没想到吧又是我！

/[/left(/frac{n}{p}/right)/equiv n^{/frac{p-1}{2}}/ /pmod p
/]

证明略过不提其实是懒得写。
这样我们就可以用快速幂计算出勒让德符号，进而判定二次剩余是否存在了。

二次剩余的个数

在模意义之下的二次剩余数与非二次剩余数相等，即为 /(/frac{p-1}{2}/)。
比较专业的证明需要用到拉格朗日定理，这里采用一种更为简单的证明方式。

假设原方程在模意义下的两个不同解分别为 /(x_1/) 和 /(x_2/) ，由平方差公式可以知道 /(p|(x_1+x_2)(x_1-x_2)/)。
当 /(p/) 为奇素数时，会有/((x_1-x_2) /bmod p /ne 0/)，那么/((x_1+x_2) /bmod p = 0/)，也就是说 /(x_1,x_2/)互为相反数，故共有 /(/frac{p-1}{2}/) 个二次剩余。
与此同时我们也可以知道，对于每个二次剩余而言，它对应的解的个数恰好为两个。

Cipolla 算法

讲了这么多，终于到算法核心内容了。
首先我们用 rand() 求出一个 /(a/) 使得 /(a^2-n/) 为非二次剩余。由上面二次剩余个数可以知道，这个过程的期望复杂度为 /(O(2)/)。
接下来在模意义下暴力开根。定义 /(/omega ^2 /equiv a^2-n/), 类似虚数的操作，我们可以用 /(a+/omega b/) 表示这个模意义下的所有数。
此时原方程的解便是/((a+/omega)^{/frac{p-1}{2}}/) 我们来证明一下。
在模意义，解可以表示为/(x /equiv (a+/omega)^{/frac{p-1}{2}}/)。
暴力推柿子时间！
当然在推柿子之前还得来个引理：为什么不在前面全部说完
Lemma： /((a+b)^p /equiv a^p +b^p/)。用二项式定理展开以后，系数不为 /(1/) 的所有部分都会被模 /(p/) 消去，得证。
最后利用这两个引理推柿子：
/(x^2 /equiv (a+/omega)^{p-1}/)
/(/equiv (a+/omega)^p(a+/omega)/)
/(/equiv (a-/omega)(a+/omega)/) （运用Lemma）
/(/equiv a^2 – /omega ^2/)
/(/equiv a^2 – (a^2 – n)/) （运用定义）
/(/equiv n/).