模平方根
字数 2744 2025-10-26 09:01:44

模平方根

模平方根是指求解形如 \(x^2 \equiv a \pmod{n}\) 的方程的解 \(x\)，其中 \(a\) 和 \(n\) 是整数，且 \(n > 1\)。这个问题在数论和密码学中有重要应用。下面我们从简单情况开始，逐步深入。

1. 问题定义与基本概念

若存在整数 \(x\) 满足 \(x^2 \equiv a \pmod{n}\)，则称 \(a\) 是模 \(n\) 的二次剩余，否则称为二次非剩余。模平方根就是找出所有满足条件的 \(x\)。

  • 当 \(n\) 是合数时，问题可能有多解或无解，且求解难度与 \(n\) 的分解难度相关（例如 RSA 问题）。
  • 我们首先研究模奇素数 \(p\) 的情况，再推广到模素数幂和模合数。

2. 模奇素数 \(p\) 的平方根

设 \(p\) 是奇素数，\(a\) 是模 \(p\) 的二次剩余（即勒让德符号 \(\left( \frac{a}{p} \right) = 1\)）。

特殊情况：\(p \equiv 3 \pmod{4}\)

此时 \(p = 4k + 3\)。若 \(a\) 是二次剩余，则解为：

\[x \equiv \pm a^{(p+1)/4} \pmod{p} \]

验证：由费马小定理，\(a^{(p-1)/2} \equiv 1 \pmod{p}\)，于是

\[\left( a^{(p+1)/4} \right)^2 = a^{(p+1)/2} = a \cdot a^{(p-1)/2} \equiv a \pmod{p}。 \]

例子：解 \(x^2 \equiv 2 \pmod{11}\)（11 ≡ 3 mod 4）。
计算 \(a^{(p+1)/4} = 2^{(11+1)/4} = 2^3 = 8\)，解为 \(x \equiv \pm 8 \equiv 8, 3 \pmod{11}\)。

一般情况：\(p \equiv 1 \pmod{4}\)

此时没有直接公式，常用 Tonelli–Shanks 算法（1970s）。其核心思想：

  1. 将 \(p-1\) 分解为 \(p-1 = 2^s \cdot t\)，其中 \(t\) 是奇数。
  2. 找一个模 \(p\) 的二次非剩余 \(z\)（即 \(\left( \frac{z}{p} \right) = -1\)）。
  3. 通过迭代调整指数，将问题转化为容易求解的形式。

算法步骤简述：

  • 初始化：令 \(m = s\), \(c = z^t\), \(x = a^{(t+1)/2}\), \(b = a^t\)。
  • 循环直到 \(b \equiv 1 \pmod{p}\)：
    • 找到最小的 \(k\) 使得 \(b^{2^k} \equiv 1 \pmod{p}\)。
    • 更新：

\[ x \leftarrow x \cdot c^{2^{m-k-1}}, \quad b \leftarrow b \cdot c^{2^{m-k}}, \quad c \leftarrow c^{2^{m-k}}, \quad m \leftarrow k。 \]

  • 最终 \(x\) 是一个平方根，另一个是 \(-x\)。

3. 模素数幂 \(p^k\) 的平方根

若已知模 \(p\) 的平方根，可用 Hensel 引理 提升到模 \(p^k\)。

步骤：
设 \(x_1\) 满足 \(x_1^2 \equiv a \pmod{p}\)。迭代求解 \(x_{k}\) 使得 \(x_k^2 \equiv a \pmod{p^k}\)：
假设已有 \(x_{k}\) 满足 \(x_k^2 \equiv a \pmod{p^k}\)，令 \(x_{k+1} = x_k + t p^k\)，代入模 \(p^{k+1}\)：

\[(x_k + t p^k)^2 \equiv x_k^2 + 2 t x_k p^k \equiv a \pmod{p^{k+1}}。 \]

整理得：

\[2 t x_k p^k \equiv a - x_k^2 \pmod{p^{k+1}}。 \]

