二次筛法
字数 2222 2025-10-30 11:52:44

二次筛法

二次筛法是一种用于大整数分解的算法，属于现代因子分解方法的重要代表。它的核心思想是利用二次同余关系构造平方差，从而通过最大公因数分解整数。下面我们逐步展开讲解。

1. 基本思想：平方差分解法

若需分解合数 \(n\)，目标是找到整数 \(x, y\) 满足：

\[x^2 \equiv y^2 \pmod{n}, \quad x \not\equiv \pm y \pmod{n} \]

则 \(\gcd(x - y, n)\) 或 \(\gcd(x + y, n)\) 很可能给出 \(n\) 的非平凡因子。
关键问题：如何高效找到这样的 \((x, y)\)？

2. 构造同余关系：多项式筛选

二次筛法选择多项式 \(Q(x) = (x + \lfloor \sqrt{n} \rfloor)^2 - n\)，计算一系列 \(x\) 对应的 \(Q(x)\) 值。
观察：当 \(x\) 接近 \(0\) 时，\(Q(x)\) 相对较小，易于分解其质因数。

3. 平滑数与因子基

定义：若一个数的所有质因子均属于预先选定的质数集合 \(B\)（称为因子基），则该数是 \(B\)-平滑的。
因子基通常选取所有小于某个上界 \(B\) 的质数（可能包括 \(-1\) 以处理负值）。
步骤：

  1. 对多个 \(x\) 计算 \(Q(x)\)，尝试完全分解其质因子。
  2. 仅保留所有质因子均属于 \(B\) 的 \(Q(x)\)（即平滑数）。

4. 线性代数阶段：指数向量模 2

对每个平滑的 \(Q(x)\)，记录其质因子分解的指数向量（模 \(2\)）。
例如：若 \(Q(x) = (-1)^a p_1^{e_1} p_2^{e_2} \dots\)，则向量为 \((a \bmod 2, e_1 \bmod 2, \dots)\)。
目标：找到若干平滑数的集合，使其指数向量之和为偶数（即模 \(2\) 下线性相关）。
这等价于这些 \(Q(x)\) 的乘积是一个完全平方数。

5. 构造平方差

设平滑数集合为 \(S\)，满足：

\[\prod_{x \in S} Q(x) = y^2 \]

同时，由 \(Q(x) = (x + \lfloor \sqrt{n} \rfloor)^2 - n\)，定义：

\[x \equiv \prod_{x \in S} (x + \lfloor \sqrt{n} \rfloor) \pmod{n} \]

则有：

\[x^2 \equiv \prod Q(x) \equiv y^2 \pmod{n} \]

此时计算 \(\gcd(x - y, n)\) 即可能得到因子。

6. 优化：筛法加速分解

直接对每个 \(Q(x)\) 分解质因数效率低。二次筛法的核心优化是使用筛法快速标记平滑数：

  • 对每个质数 \(p \in B\)，解方程 \(Q(x) \equiv 0 \pmod{p}\)（即求 \(n\) 模 \(p\) 的平方根）。
  • 在 \(x\) 的序列中，每隔 \(p\) 个位置，\(Q(x)\) 可被 \(p\) 整除。对这些位置累加 \(\log p\) 的近似值。
  • 最终，值接近 \(\log |Q(x)|\) 的 \(x\) 很可能对应平滑数，再尝试精确分解。

7. 算法复杂度

二次筛法的复杂度为：

\[L_n\left[ \frac{1}{2}, 1 \right] = e^{(1 + o(1)) \sqrt{\ln n \ln \ln n}} \]

优于试除法，但弱于数域筛法（NFS）。适用于分解数十位到百位的大整数。

8. 举例说明（简化版）

设 \(n = 1649\)，\(\lfloor \sqrt{n} \rfloor = 40\)。
取 \(Q(x) = (x+40)^2 - 1649\)：

  • \(x=0\): \(Q=1600-1649=-49=-7^2\)
  • \(x=1\): \(Q=1681-1649=32=2^5\)
    取因子基 \(B = \{-1, 2, 7\}\)，以上两个 \(Q(x)\) 均平滑。
    乘积：\((-49) \times 32 = -1568 = -1 \cdot 2^5 \cdot 7^2\)
    指数向量模 \(2\) 之和为 \((1,1,0) + (0,1,0) = (1,0,0)\)（非零，需调整？实际应选偶数次幂）。
    若直接计算：
    \(\prod Q(x) = (-7^2)(2^5)\)，非平方。但若仅用 \(x=0\)：\(Q(0) = -7^2\) 已是平方。
    此时 \(y=7\)，\(x = 40\)，\(\gcd(40-7, 1649) = \gcd(33, 1649) = 17\)，得因子 \(17\)（\(1649 = 17 \times 97\)）。

总结

二次筛法通过多项式生成平滑数，利用线性代数构造平方同余式，是大整数分解的重要实用算法。其改进版（如多重多项式二次筛）进一步提升了效率。

