有理篩選法

在數學上，有理篩選法是一種將整數分解的通用算法。它是一般數域篩選法的特例。雖然它比一般的數域篩選法效率低，但它在概念上更簡單，對理解後續的數域篩選法的原理起到重要的鋪墊作用。相對於後續的數域篩選法的過程，該算法在數域處理的過程中本質上只涉及到了有理數域，因此其名稱可能來源於此特性。

方法

假設我們試圖分解合數n .我們選擇一個邊界B , 並確定B對應的因數基底（我們將稱為P ），即小於等於B的所有素數的集合。接下來，我們搜索正整數z使得z和z+n都是B平滑的—即它們的所有素因子都在P中。因此有：

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

其中$a_{i}$是$p_{i}$對應的冪次。同樣， 我們有

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

其中$b_{i}$為$p_{i}$對應的冪次。 但$z$和$z+n$在模$n$意義下相等 ，所以對於每一個這樣的整數z, 我們找到了P的元素之間產生的一個模n的乘法關係 ，即

$\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的大小多幾個通常就足夠了），我們可以使用線性代數的方法將這些不同的關係相乘，使得這些素數$p_{i}$的冪次都是偶數（我們只關心冪次的奇偶性，這時相當於將冪次對2取模，視為二元域$F_{2}$上的整數，所有素數$p_{i}$的冪次總體可以視為一個向量，冪次全為偶數相當於向量的分量全為0, 得到該結果的過程即為在二元域$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分解無需繼續了。但現在187並不能被 2,3,5或7整除，所以接下來就應該繼續，開始尋找合適的z值；前幾個是 2,5,9和56. z的四個合適的值給出了四個模187意義下的乘法關係：

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

1

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

2

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

3

$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互素 ），關係式簡化為了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使得$\lfloor n^{1/b}\rfloor ^{b}=n$成立。

最大的問題是找到足夠數量的z使得z和z + n都是B平滑的。對於任意一個固定的B ，隨着數字數值的增大，符合要求的B平滑數字的比例會迅速下降。因此，如果n很大（例如，一百多位數），則很難或者根本不可能找到足夠多的z, 這樣這個算法就不太可行了。而後續的一般數域篩選法的優點是要找的光滑數的大小只需要在n^1/d（d通常為3或5的整數）這個數量級左右，而不是這裡的n的數量級。