二次筛法的数论基础与算法步骤
字数 1256 2025-12-05 19:09:04

二次筛法的数论基础与算法步骤

  1. 二次筛法的基本目标
    二次筛法是一种用于分解大整数的算法，属于现代整数分解算法中相对高效的一类。其核心思想是利用“平方同余”关系：寻找两个整数 \(x\) 和 \(y\)，使得 \(x^2 \equiv y^2 \pmod{N}\)，但 \(x \not\equiv \pm y \pmod{N}\)，从而通过计算 \(\gcd(x - y, N)\) 得到 \(N\) 的一个非平凡因子。这里 \(N\) 是待分解的奇合数。

  2. 构造平方同余关系
    为了得到 \(x^2 \equiv y^2 \pmod{N}\)，算法通常选择一个“因子基” \(B\)，由一组小素数（包括 \(-1\) 和所有小于某个界限 \(B_{\text{max}}\) 的素数）构成。目标是收集多个“关系”，即整数 \(r\) 使得 \(r^2 \bmod N\) 的所有质因子都在 \(B\) 中（这样的 \(r^2 \bmod N\) 称为“\(B\)-光滑数”）。每个关系写作：

\[r^2 \equiv (-1)^{e_0} p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \pmod{N} \]

其中 \(p_i \in B\)，指数向量 \((e_0, e_1, \dots, e_k)\) 记录质因数分解。

  1. 线性代数步骤
    收集足够多关系后（数量略大于因子基大小），将这些指数向量模 2 简化，得到一个线性方程组。目标是找到一组关系，其对应指数向量之和为偶向量（即每个分量模 2 均为 0）。这意味着这些关系相乘后，左边是平方数 \(X^2\)，右边也是平方数 \(Y^2\)，从而得到所需同余式 \(X^2 \equiv Y^2 \pmod{N}\)。

  2. 筛选（Sieve）优化
    二次筛法的效率关键在“筛选”步骤：通过多项式 \(Q(x) = (x + \lfloor \sqrt{N} \rfloor)^2 - N\) 生成候选 \(r\)。对每个因子基中的素数 \(p\)，求解方程 \(Q(x) \equiv 0 \pmod{p}\)，得到 \(x\) 的两个模 \(p\) 根（若存在）。然后利用这些根快速筛选出使 \(Q(x)\) 能被 \(p\) 整除的 \(x\) 值，从而高效识别 \(B\)-光滑的 \(Q(x)\) 值，对应 \(r = x + \lfloor \sqrt{N} \rfloor\)。

  3. 算法复杂度与实际应用
    二次筛法的渐近时间复杂度为 \(L_N[1/2, 1] = e^{(1+o(1)) \sqrt{\ln N \ln\ln N}}\)，其中 \(L_N\) 是亚指数函数。它适用于分解 50 到 100 位十进制数，曾是 20 世纪末最有效的通用分解算法，后来被数域筛法超越。其名称“二次”来源于多项式 \(Q(x)\) 为二次型，而“筛”指的是用类似埃拉托斯特尼筛法的方式筛选光滑数。

二次筛法的数论基础与算法步骤 二次筛法的基本目标 二次筛法是一种用于分解大整数的算法，属于现代整数分解算法中相对高效的一类。其核心思想是利用“平方同余”关系：寻找两个整数 \(x\) 和 \(y\)，使得 \(x^2 \equiv y^2 \pmod{N}\)，但 \(x \not\equiv \pm y \pmod{N}\)，从而通过计算 \(\gcd(x - y, N)\) 得到 \(N\) 的一个非平凡因子。这里 \(N\) 是待分解的奇合数。 构造平方同余关系 为了得到 \(x^2 \equiv y^2 \pmod{N}\)，算法通常选择一个“因子基” \(B\)，由一组小素数（包括 \(-1\) 和所有小于某个界限 \(B_ {\text{max}}\) 的素数）构成。目标是收集多个“关系”，即整数 \(r\) 使得 \(r^2 \bmod N\) 的所有质因子都在 \(B\) 中（这样的 \(r^2 \bmod N\) 称为“\(B\)-光滑数”）。每个关系写作： \[ r^2 \equiv (-1)^{e_ 0} p_ 1^{e_ 1} p_ 2^{e_ 2} \cdots p_ k^{e_ k} \pmod{N} \] 其中 \(p_ i \in B\)，指数向量 \((e_ 0, e_ 1, \dots, e_ k)\) 记录质因数分解。 线性代数步骤 收集足够多关系后（数量略大于因子基大小），将这些指数向量模 2 简化，得到一个线性方程组。目标是找到一组关系，其对应指数向量之和为偶向量（即每个分量模 2 均为 0）。这意味着这些关系相乘后，左边是平方数 \(X^2\)，右边也是平方数 \(Y^2\)，从而得到所需同余式 \(X^2 \equiv Y^2 \pmod{N}\)。 筛选（Sieve）优化 二次筛法的效率关键在“筛选”步骤：通过多项式 \(Q(x) = (x + \lfloor \sqrt{N} \rfloor)^2 - N\) 生成候选 \(r\)。对每个因子基中的素数 \(p\)，求解方程 \(Q(x) \equiv 0 \pmod{p}\)，得到 \(x\) 的两个模 \(p\) 根（若存在）。然后利用这些根快速筛选出使 \(Q(x)\) 能被 \(p\) 整除的 \(x\) 值，从而高效识别 \(B\)-光滑的 \(Q(x)\) 值，对应 \(r = x + \lfloor \sqrt{N} \rfloor\)。 算法复杂度与实际应用 二次筛法的渐近时间复杂度为 \(L_ N[ 1/2, 1] = e^{(1+o(1)) \sqrt{\ln N \ln\ln N}}\)，其中 \(L_ N\) 是亚指数函数。它适用于分解 50 到 100 位十进制数，曾是 20 世纪末最有效的通用分解算法，后来被数域筛法超越。其名称“二次”来源于多项式 \(Q(x)\) 为二次型，而“筛”指的是用类似埃拉托斯特尼筛法的方式筛选光滑数。