二次筛法 二次筛法是一种用于大整数分解的算法，属于现代因子分解方法的重要代表。它的核心思想是利用二次同余关系构造平方差，从而通过最大公因数分解整数。下面我们逐步展开讲解。 1. 基本思想：平方差分解法 若需分解合数 \( n \)，目标是找到整数 \( x, y \) 满足： \[ x^2 \equiv y^2 \pmod{n}, \quad x \not\equiv \pm y \pmod{n} \] 则 \( \gcd(x - y, n) \) 或 \( \gcd(x + y, n) \) 很可能给出 \( n \) 的非平凡因子。 关键问题 ：如何高效找到这样的 \( (x, y) \)？ 2. 构造同余关系：多项式筛选 二次筛法选择多项式 \( Q(x) = (x + \lfloor \sqrt{n} \rfloor)^2 - n \)，计算一系列 \( x \) 对应的 \( Q(x) \) 值。 观察 ：当 \( x \) 接近 \( 0 \) 时，\( Q(x) \) 相对较小，易于分解其质因数。 3. 平滑数与因子基 定义：若一个数的所有质因子均属于预先选定的质数集合 \( B \)（称为 因子基 ），则该数是 \( B \)-平滑 的。 因子基通常选取所有小于某个上界 \( B \) 的质数（可能包括 \( -1 \) 以处理负值）。 步骤 ： 对多个 \( x \) 计算 \( Q(x) \)，尝试完全分解其质因子。 仅保留所有质因子均属于 \( B \) 的 \( Q(x) \)（即平滑数）。 4. 线性代数阶段：指数向量模 2 对每个平滑的 \( Q(x) \)，记录其质因子分解的指数向量（模 \( 2 \)）。 例如：若 \( Q(x) = (-1)^a p_ 1^{e_ 1} p_ 2^{e_ 2} \dots \)，则向量为 \( (a \bmod 2, e_ 1 \bmod 2, \dots) \)。 目标 ：找到若干平滑数的集合，使其指数向量之和为偶数（即模 \( 2 \) 下线性相关）。 这等价于这些 \( Q(x) \) 的乘积是一个完全平方数。 5. 构造平方差 设平滑数集合为 \( S \)，满足： \[ \prod_ {x \in S} Q(x) = y^2 \] 同时，由 \( Q(x) = (x + \lfloor \sqrt{n} \rfloor)^2 - n \)，定义： \[ x \equiv \prod_ {x \in S} (x + \lfloor \sqrt{n} \rfloor) \pmod{n} \] 则有： \[ x^2 \equiv \prod Q(x) \equiv y^2 \pmod{n} \] 此时计算 \( \gcd(x - y, n) \) 即可能得到因子。 6. 优化：筛法加速分解 直接对每个 \( Q(x) \) 分解质因数效率低。二次筛法的核心优化是使用 筛法 快速标记平滑数： 对每个质数 \( p \in B \)，解方程 \( Q(x) \equiv 0 \pmod{p} \)（即求 \( n \) 模 \( p \) 的平方根）。 在 \( x \) 的序列中，每隔 \( p \) 个位置，\( Q(x) \) 可被 \( p \) 整除。对这些位置累加 \( \log p \) 的近似值。 最终，值接近 \( \log |Q(x)| \) 的 \( x \) 很可能对应平滑数，再尝试精确分解。 7. 算法复杂度 二次筛法的复杂度为： \[ L_ n\left[ \frac{1}{2}, 1 \right ] = e^{(1 + o(1)) \sqrt{\ln n \ln \ln n}} \] 优于试除法，但弱于数域筛法（NFS）。适用于分解数十位到百位的大整数。 8. 举例说明（简化版） 设 \( n = 1649 \)，\( \lfloor \sqrt{n} \rfloor = 40 \)。 取 \( Q(x) = (x+40)^2 - 1649 \)： \( x=0 \): \( Q=1600-1649=-49=-7^2 \) \( x=1 \): \( Q=1681-1649=32=2^5 \) 取因子基 \( B = \{-1, 2, 7\} \)，以上两个 \( Q(x) \) 均平滑。 乘积：\( (-49) \times 32 = -1568 = -1 \cdot 2^5 \cdot 7^2 \) 指数向量模 \( 2 \) 之和为 \( (1,1,0) + (0,1,0) = (1,0,0) \)（非零，需调整？实际应选偶数次幂）。 若直接计算： \( \prod Q(x) = (-7^2)(2^5) \)，非平方。但若仅用 \( x=0 \)：\( Q(0) = -7^2 \) 已是平方。 此时 \( y=7 \)，\( x = 40 \)，\( \gcd(40-7, 1649) = \gcd(33, 1649) = 17 \)，得因子 \( 17 \)（\( 1649 = 17 \times 97 \)）。 总结 二次筛法通过多项式生成平滑数，利用线性代数构造平方同余式，是大整数分解的重要实用算法。其改进版（如多重多项式二次筛）进一步提升了效率。