二次剩余学习笔记

勒让德符号

对于一个奇质数$p$且$n\perp p$，定义勒让德符号为$(\frac np)$，其中

$$\left( \frac{n}{p} \right)=\begin{cases} 1 & n\text{ is a quadratic residue}\\ -1 & \text{Otherwise} \end{cases}$$

如何计算勒让德符号？

$$n^{\frac{p-1}{2}}=\left( \frac{n}{p} \right) \mod p$$

这样就可以快速幂计算了。

Cipolla 算法

简要描述

要求解方程$x^2\equiv n\pmod p$，首先判断$n$是否是二次剩余。

然后随机一个$a$使得$a^2-n$不是二次剩余，那么设$w=\sqrt{a^2-n}$并扩域，则$x=(a+w)^{\frac{p+1}{2}}$。

勒让德符号只能判断一个数是否是二次剩余。接下来我们介绍 Cipolla 算法以用于具体计算二次剩余。

考虑方程$x^2\equiv n\pmod p$。首先判断它是不是二次剩余。如果不是就不用求了。

考虑随机一个$a$使得$a^2-n$不是$\bmod p$意义下的二次剩余。那么设$w=\sqrt{a^2-n}$。显然$w$在$\bmod p$域（$\mathbf{F}_p$）下是不存在的，我们称它是虚数单位元。我们对其扩域，这样得到一个新的域$\mathbf{F}_{p^2}$。也就是说

$$\mathbf{F}_{p^2}=\left\{ x+y\sqrt{a^2-n}: x,y\in \mathbf{F}_p \right\}$$

我们类比复数域，定义它的加法和乘法运算。那么$\mathbf{F}_{p^2}$是否满足域的所有性质呢？容易证明是满足的。这其中可能乘法逆元要难证一点。考虑$(x_1+y_1w)(x_2+y_2w)=1$，则变成

$$(x_1x_2+y_1y_2(a^2-n))+(x_1y_2+x_2y_1)w=1$$

然后发现这个方程在$\mathbf{F}_{p}$域下是有解的。因此就证明了乘法逆元的存在。

此外，我们还可以知道

定理 1：$w^{p}=-w\pmod p$。

证明：因为$a^2-n$不是二次剩余，所以$w^{p+1}=(a^2-n)^{\frac{p+1}{2}}=-1\pmod p$。

定理 2：$(a+b)^p=a^p+b^p\pmod p$（$p$是质数）。

证明：二项式定理。

那么一通操作猛如虎：

$$\begin{aligned} (a+w)^{p+1}&=(a+w)^p(a+w)\\ &=(a^p+w^p)(a+w)\\ &=(a-w)(a+w)\\ &=a^2-w^2\\ &=n \end{aligned} \pmod p$$

因此$x=(a+w)^{\frac{p+1}{2}}$。$-x$是另一个解。并且算出来虚部的系数一定是$0$。

时间复杂度$O(\log_2p)$。随机的复杂度就忽略不计了。

代码