Quadratic Residue

仅讨论模数为奇质数 $p$ 的情况。

在 $\bmod p$ 意义下，对于数 $a$ 若存在 $x$ 满足

则称 $a$ 是 $\bmod p$ 下的一个二次剩余 (quadratic residue)。特别地，我们不认为 $a = 0$ 是二次剩余，后面会解释。

感性理解：能开根号的数是二次剩余。

对于一个二次剩余 $a$，它有几个平方根？即有几个数满足 $x^2 \equiv a \pmod p$？

对于两个不相等的解 $x_1 \ne x_2$，玩一玩性质。

也就是说，若两个解不同，则它们只能是相反数。因此最多只有两个解。

对于一个非零的二次剩余 $a$，它必定存在非零解，因此有且仅有两解。这也是为什么我们不认为 $a = 0$ 也算二次剩余。

$\bmod p$ 下有几个二次剩余？几个非二次剩余？

相反数对和二次剩余形成双射，具体来说，所有的二次剩余就是 $1^2, 2^2, \cdots, (\frac {p-1} 2)^2$。因此有 $\frac {p-1} 2$ 个二次剩余。

去掉这些二次剩余，还剩 $\frac {p-1} 2$ 个非二次剩余。

Euler’s criterion

如何判断一个 $a$ 是不是 $\bmod p$ 下的二次剩余？

Euler 说：对奇质数 $p$ 和非零的 $a$，有

• $a$ 是 $p$ 的二次剩余当且仅当 $a^{\frac {p-1} 2} \equiv 1 \pmod p$。
• $a$ 是 $p$ 的非二次剩余当且仅当 $a^{\frac {p-1} 2} \equiv -1 \pmod p$。

证明

若 $a$ 是二次剩余，代入 $a \equiv x^2$：

考虑非二次剩余的情况怎么证。给 Fermat’s little theorem 变个形：

即 $a^{\frac {p-1} 2} - 1 \equiv 0$ 或 $a^{\frac {p-1} 2} + 1 \equiv 0$。

根据 Lagrange 定理，关于 $a$ 的方程 $a^{\frac {p-1} 2} - 1 \equiv 0$ 最多只有 $\frac {p-1} 2$ 个解。而我们已经发现所有二次剩余都是解，找到了 $\frac {p-1} 2$ 个解，不可能再有多的了。

也就是说，对于非二次剩余 $a$，只能 $a^{\frac {p-1} 2} + 1 \equiv 0$，即 $a^{\frac {p-1} 2} \equiv -1$。

Legendre Symbol

在 $\bmod p$ 下，已知 $a$ 是 / 不是二次剩余，$b$ 是 / 不是二次剩余。判断 $a \times b$ 是否是二次剩余？

应用 Euler’s criterion：

因此就是一个简单的 $1$ 和 $-1$ 的乘法关系：

• 二次剩余 × 二次剩余 = 二次剩余
• 非二次剩余 × 非二次剩余 = 二次剩余
• 二次剩余 × 非二次剩余 = 非二次剩余

这启发我们直接定义一个符号来描述：

它被称为 Legendre symbol，满足性质：

Euler’s criterion 也可以用它描述：

Cipolla 算法

在模奇质数下寻找二次剩余的算法。

在 $p$ 为奇质数的情况下，求解方程

\[x^2 \equiv a \pmod p\]

忽略 $a \equiv 0$ 的平凡情况，以及 $a$ 是非二次剩余的情况（利用 Euler’s criterion）。

随机一个 $r$ 使得 $r^2 - a$ 为非二次剩余（可以在期望 $2 + \frac 2 {p-1}$ 次内抽到，用 Euler’s criterion 验算）。有

此处 $\sqrt{r^2 - a}$ 是一个形式上的二次剩余，可以证明最后必定会消掉。

证明

TODO:

二次互反律 Law of Quadratic Reciprocity

一对奇质数 $p,q$，它们互相的 Legendre 符号 $\left( \frac p q \right), \left( \frac q p \right)$ 有什么关系？

Gauss 说：

对于小质数 $p$ 和大质数 $q$，$\left( \frac p q \right)$ 可以这样快速计算，把 $\bmod q$ 下的问题转化为 $\bmod p$ 下的问题：

特别地，当 $p = 2$ 时：

证明

TODO: