二次筛选法

二次筛选法是数学中数论领域的一个术语，描述了已知最快的大自然数因式分解算法之一。 它是一种通用的分解方法， 运行时间仅取决于要分解的数字的大小，而不取决于数字（或其除数）的特殊属性。 对于最多约 100 位小数的数字，它是最快的（一般）因式分解方法。 对于更大的数字，数字字段筛选更快。 使用方筛分解数字 n 的运行时间（在某些假设下被认为是可能的）为

exp ⁡ ( ln ⁡ n ⋅ ln ⁡ ln ⁡ n )

Carl Pomerance 在 John Brillhart 和 Michael Morrison 的连分数法的基础上，受到 Richard Schroeppel 的线性筛的启发，通过理论思考于 1981 年发明了二次筛，其速度比以前所有已知的因式分解方法都快。

此后不久，James Davis 和 Diane Holdridge 以及 Peter Montgomery 分别独立地发现了多重多项式二次筛（称为 MPQS）的变体。 另一项改进，即所谓的特殊方筛，由 Mingzhi Zhang 提出； 但它只能应用于特殊号码。

二次筛是狄克逊因式分解方法的进一步发展。 与大多数现代因式分解方法一样，它使用乘积的表示形式作为平方差。

不是检查数字的可整除性，而是寻求将数字表示为平方差。 从表示 x 2 − n = y 2 得到除数 x + y 和 x − y 的 n {\displaystyle n} 。

在 Fermat 的因式分解方法中，计算各种数字 x的值 q ( x ) = x 2 − n ，直到找到一个 q ( x )  这是一个平方数。 xxx个 x 被选为大于 n 平方根的最小数。 然后在每一步中将 x 递增 1。 例如，如果你用这个方法对数字 1649 进行因式分解，你会得到下表中 q ( x ) 的值。

在筛分步骤中，形状一致

x 2 ≡ q mod n

寻求，其中 q 的质因数分解是已知的并且仅由小质数组成（换句话说：q 应该相对于固定边界是平滑的）。 选择靠近 n 的根的数字 x，因此值 x := x 2 − n {\displaystyle q(x):=x^{2}-n} 很小。 因此找到偶数 q(x) 的概率很高。 然而，一个数的质因数分解通常无法在多项式时间内计算。

因此，如果找到 q(x) 可被 p 整除的位置 x，则可以确定可被 p 整除的 q ( x + k p ) 的整个序列。 p 除 q ( x ) = x 2 − n 当且仅当 x 2 ≡ n ( mod p ) 。