二次筛选法1981

二次筛选法是由卡尔·帕梅朗斯在1981年所发明，并作为理查德·施罗佩尔的线性筛法之改良版。

基础目标

此算法试图去建立一个模 n （ n 为欲分解的数）下的平方同余，这往往即是 n 的因数分解。算法有两个阶段：“数据收集”，在此阶段收集可能可以找到一个平方同余的资料；以及“数据处理”，它把所有收集的数据放进一个矩阵里，并解决、获得一个平方同余数。

数据收集的阶段可以很轻易地使用多个处理器去平行化。但数据处理阶段需要大量的记忆体，并且在多个运算节点之间有效地平行化相当困难，也可能每个运算节点的记忆体不够足以储存整个阵列。而Block Wiedemann算法可以使用在一些可以保存阵列的系统。

要找到一个平方同余，一个较天然的方法便是随机挑选数字，将其平方，并希望模 n 之后的非负余数是一个完全平方数。 例如： 80² 模 5959=441，同时也是 21²。

这种方法对很大的 n 值而言，可以找到一个同余的平方数的情况很罕见。但是当真的找到了一个时，在大多数情况下，同余数为非平凡解而整数分解便完成了。这大致上即是费马因式分解法（Fermat's factorization method）的核心。

而二次筛选法改良自狄克森因式分解法。

解决方法

令 x 模 y 表示为 x 除以 y 之后所剩的余数。 为了分解整数 （公式略）， 费马因式分解法牵涉到需要寻找一个数字 a （ n^(1/2)<a<n-1），使得 （公式略） 是一个完全平方数。 但这些 a 值相当难找到。 二次筛选法包括对于好几个 a 值去计算了 （公式略），然后在 a 值与 （公式略） 的集合中找到一个子集，当中的元素之乘积为完全平方数。 而产生出一个平方同余。

例如： 41² 模 1649=32、 42² 模 1649=115 以及 43² 模 1649 为 200。 在这些数字（32、115、200）当中皆无完全平方数，但存在一乘积 32× 200=6400=80² 是一个平方数。 模1649 之后，这个乘积 32× 200=(41²)× (43²)=(41× 43)²=114² （因为 41× 43 模 1649=114）。 32× 200=80² 的观察因而给出了一个平方同余： 114²≡ 80² (模 1649)。

但是，如何将以下问题解决呢？“给予一组数字，找到一个子集使其乘积是平方数。”该解决方案使用了指数向量的概念。而指数向量，例如根据算术基本定理，504 可分解为 2³3²5⁰7¹。

算法

总地来说，二次筛算法基本有以下主要的步骤：

选择一个光滑数之上界 B。 以质数计数函数 π (B) 表示小于 B 的质数之数量，其将控制之后向量的长度以及需要的向量之数量。

使用筛法找到 π (B)+1 个数字 aᵢ 使得 这样 bᵢ=(aᵢ² 模 n) 为一个 B -光滑数。

将 bᵢ 作质因数分解生成一个指数向量（每个数字都要模 2）。

套用线性代数的概念找到一个子集，其中的每个向量之和为一零向量。 把这些向量所对应的 aᵢ 相乘、 bᵢ 相乘并模 n：便得到一个 B -光滑数 b².

现在，我们得到方程式 a²=b²( 模 n) 因为从步骤 4 得到 (a² 模 n) 的两个平方根，一个即是对整数 b² 取平方根，也就是 b；另一个则是步骤 4 得到的 a 本身。

因此现在，我们掌握了所需的恒等式： （公式略）

