密码学数学基础 - 扩展二次剩余 | Alice and Bobの神秘小屋

前一章中，我们主要聚焦于单一素数模数下的二次剩余问题，这为我们理解二次剩余奠定了坚实的基础。然而，在实际应用中，我们经常会遇到更复杂的情况，比如模数是合数或者有多个素因数的情况。在本章中，我们将扩展我们的视野，探讨这些更一般的二次剩余问题。

这章比较难，跟进我的步伐，Go~~~🚀

扩展模数与雅可比符号 😵‍💫

当模数为 $p^k$，其中 $p$ 是奇素数，$k \geq 1$ 时，我们可以通过扩展勒让德符号来判断一个数是否是模 $p^k$ 的二次剩余。对于一个整数 $a$ 和一个奇素数 $p$，我们定义：

$\left( \frac{a}{p^k} \right) = \left( \frac{a}{p} \right)^{k}$

其中 $\left( \frac{a}{p} \right)$ 是勒让德符号。

雅可比符号可以看作是勒让德符号的推广。对于一个整数 $a$ 和一个正整数 $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$，雅可比符号定义如下：

$\left( \frac{a}{n} \right) = \prod_{i=1}^{m} \left( \frac{a}{p_i} \right)^{k_i}$

雅可比符号具有以下性质：

$\left( \frac{a}{n} \right) = \left( \frac{a}{p_1} \right) \left( \frac{a}{p_2} \right) \cdots \left( \frac{a}{p_m} \right)$
$\left( \frac{ab}{n} \right) = \left( \frac{a}{n} \right) \left( \frac{b}{n} \right)$
二次互反律推广：对于两个正整数 $m$ 和 $n$，如果 $\gcd(m, n) = 1$，则 $\left( \frac{m}{n} \right) = (-1)^{\frac{(m-1)}{2} \cdot \frac{(n-1)}{2}} \left( \frac{n}{m} \right)$。

注意，雅可比符号的值为 $-1$ 并不一定意味着 $a$ 是模 $n$ 的二次非剩余，因为 $n$ 可能不是素数。因此，雅可比符号只能提供一个必要条件，而不是充分条件。

判断扩展模数下的二次剩余 😵

接上文雅可比符号不可以直接用来判断二次剩余，那么欧拉准则在扩展模数下也失效了，设 $p^k$ 是一个奇素数的幂，其中 $p$ 是奇素数，$k \geq 1$。对于任意整数 $a$，如果 $\gcd(a, p^k) = 1$，则：

$a^{\frac{p^k - 1}{2}} \equiv \left( \frac{a}{p^k} \right) \mod p^k$

那么如何判断 $a$ 是否是模 $p^k$ 的二次剩余呢？我们有一个结论①：

$a \text{ 是模 } p^k \text{ 的二次剩余} \iff a \text{ 是模 } p \text{ 的二次剩余}$

也就是说，如果 $a$ 是模 $p$ 的二次剩余，那么它也是模 $p^k$ 的二次剩余；反之，如果 $a$ 不是模 $p$ 的二次剩余，那么它也不是模 $p^k$ 的二次剩余。
那么实际上我们可以通过判断 $a$ 是否是模 $p$ 的二次剩余来判断 $a$ 是否是模 $p^k$ 的二次剩余。

那么对于一个合数 $n$，如果 $a$ 是模 $n$ 的二次剩余，那么 $a$ 必须是模 $n$ 的每个素因数的二次剩余。也就是说，如果 $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$ 是 $n$ 的质因数分解，那么如果 $a$ 是模 $n$ 的二次剩余，则 $a$ 必须是模每个 $p_i$ 的二次剩余。因此，我们很容易得到结论：

$a \text{ 是模 } n \text{ 的二次剩余} \implies a \text{ 是模 } p_i \text{ 的二次剩余，对于所有} i$

求解扩展模数下的二次剩余 😫

之前我们已经知道可以使用Tonelli-Shanks算法来求解模素数的二次剩余，那么对于模为 $p^k$ 以及模合数 $n$ 的二次剩余，我们又该如何求解呢？

