问题描述

给定一个式子\(x^2 \equiv n \pmod p\)，求\(x\)的值。其中，如果\(x\)有解，则称\(n\)为\(p\)的二次剩余。

勒让德符号

首先，我们要先判断这个方成是否有根。在这里我们引入勒让德符号来进行判断。我们定义：

\[ \left( \frac{a}{p} \right) = \begin{cases} 1, a 为 p 的二次剩余 \\ -1, a 不是 p 的二次剩余 \\ 0, a \equiv 0 \pmod p \end{cases} \]

如何用运算来进行判别呢，接下来我们引入欧拉判别法：对于勒让德符号，有

\[ \left( \frac{a}{p} \right) = a^{\frac{p-1}{2}} \pmod p \]

证明：分类讨论以下几种情况

• 当\(\left( \frac{a}{p} \right) \equiv 1 \pmod p \)时，转化式子为\(\sqrt{ a^{p-1} } \equiv 1 \pmod p\)，根据费马小定理，得证。
• 当\(\left( \frac{a}{p} \right) \equiv -1 \pmod p\)时，二次剩余不存在。化简为\( a^{\frac{p-1}{2}} \equiv -1 \pmod p\)，不存在二次剩余时存在\(ij \equiv a \pmod p, i != j, i, j \in [1, p-1]\)。可以知道在数论中，有一共\(\frac{p-1}{2}\)对这样的\((i,j)\)，所以勒让德式可进一步转换为\( (p-1)! \equiv -1 \pmod p \)，根据威尔逊定理，得证。

Cipolla 算法

讲完了上面玄学判别式之后，我们来引进能计算二次剩余的 Cipolla 算法。首先，就像所有的二次方程一样，我们先需要验根，根据上面的判别法计算即可。之后，我们随机枚举一个\(c\)，满足\(c^2-n\)的勒让德符号为\(-1\)，并且设\(i=\sqrt{c^2-n}\)进行强行开根号（有点类似于虚数）。然后以下引理可以得出答案。

\[ x \equiv (n+i)^{\frac{p+1}{2}} \pmod p \]

证明：

\[ \begin{aligned} x^2 & \equiv (n+i)^{p+1} \\ & \equiv (n+i)(n+i)^p \\ & \equiv (n+i)(n^p+i^p) \\ & \equiv (n+i)(n^p + (c^2-n)^{\frac{p-1}{2}} * i) \\ & \equiv (n+i)(n^p – i) \\ & \equiv (n+i)(n-i) \\ & \equiv n \end{aligned} \]

在证明中有一些简便步骤，我在这里做一个解释和证明：

• \((a+b)^n \equiv \sum^n_{i=0} C_n^i a^ib^{n-i} \equiv a^n+b^n \pmod p\)，消去中间项的原因是组合数\(C_n^i\)的存在，提供了因子\(n\)。
• 根据费马小定理，有\(a^p \equiv a \pmod p\)。