有理筛选法

在数学上，有理筛选法是一种将整数分解的通用算法。它是一般数域筛选法的特例。虽然它比一般的数域筛选法效率低，但它在概念上更简单，对理解后续的数域筛选法的原理起到重要的铺垫作用。相对于后续的数域筛选法的过程，该算法在数域处理的过程中本质上只涉及到了有理数域^{[1]:327[2]:55}，因此其名称可能来源于此特性。

方法

假设我们试图分解合数n .我们选择一个边界B , 并确定B对应的因数基底（我们将称为P ），即小于等于B的所有素数的集合。接下来，我们搜索正整数z使得z和z+n都是B平滑的—即它们的所有素因子都在P中。因此有：

${\displaystyle z=\prod _{p_{i}\in P}p_{i}^{a_{i}}}$

其中${\displaystyle a_{i}}$是${\displaystyle p_{i}}$对应的幂次。同样， 我们有

${\displaystyle z+n=\prod _{p_{i}\in P}p_{i}^{b_{i}}}$ .

其中${\displaystyle b_{i}}$为${\displaystyle p_{i}}$对应的幂次。 但${\displaystyle z}$和${\displaystyle z+n}$在模${\displaystyle n}$意义下相等 ，所以对于每一个这样的整数z, 我们找到了P的元素之间产生的一个模n的乘法关系 ，即

${\displaystyle \prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i}}{\pmod {n}}}$

（其中a_i和b_i是非负整数。 )

当我们生成了足够多的这些关系时（关系的数量通常比集合P的大小多几个通常就足够了^{[注 1]}），我们可以使用线性代数的方法将这些不同的关系相乘，使得这些素数${\displaystyle p_{i}}$的幂次都是偶数（我们只关心幂次的奇偶性，这时相当于将幂次对2取模，视为二元域（英语：GF(2)）${\displaystyle F_{2}}$上的整数，所有素数${\displaystyle p_{i}}$的幂次总体可以视为一个向量，幂次全为偶数相当于向量的分量全为0, 得到该结果的过程即为在二元域${\displaystyle F_{2}}$的运算规则下将向量的分量全部消为0的过程）。这样就能够产生一个平方同余关系：a² ≡b² (mod n), 从而得到n的一个因式分解：n = gcd(a-b,n)×gcd(a+b, n) . 这种因式分解可能会产生平凡的结果（即n=n×1），这种情况下需要再次尝试使用不同的关系组合，如果运气足够好，最后就能够得到一对非平凡的n因子，成功将n分解，算法结束。

例子

下面使用有理筛选法分解整数n = 187. 首先随便选取B = 7作为尝试，这时因子基P = {2,3,5,7}. 第一步先是测试n是否可以被P的每个成员整除，如果是这样的话那么我们就直接找到了n的一个因子，这样就成功将n分解无需继续了^{[注 2]}。但现在187并不能被 2,3,5或7整除，所以接下来就应该继续，开始寻找合适的z值；前几个是 2,5,9和56. z的四个合适的值给出了四个模187意义下的乘法关系：

${\displaystyle 2^{1}3^{0}5^{0}7^{0}=2\equiv 189=2^{0}3^{3}5^{0}7^{1}}$

1

${\displaystyle 2^{0}3^{0}5^{1}7^{0}=5\equiv 192=2^{6}3^{1}5^{0}7^{0}}$

2

${\displaystyle 2^{0}3^{2}5^{0}7^{0}=9\equiv 196=2^{2}3^{0}5^{0}7^{2}}$

3

${\displaystyle 2^{3}3^{0}5^{0}7^{1}=56\equiv 243=2^{0}3^{5}5^{0}7^{0}}$

4

现在有几种本质上不同的方法可以将这些组合起来并最终得到全部为偶数的幂次。例如，

• (1)×(4): 在将这些相乘并消去共同的因子 7 之后（其它的一般情况下不能直接消去，本算法的过程中是一定可以的，原因是因为 7 已经确定与n互素 ^{[注 3]}），关系式简化为了2⁴ ≡ 3⁸ (mod n)，或 4² ≡ 81²(mod n)。结果分解为 187 = gcd(81-4,187) × gcd(81+4,187) = 11×17.

或者，等式(3)本身已经是我们想要的形式：

• (3)：3² ≡ 14² (mod n )，得到因式分解 187 = gcd(14-3,187) × gcd(14+3,187) = 11×17.

局限性

有理筛选法与一般数域筛选法一样，不能因式分解p^m形式的数字，其中p是素数，m是整数。不过，这根本不是什么问题，因为要分解的整数基本不可能会是这种数，并且已经有简单而快速的方法来事先检查给定的数字是否属于这种数字。可能最简洁实用的方法是利用整数版本的求方根的牛顿法，检查是否存在(1, log₂(n)]范围内的整数b使得${\displaystyle \lfloor n^{1/b}\rfloor ^{b}=n}$成立。^[3]

最大的问题是找到足够数量的z使得z和z + n都是B平滑的。对于任意一个固定的B ，随着数字数值的增大，符合要求的B平滑数字的比例会迅速下降。因此，如果n很大（例如，一百多位数），则很难或者根本不可能找到足够多的z, 这样这个算法就不太可行了。而后续的一般数域筛选法的优点是要找的光滑数的大小只需要在n^1/d（d通常为3或5的整数）这个数量级左右，而不是这里的n的数量级。

注释

1. 这是因为确保找到的向量线性相关，从中得到它们的线性关系，组合出来零向量。见下文的说明。
2. 实际情况下要分解的n比通常选择的B大得多，一般这里只能排除很小的因子，并不是将B取大一点就能解决的问题。因此这里只是举例。
3. 因此其它的P中的素数也是如此。另外可以参见模逆元条目。

参考文献

1. A. K. Lenstra; H. W. Lenstra; Jr.; M. S. Manasse; J. M. Pollard. The Factorization of the Ninth Fermat Number (PDF). Math. Comp. 1993, 61: 319–349 [2022-02-22]. （原始内容存档 (PDF)于2022-02-22）.
2. A. K. Lenstra, H. W. Lenstra, Jr. (eds.). The Development of the Number Field Sieve. Lecture Notes in Mathematics 1554. New York: Springer-Verlag. 1993. ISBN 9783540570134.
3. R. Crandall; J. Papadopoulos. On the implementation of AKS-class primality tests (PDF). [2022-02-22]. （原始内容存档 (PDF)于2012-10-05）.