
_START_ARTICLE_
二次篩選法
_START_SECTION_
解决方法
_START_PARAGRAPH_
令 x 模 y 表示为x 除以 y 之后所剩的余数。 为了分解整数n， 费马因式分解法牵涉到需要寻找一个数字a（n1/2 < a < n-1），使得 a² mod n  是一个完全平方数。 但这些a 值相当难找到。 二次筛选法包括对于好几个a 值去计算了a² mod n ，然后在a 值与a² mod n 的集合中找到一个子集，当中的元素之乘积为完全平方数。 而产生出一个平方同余。_NEWLINE_例如：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)。 _NEWLINE_但是，如何将以下问题解决呢？“给予一组数字，找到一个子集使其乘积是平方数。”该解决方案使用了指数向量的概念。而指数向量，例如根据算术基本定理，504 可分解为2³3²5⁰7¹。_NEWLINE_这表示可以借由指数向量(3,2,0,1)，代表 2,3,5,7 在因式分解的指数值。490 会同样可分解为指数向量(1,0,1,2)。将这些数字相乘相当余把其指数向量的对应值一一相加：504×490 得一向量(4,2,1,3)。_NEWLINE_有一些数字为平方数，其满足每个在其指数向量的各个数字为偶数。 例如，向量 (3,0,0,1)、(1,2,0,1) 之和为(4,2,0,2)，因此 56 乘以126 是一个平方数。 找寻一个平方数只需对于向量里数字之的奇偶性之知识，所以有可能将整个向量简化为模2 的形式并作模2 下的加法: (1,0,0,1) + (1,0,0,1) = (0,0,0,0)。 在实作中，这相当地有效率，因其可以表示为一位元集（bitsets）且模2 之加法将变为位元运算互斥或（XOR）。_NEWLINE_于是此问题变化为：“给予一个0, 1向量构成的集合，找到一个子集，其中所有向量之和为模2 的零向量。”而这是一个线性代数的问题；且该解答为线性相依的。_NEWLINE_线性相依是线性代数中的一个定理：当有比每个向量中含有的元素还要多的向量时，这种相依关系必然存在。而它可以被高效率地找到，例如：把所有向量一列一列地排在一个矩阵里 ，然后使用高斯消去法。比起实数来说，此方法尤其容易套用到模2 后的整数上。而此算法所需的平方数即是那些向量所对应的数字之积。_NEWLINE_然而，纯粹地只去将一堆随机数字平方并模n 会产生很大量的、不同的质因数，也因此会产生出很长的向量以及一个非常大的矩阵。解决方法是去找到一些特别的数字a ，使得 a² 模 n 之值只由很小的质因数组成（它们都是光滑数）。此种数字很难被找到，但是若仅使用光滑数将可以保持向量和矩阵之尺寸更小、更容易处理。_NEWLINE_而二次筛选法使用一种之后会提及名为“筛法”（sieving）的技巧去找寻光滑数，也就是此算法的命名由来。
_START_SECTION_
基本筛选的例子
_START_PARAGRAPH_
以下例子将演示没有作对数优化或是质数次方的标准的二次筛法。 令要分解的数为N  = 15347，因此平方根N 无条件进位为124。 由于 N 很小，因此基本的多项式即足够了： y(x)=(x +124)² − 15347
_START_SECTION_
单一的大质数
_START_PARAGRAPH_
如果在除以所有小于A 的因数之后，剩余的数字（余因子）小于 A²，那么这个余因子必为质数。 实际上，借由对于余因子去排序“关系”表，则它可以添加进因数基底里。如果 y(a) = 7 × 11 × 23 × 137 且 y(b) = 3 × 5 × 7 × 137, 则 y(a) × y(b) = 3 × 5 × 11 × 23 × 7² × 137²。 此可以降低以上完整执行因式分解的筛选阵列之“元”的临界值。
_START_SECTION_
更多的大质数
_START_PARAGRAPH_
甚至更进一步去降低临界值，并且使用一个高效处理将y(x) 之值分解为一些更大的质数之积（ECM 适合处理这样子的东西）可以找到因数大多在因数基底，但有两个甚至三个大质数的“关系”。 循环的寻找过程因此允许一个共享好几个质数的“关系”集合，合并成为单一的“关系”。
_START_SECTION_
整数分解的纪录
_START_PARAGRAPH_
直到发现普通数体筛选法（number field sieve, 简称 NFS）之前，二次筛法（QS）曾是已知渐近最快的通用整数分解算法。 现在， 伦斯特拉椭圆曲线因式分解具有跟QS 有相同的渐近运行时间（在 n 由两个相同大小级别的质数相乘所得的情况下），但在实际情况中，QS 速度更快，因为它采用的是单精度浮点数操作而不是椭圆曲线所使用的高精度计算。_NEWLINE_在 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。_NEWLINE_目前 QS 的纪录是 的一个135 位数长之余因子，其为的一个Aurifeuillian因数 ，在 2001 年分解为66 位以及69 位数长的质因数。