两边除以 \(p^k\)（模 \(p\) 下）：

\[2 t x_k \equiv \frac{a - x_k^2}{p^k} \pmod{p}。 \]

由于 \(x_k \not\equiv 0 \pmod{p}\)，可解出 \(t\)，从而得到 \(x_{k+1}\)。

4. 模合数 \(n\) 的平方根

设 \(n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}\)。

  1. 对每个素因子幂求解 \(x_i^2 \equiv a \pmod{p_i^{k_i}}\)。
  2. 若某个模数下无解，则整个系统无解。
  3. 用中国剩余定理（CRT）组合所有 \(x_i\)，得到模 \(n\) 的解。

注意：解的数量可能为 \(0, 2^r, 2^{r+1}\) 或 \(2^{r+2}\)，具体取决于 \(a\) 模 8 和模 4 的情况（当 \(n\) 有因子 2 时需单独处理）。

5. 模 2 的幂的平方根

模 \(2^k\) 的平方根需要特殊讨论：

  • 模 2：解 \(x^2 \equiv a \pmod{2}\) 只有平凡解 \(x \equiv a \pmod{2}\)（因为 0²=0, 1²=1）。
  • 模 4：解存在当且仅当 \(a \equiv 0, 1 \pmod{4}\)。
  • 模 8：解存在当且仅当 \(a \equiv 0, 1, 4 \pmod{8}\)。
  • 模 \(2^k\)（\(k \geq 3\)）：解的存在性和形式需通过逐次提升分析。

6. 应用与复杂性

  • 在密码学中，模合数的平方根求解与 RSA 困难性相关；若 \(n\) 的分解未知，求平方根是困难的。
  • 素模下的平方根计算（如 Tonelli–Shanks）时间复杂度为 \(O(\log p)^2\)，与模幂同阶。

以上内容涵盖了模平方根从特殊到一般的求解方法。如果需要进一步了解某个具体算法（如 Tonelli–Shanks 的完整示例）或模 2^k 的详细分类，可以继续提问！

模平方根 模平方根是指求解形如 \( x^2 \equiv a \pmod{n} \) 的方程的解 \( x \)，其中 \( a \) 和 \( n \) 是整数，且 \( n > 1 \)。这个问题在数论和密码学中有重要应用。下面我们从简单情况开始，逐步深入。 1. 问题定义与基本概念 若存在整数 \( x \) 满足 \( x^2 \equiv a \pmod{n} \)，则称 \( a \) 是模 \( n \) 的 二次剩余 ，否则称为 二次非剩余 。模平方根就是找出所有满足条件的 \( x \)。 当 \( n \) 是合数时，问题可能有多解或无解，且求解难度与 \( n \) 的分解难度相关（例如 RSA 问题）。 我们首先研究模奇素数 \( p \) 的情况，再推广到模素数幂和模合数。 2. 模奇素数 \( p \) 的平方根 设 \( p \) 是奇素数，\( a \) 是模 \( p \) 的二次剩余（即勒让德符号 \( \left( \frac{a}{p} \right) = 1 \)）。 特殊情况：\( p \equiv 3 \pmod{4} \) 此时 \( p = 4k + 3 \)。若 \( a \) 是二次剩余，则解为： \[ x \equiv \pm a^{(p+1)/4} \pmod{p} \] 验证 ：由费马小定理，\( a^{(p-1)/2} \equiv 1 \pmod{p} \)，于是 \[ \left( a^{(p+1)/4} \right)^2 = a^{(p+1)/2} = a \cdot a^{(p-1)/2} \equiv a \pmod{p}。 \] 例子 ：解 \( x^2 \equiv 2 \pmod{11} \)（11 ≡ 3 mod 4）。 计算 \( a^{(p+1)/4} = 2^{(11+1)/4} = 2^3 = 8 \)，解为 \( x \equiv \pm 8 \equiv 8, 3 \pmod{11} \)。 一般情况：\( p \equiv 1 \pmod{4} \) 此时没有直接公式，常用 Tonelli–Shanks 算法 （1970s）。其核心思想： 将 \( p-1 \) 分解为 \( p-1 = 2^s \cdot t \)，其中 \( t \) 是奇数。 找一个模 \( p \) 的二次非剩余 \( z \)（即 \( \left( \frac{z}{p} \right) = -1 \)）。 通过迭代调整指数，将问题转化为容易求解的形式。 算法步骤简述 ： 初始化：令 \( m = s \), \( c = z^t \), \( x = a^{(t+1)/2} \), \( b = a^t \)。 循环直到 \( b \equiv 1 \pmod{p} \)： 找到最小的 \( k \) 使得 \( b^{2^k} \equiv 1 \pmod{p} \)。 更新： \[ x \leftarrow x \cdot c^{2^{m-k-1}}, \quad b \leftarrow b \cdot c^{2^{m-k}}, \quad c \leftarrow c^{2^{m-k}}, \quad m \leftarrow k。 \] 最终 \( x \) 是一个平方根，另一个是 \( -x \)。 3. 模素数幂 \( p^k \) 的平方根 若已知模 \( p \) 的平方根，可用 Hensel 引理 提升到模 \( p^k \)。 步骤 ： 设 \( x_ 1 \) 满足 \( x_ 1^2 \equiv a \pmod{p} \)。迭代求解 \( x_ {k} \) 使得 \( x_ k^2 \equiv a \pmod{p^k} \)： 假设已有 \( x_ {k} \) 满足 \( x_ k^2 \equiv a \pmod{p^k} \)，令 \( x_ {k+1} = x_ k + t p^k \)，代入模 \( p^{k+1} \)： \[ (x_ k + t p^k)^2 \equiv x_ k^2 + 2 t x_ k p^k \equiv a \pmod{p^{k+1}}。 \] 整理得： \[ 2 t x_ k p^k \equiv a - x_ k^2 \pmod{p^{k+1}}。 \] 两边除以 \( p^k \)（模 \( p \) 下）： \[ 2 t x_ k \equiv \frac{a - x_ k^2}{p^k} \pmod{p}。 \] 由于 \( x_ k \not\equiv 0 \pmod{p} \)，可解出 \( t \)，从而得到 \( x_ {k+1} \)。 4. 模合数 \( n \) 的平方根 设 \( n = p_ 1^{k_ 1} p_ 2^{k_ 2} \cdots p_ r^{k_ r} \)。 对每个素因子幂求解 \( x_ i^2 \equiv a \pmod{p_ i^{k_ i}} \)。 若某个模数下无解，则整个系统无解。 用中国剩余定理（CRT）组合所有 \( x_ i \)，得到模 \( n \) 的解。 注意 ：解的数量可能为 \( 0, 2^r, 2^{r+1} \) 或 \( 2^{r+2} \)，具体取决于 \( a \) 模 8 和模 4 的情况（当 \( n \) 有因子 2 时需单独处理）。 5. 模 2 的幂的平方根 模 \( 2^k \) 的平方根需要特殊讨论： 模 2：解 \( x^2 \equiv a \pmod{2} \) 只有平凡解 \( x \equiv a \pmod{2} \)（因为 0²=0, 1²=1）。 模 4：解存在当且仅当 \( a \equiv 0, 1 \pmod{4} \)。 模 8：解存在当且仅当 \( a \equiv 0, 1, 4 \pmod{8} \)。 模 \( 2^k \)（\( k \geq 3 \)）：解的存在性和形式需通过逐次提升分析。 6. 应用与复杂性 在密码学中，模合数的平方根求解与 RSA 困难性相关；若 \( n \) 的分解未知，求平方根是困难的。 素模下的平方根计算（如 Tonelli–Shanks）时间复杂度为 \( O(\log p)^2 \)，与模幂同阶。 以上内容涵盖了模平方根从特殊到一般的求解方法。如果需要进一步了解某个具体算法（如 Tonelli–Shanks 的完整示例）或模 2^k 的详细分类，可以继续提问！