二次筛法 二次筛法是一种用于大整数分解的算法，属于因子分解方法中较高效的一类。它的核心思想是利用二次同余关系来寻找平方差，从而分解整数。 基本目标与思想 目标 ：分解一个大合数 \( N \)（假设是奇数，且不是任何素数的幂）。 核心思想（费马分解法） ：如果我们能找到两个整数 \( X \) 和 \( Y \)，使得 \( X^2 \equiv Y^2 \pmod{N} \)，但 \( X \not\equiv \pm Y \pmod{N} \)，那么 \( \gcd(X-Y, N) \) 和 \( \gcd(X+Y, N) \) 就是 \( N \) 的非平凡因子。二次筛法的目标就是系统地寻找这样的 \( X \) 和 \( Y \)。 挑战 ：直接随机寻找满足 \( X^2 \equiv Y^2 \) 的数对效率极低。二次筛法通过筛选一系列“小”的二次剩余来构造这样的 \( Y^2 \)。 构造二次同余式 我们考虑一个二次多项式。令 \( Q(x) = (x + \lfloor \sqrt{N} \rfloor)^2 - N \)，其中 \( \lfloor \cdot \rfloor \) 表示向下取整。 对于整数 \( x \)，有 \( Q(x) \equiv (x + \lfloor \sqrt{N} \rfloor)^2 \pmod{N} \)。如果我们定义 \( X \equiv x + \lfloor \sqrt{N} \rfloor \pmod{N} \)，那么 \( Q(x) \equiv X^2 \pmod{N} \)。 我们的目标是找到一组 \( x \) 值，使得对应的 \( Q(x) \) 的乘积是一个完全平方数。即，找到一组索引 \( S \)，使得 \( \prod_ {x \in S} Q(x) = Y^2 \) 是一个平方数。那么，令 \( X \equiv \prod_ {x \in S} (x + \lfloor \sqrt{N} \rfloor) \pmod{N} \)，我们就得到了 \( X^2 \equiv Y^2 \pmod{N} \)。 因子基与平滑数 因子基 ：为了判断 \( Q(x) \) 的乘积是否为平方数，我们限制 \( Q(x) \) 的因子来自一个预先选定的、较小的素数集合 \( B = \{ p_ 1, p_ 2, ..., p_ k \} \)。这个集合 \( B \) 称为因子基。通常包括 -1（为了处理负值）和所有小于某个界限 \( B_ {\text{limit}} \) 的素数。 B-平滑数 ：如果一个数的所有素因子都在因子基 \( B \) 中，则称这个数是 B-平滑 的。 策略转换 ：现在问题转化为：找到一组 \( x \) 值，使得对应的 \( Q(x) \) 是 B-平滑 的。这些平滑的 \( Q(x) \) 被称为“关系”。 筛法过程（“筛”的由来） 我们需要在许多连续的 \( x \) 值上计算 \( Q(x) \)，并快速判断哪些 \( Q(x) \) 是 B-平滑的。直接对每个 \( Q(x) \) 进行试除非常慢。 核心技巧 ：对于因子基中的每个素数 \( p \)，方程 \( Q(x) \equiv 0 \pmod{p} \) 是一个模 \( p \) 的二次同余方程。这个方程通常有两个解（如果 \( N \) 是模 \( p \) 的二次剩余），记作 \( s_ {p,1} \) 和 \( s_ {p,2} \)。 根据解的性质，对于满足 \( x \equiv s_ {p,1} \pmod{p} \) 或 \( x \equiv s_ {p,2} \pmod{p} \) 的整数 \( x \)，\( Q(x) \) 能被 \( p \) 整除。 筛法 ：我们初始化一个数组，其索引对应一段连续的 \( x \) 值。对于因子基中的每个素数 \( p \)，我们找到所有满足上述同余条件的 \( x \)（即 \( x \) 在模 \( p \) 的剩余类中），然后对这些位置上的 \( Q(x) \) 值除以 \( p \)（并记录除以 \( p \) 的次数）。在计算机实现中，通常用快速的对数加法来近似这个过程。 经过对所有素数 \( p \) 进行这样的“筛”处理之后，数组中值接近 1（或其对数值接近 0）的位置，对应的 \( Q(x) \) 就很有可能是 B-平滑的。然后我们只需对这些候选值进行精确的试除验证，从而高效地收集到大量“关系”。 线性代数阶段 对于每一个找到的平滑关系（即 \( Q(x) \) 是 B-平滑的），我们可以将其因子分解写成指数向量形式。例如，如果 \( Q(x) = (-1)^{e_ 0} p_ 1^{e_ 1} p_ 2^{e_ 2} ... p_ k^{e_ k} \)，则其指数向量为 \( \vec{v}_ x = (e_ 0, e_ 1, e_ 2, ..., e_ k) \mod 2 \)（我们对指数模 2 感兴趣，因为我们要寻找平方数）。 如果我们收集到的关系数 \( R \) 大于因子基的大小 \( k+1 \)，那么这些模 2 的指数向量在 \( \mathbb{F}_ 2^{k+1} \) 中是线性相关的。 通过线性代数方法（如高斯消元法）可以找到一组向量（即一组平滑关系），使得它们的指数向量之和（模 2）为零向量。这意味着这组平滑关系中，每个素因子的总指数均为偶数，从而它们的乘积 \( \prod Q(x) \) 是一个完全平方数 \( Y^2 \)。 计算最大公约数（GCD） 一旦找到了这样一组关系 \( S \)，我们计算： \( X = \prod_ {x \in S} (x + \lfloor \sqrt{N} \rfloor) \mod N \) \( Y = \sqrt{ \prod_ {x \in S} Q(x) } \)（在整数中取平方根） 然后计算 \( d = \gcd(X - Y, N) \)。有很高的概率，\( d \) 是 \( N \) 的一个非平凡因子。如果第一次不成功（即 \( d=1 \) 或 \( d=N \)），可以寻找另一组线性相关的向量重新尝试。 总结 ：二次筛法通过构造二次多项式、利用筛法高效筛选平滑数、将分解问题转化为线性代数问题，最终通过计算最大公约数来分解大整数。它是目前分解百位十进制数最有效的算法之一，也是更高级的数域筛法的基础。