查看“︁有理筛选法”︁的源代码

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

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

<math>z=\prod_{p_i\in P} p_i^{a_i}</math>

其中<math>a_i</math>是<math>p_i</math>对应的幂次。同样， 我们有

<math>z+n=\prod_{p_i\in P} p_i^{b_i}</math> .

其中<math>b_i</math>为<math>p_i</math>对应的幂次。 但<math>z</math>和<math>z+n</math>在模<math>n</math>意义下相等 ，所以对于每一个这样的整数''z,'' 我们找到了''P''的元素之间产生的一个[[模算數|模n]]的乘法关系 ，即

: <math>\prod_{p_i\in P} p_i^{a_i} \equiv \prod_{p_i\in P} p_i^{b_i} \pmod n</math>

（其中''a<sub>i</sub>''和''b<sub>i</sub>''是非负整数。 )

当我们生成了足够多的这些关系时（关系的数量通常比集合''P''的大小多几个通常就足够了{{notetag|这是因为确保找到的向量线性相关，从中得到它们的线性关系，组合出来零向量。见下文的说明。}}），我们可以使用[[线性代数]]的方法将这些不同的关系相乘，使得这些素数<math>p_i</math>的幂次都是偶数（我们只关心幂次的奇偶性，这时相当于将幂次对2取模，视为{{link-en|二元域|GF(2)}}<math>F_2</math>上的整数，所有素数<math>p_i</math>的幂次总体可以视为一个向量，幂次全为偶数相当于向量的分量全为0, 得到该结果的过程即为在二元域<math>F_2</math>的运算规则下将向量的分量全部消为0的过程）。这样就能够产生一个[[平方同餘|平方同余]]关系：a<sup>2</sup> ≡b<sup>2</sup> (mod ''n''), 从而得到''n''的一个因式分解''：n ='' [[最大公因數|gcd]](''a''-''b'',''n'')×gcd(''a''+''b'', ''n'') . 这种因式分解可能会产生[[平凡 (數學)|平凡]]的结果（即''n''=''n''×1），这种情况下需要再次尝试使用不同的关系组合，如果运气足够好，最后就能够得到一对非平凡的''n''因子，成功将''n''分解，算法结束。

== 例子 ==
下面使用有理筛选法分解整数''n'' = 187. 首先随便选取''B'' = 7作为尝试，这时因子基''P''&nbsp;=&nbsp;{2,3,5,7}. 第一步先是测试''n''是否可以被''P''的每个成员整除，如果是这样的话那么我们就直接找到了''n''的一个因子，这样就成功将''n''分解无需继续了{{notetag|实际情况下要分解的''n''比通常选择的''B''大得多，一般这里只能排除很小的因子，并不是将''B''取大一点就能解决的问题。因此这里只是举例。}}。但现在187并不能被 2,3,5或7整除，所以接下来就应该继续，开始寻找合适的''z''值；前几个是 2,5,9和56. ''z''的四个合适的值给出了四个模187意义下的乘法关系：{{NumBlk|:|<math>2^1 3^0 5^0 7^0  = 2 \equiv 189 = 2^0 3^3 5^0 7^1</math>|{{EquationRef|1}}}}{{NumBlk|:|<math>2^0 3^0 5^1 7^0  = 5 \equiv 192 = 2^6 3^1 5^0 7^0</math>|{{EquationRef|2}}}}{{NumBlk|:|<math>2^0 3^2 5^0 7^0  = 9 \equiv 196 = 2^2 3^0 5^0 7^2</math>|{{EquationRef|3}}}}{{NumBlk|:|<math>2^3 3^0 5^0 7^1  = 56 \equiv 243 = 2^0 3^5 5^0 7^0</math>|{{EquationRef|4}}}}现在有几种本质上不同的方法可以将这些组合起来并最终得到全部为偶数的幂次。例如，

* (1)×(4): 在将这些相乘并消去共同的因子 7 之后（其它的一般情况下'''不能'''直接消去，本算法的过程中是一定可以的，原因是因为 7 已经确定与''n''互素 {{notetag|因此其它的''P''中的素数也是如此。另外可以参见[[模逆元]]条目。}}），关系式简化为了2<sup>4</sup> ≡ 3<sup>8</sup> (mod ''n'')，或 4<sup>2</sup> ≡ 81<sup>2</sup>(mod ''n'')。结果分解为 187 = gcd(81-4,187) × gcd(81+4,187) = 11×17.

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

* (3)：3<sup>2</sup> ≡ 14<sup>2</sup> (mod ''n'' )，得到因式分解 187 = gcd(14-3,187) × gcd(14+3,187) = 11×17.

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

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

== 注释 ==
{{notefoot}}

== 参考文献 ==
{{reflist|refs=<ref name="DevNFS">{{cite encyclopedia |author=A. K. Lenstra, H. W. Lenstra, Jr. (eds.) |title=The Development of the Number Field Sieve |encyclopedia=Lecture Notes in Mathematics |volume=1554 |year=1993 |publisher=Springer-Verlag |location=New York |isbn=9783540570134}}</ref><ref name="Fermat">{{cite journal |author1=A. K. Lenstra |author2=H. W. Lenstra |author3=Jr. |author4=M. S. Manasse |author5=J. M. Pollard |title=The Factorization of the Ninth Fermat Number |journal=Math. Comp |date=1993 |volume=61 |pages=319-349 |url=https://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1182953-4/S0025-5718-1993-1182953-4.pdf |access-date=2022-02-22 |archive-date=2022-02-22 |archive-url=https://web.archive.org/web/20220222124343/https://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1182953-4/S0025-5718-1993-1182953-4.pdf |dead-url=no }}</ref><ref name="RC">{{cite journal |author1=R. Crandall |author2=J. Papadopoulos |title=On the implementation of AKS-class primality tests |url=https://www.apple.com/acg/pdf/aks3.pdf |journal= |access-date=2022-02-22 |archive-date=2012-10-05 |archive-url=https://web.archive.org/web/20121005235722/http://www.apple.com/acg/pdf/aks3.pdf |dead-url=no }}</ref>}}

{{数论算法}}
[[Category:整数分解算法]]