( （公式略）

( （公式略）。 计算 n 与 a-b （或是 a+b）的 GCD （最大公因数，Greatest Common Divisor）。 此将产生 n 的其中一个因数，尽管有可能是一个平凡（trivial）因数 (即为 n 或是 1)。 如果此因数是平凡的，使用不同的线性相依或是不同的 a 值去再次尝试。

二次筛法（QS）如何最佳化找寻同余

二次筛选法试图找到一整数对 x 和 y(x) （其中 y(x) 为 x 的函数）其满足比 x²≡ y( 模 n) 还要弱得多的条件。它选择一些质数作为一集合作为“因数基底”，并试图找到 x，使得 y(x)=x² 模 n 之值的质因数只会在此因数基底。 此时可称 y 值：对于此因数基底是光滑的。 y(x) 的其中一个值之因式分解（为因数基底的一部分），跟 x 一起，被称为“关系”（relation）。 二次筛选法借由采取接近 n 的平方根之 x 值，以加速寻找这类“关系”的过程。 这将确保 y(x) 会较小，因而具有更大的可能性是光滑的。 （公式略）

（公式略）

这意味着， y 在 2x√n 的数量级上.。然而，这也意味着 y 的增长幅度与 x 乘以 ( n 的平方根) 成正比。

另一个可以增加光滑的可能性是，即是单纯地增大因数基底的大小。 然而，比起因数基底的质数数量，至少找到一个光滑的“关系”还是必要许多，其确保存在一个线性相依。

“部分关系”以及循环

即使对于某些“关系”来说， y(x) 并非光滑的。但如果两个 y 刚好是由因数基底以外的相同质数之乘积，也可能可以合并这两个部分“关系”，以形成一个完整的“关系”。 [注：此形同于因数基底的扩展。]

基本筛选的例子

以下例子将演示没有作对数优化或是质数次方的标准的二次筛法。 令要分解的数为 N=15347，因此平方根 N 无条件进位为124。 由于 N 很小，因此基本的多项式即足够了： y(x)=(x+124)²-15347。

数据收集

因为 N 为小数字，所以只需 4 个质数。 满足在模 p 下 15347 有一平方根的前 4 个质数 p 为 2、17、23 以及 29(换句话说，对这些质数来说，15347是一个模这些数字的二次剩余)。 这些质数将是筛选的基础。

现在我们要建造出我们的筛选 V_(X) 从 （公式略） 并开始对基底里每个质数进行筛选，以下选择筛出 0≤ X<100 的那些 Y(X)： （公式略）

下一步即是去作筛选的动作。 对于我们的质数基底 （公式略） 中的每一个质数 p 值去解决以下方程式： （公式略）

找到阵列 V 之中可被 p 所整除的那些“元”。

对于 p=2 解出 （公式略） 得到了 （公式略）。

所以，从 X=1 开始每次 +2，每个“元”可被 2 整除。把那些元除以 2 之后得到： （公式略）

同理，对于剩下的质数 p

{ （公式略） 方程式 （公式略） 也解决了。

倍数多项式

在实际用途上，有许多相异的多项式用在 y 上，因为仅仅一个多项式通常不足以产生出对于因数基底的光滑数对 (x,y)。 使用的多项式使用必须要有一个特别形式，因为它们需要为模 n. 下的平方数。 多项式必定会与原始的 y(x)=x²-n 有类似的形式： y(x)=(Ax+B)²-n A,B∈ Z

假设 B²-n 是 A 的一个倍数，则 B²-n=AC 且多项式 y(x) 可以被写作 y(x)=A· (Ax²+2Bx+C)。而如果 A 为一个完全平方数，则只需考虑 (Ax²+2Bx+C) 的部分。

此方式（称为 MPQS，倍数多项式二次筛选法（Multiple Polynomial Quadratic Sieve））非常适合平行运算，因为每一个处理因式分解的处理器可以单纯的给入 n、因数基底以及多项式的集合，且直到运算完多项式之前都不须跟中央处理器作任何传输。

大质数

单一的大质数

如果在除以所有小于 A 的因数之后，剩余的数字（余因子）小于 A²，那么这个余因子必为质数。 实际上，借由对于余因子去排序“关系”表，则它可以添加进因数基底里。如果 y(a)=7× 11× 23× 137 且 y(b)=3× 5× 7× 137, 则 y(a)× y(b)==3× 5× 11× 23× 7²× 137²。 此可以降低以上完整执行因式分解的筛选阵列之“元”的临界值。

更多的大质数

甚至更进一步去降低临界值，并且使用一个高效处理将 y(x) 之值分解为一些更大的质数之积（ECM 适合处理这样子的东西）可以找到因数大多在因数基底，但有两个甚至三个大质数的“关系”。 循环的寻找过程因此允许一个共享好几个质数的“关系”集合，合并成为单一的“关系”。

实际例子下的参数

为了展示在一个有包含多个多项式以及大质数优化下的实作方式去跑实际例子，会有的典型参数选取， 将一个 267 位元的半质数输入进 msieve（页面存档备份，存于互联网档案馆） 中，产出了以下的参数：

• 试除因数分解截止于：27 位元
• 筛选区间（对于每个多项式）：393216（12 个大小为 32768 的区块）
• 光滑数之上界：1300967 (共 50294 个质数)
• 对于多项式 A 的系数之因数数量：10 (见上面倍数多项式条目)
• 大质数之上界：128795733 (26 位元) (见上面大质数条目)

光滑数的发现数：有 25952 为直接筛出，另外的 24462 为借由合并那些有大质数的数字所得出

最终矩阵的大小：50294 × 50414，借由过滤法减少到 35750 × 35862

非平凡的线性相依之发现数：15

总执行时间 (在 1.6 GHz UltraSparc III 上)：35 分 39 秒

最大记忆体使用量：8 MB

整数分解的纪录

直到发现普通数体筛选法（number field sieve, 简称 NFS）之前，二次筛法（QS）曾是已知渐近最快的通用整数分解算法。 现在， 伦斯特拉椭圆曲线因式分解具有跟 QS 有相同的渐近运行时间（在 n 由两个相同大小级别的质数相乘所得的情况下），但在实际情况中，QS 速度更快，因为它采用的是单精度浮点数操作而不是椭圆曲线所使用的高精度计算。

在 1994 年的 4 月，RSA-129 的因数分解借由 QS 完成了。 其为一个由两个大质数相乘的129 位数数字一个因数为 64 位长而另一个为 65 位。 此因数分解的因数基底包含了 524339 个质数。 数据收集阶段花了 5000 个 MIPS 年，其完成于互联网上的分散式计算。 数据收集总量为 2 GB。 数据处理花了45个小时在 Bellcore ( 现为 Telcordia 科技公司) 的 MasPar （大规模的平行化）超级电脑。 这曾是最大的、借由通用算法的公开分解，直至 NFS 被用于分解 RSA-130，于 1996 年 4 月 10 日 完成。 所有自此以后分解的 RSA号码 皆使用 NFS。

实作

PPMPQS and PPSIQS（页面存档备份，存于互联网档案馆）

mpqs（页面存档备份，存于互联网档案馆）

SIMPQS（页面存档备份，存于互联网档案馆） 是由 William Hart 编写的自我初始化（self-initializing）的倍数多项式二次筛选法的快速实作。 其提供大质数的优化变体，并使用 Jason Papadopoulos' block Lanczos 程式码于线性代数阶段.。SIMPQS 可以使用 qsieve 指令在 SageMath 电脑代数套件上存取，或是原始来源里下载。 SIMPQS 被优化用于 Athlon 和 Opteron 机器上，但仍可在最常见的 32、 64 位元的结构上运行。 而其完全是由 C 语言编写而成的。

由 Dario Alpern 所提供的 factoring applet（页面存档备份，存于互联网档案馆）， 其在特定状况之下会使用二次筛选法。

PARI/GP 电脑代数套件包含着自我初始化（self-initializing）的倍数多项式二次筛选法的一个实作并有着大质数的优化变体。