对于模 $p^k$ 的二次剩余，我们有一个结论：如果 $a$ 是模 $p$ 的二次剩余，那么 $a$ 也是模 $p^k$ 的二次剩余。我们可以先用Tonelli-Shanks算法求解模 $p$ 的二次剩余，得到一个平方根 $x$，然后我们可以通过Hensel-lifting技术进行迭代的方法来求解模 $p^k$ 的二次剩余。

对于模合数 $n$ 的二次剩余，我们可以先将 $n$ 分解为其质因数的幂的形式 $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$，然后分别求解模每个 $p_i^{k_i}$ 的二次剩余，最后通过中国剩余定理将这些结果组合起来，得到模 $n$ 的二次剩余。

具体算法和技术的原理和证明以及实现我放到另外文章里专门讲解，请看末尾相关链接，先不展开讲解了，这里先把结论和思路讲清楚了。🤐

求解一元二次同余方程 😵💫

我们在求解正常一元二次方程的时候，都是先计算判别式 $\Delta = b^2 - 4ac$，然后根据判别式的值来判断方程的根的情况，其本质是 $\Delta$ 的平方根存在。
那么在模 $n$ 的情况下，我们也可以定义一个类似的判别式来判断一元二次同余方程 $ax^2 + bx + c \equiv 0 \mod p$ 的解的情况。我们定义判别式 $\Delta = b^2 - 4ac$，然后用Tonelli-sharks算法计算，根据 $\sqrt{\Delta}$ 是否存在，即是模 $p$ 的二次剩余来判断方程的解的情况。
然后一样使用韦达定理计算出方程的根

$\begin{align*} x_1 \equiv \frac{-b + \sqrt{\Delta}}{2a} \mod p \\ x_2 \equiv \frac{-b - \sqrt{\Delta}}{2a} \mod p \end{align*}$

当然，一样的模 $p^k$ 的情况下要使用 Hensel-lifting 技术进行迭代的方法来求解模 $p^k$ 的二次剩余，模合数 $n$ 的情况下要先分解质因数再使用中国剩余定理来组合结果。

Blum 整数和半素数 💣

Blum 整数是指形如 $n = p \cdot q$ 的整数，其中 $p$ 和 $q$ 是两个不同的素数，并且满足 $p \equiv 3 \mod 4$ 和 $q \equiv 3 \mod 4$。
半素数（又叫二素数）是指形如 $n = p \cdot q$ 的合数。

Blum 整数的性质：

对于 Blum 整数 $n$，每个二次剩余都有且仅有四个平方根。
Blum 整数$ \left( \frac{-1}{n} \right) = \left( \frac{-1}{p} \right)\left( \frac{-1}{q} \right) = 1$。
Blum 整数为模数的二次剩余可以直接套用公式来求解平方根②。 $x \equiv a^{\frac{(p-1)(q-1)+4}{8}} \mod n$

结论①②证明 😭

结论①证明 😱

首先

$a \in Z^*_{p^k} \iff \gcd(a, p^k) = 1 \iff \gcd(a, p) = 1 \iff a \in Z^*_p$

充分性：
如果 $a$ 是模 $p^k$ 的二次剩余，则 $a$ 一定是模 $p^k$ 二次剩余集合元素，所以 $\gcd(a, p^k) = 1$，因此 $\gcd(a, p) = 1$。

且$ \exists b \in Z^*_{p^k} $ 使得 $a \equiv b^2 \mod p^k$。

所以 $a \equiv b^2 \mod p$，因此 $a \in (Z^*_p)^2$。

必要性：
如果 $a \in (Z^*_p)^2$，假设 $a$ 是模 $p^k$ 的二次非剩余，那么

$\begin{align*} a^{\frac{\phi(p^k)}{2}} \equiv -1 \mod p^k \\ a^{\frac{\phi(p^k)}{2}} \equiv -1 \mod p \\ a^{\frac{p^{k-1}\phi(p)}{2}} \equiv -1 \mod p \\ a^{\frac{p-1}{2}} \equiv -1 \mod p \end{align*}$

这与 $a \in (Z^*_p)^2$ 矛盾，所以 $a$ 是模 $p^k$ 的二次剩余。