维基百科

普通数域筛选法

在数论中，普通数域筛选法（GNFS）是已知效率最高的分解整数的算法。
分解整数n（由⌊log2 n⌋ + 1个位元组成）需要

步（参见L符号）。它是从特殊数域筛选法（英语：Special number field sieve）引申出来的。
如果条件数域筛没有限定条件，就是指普通数域筛选。

方法

我们选择两个不可约分的最高次项为d和e的两个多项式f(x)和g(x)，
令通根m是f和g mod n的根；则他们会是m阶，同时次项d 和 e比较低。

选择最高次项为d和e的两个多项式f（x）和g（x），它们具有整数系数，在有理数上不可约，并且在mod n时具有共同的整数根m。
选择这些多项式的最佳策略尚不明确。
一种简单的方法是为多项式选择一个次数d，考虑n^(1/d)的多个不同m（允许在-m和m之间的数字），
并选择f（x）作为系数最小d 且 g（x）为 x − m的多项式。

考虑数字环Z [r1]和Z [r2]，其中r1和r2是多项式f和g的根。
由于f为d次且具有整数系数，因此如果a和b为整数，则(b^d)·f（a / b）也将为r，我们将其称为r。
类似地，s ＝ (b^e)·g（a / b）是整数。目的是找到a和b的整数值，
这些整数值同时使r和s相对于所选质数的底数平滑。
如果a和b小，则r和s也将小，大约为m的大小，并且我们有更好的机会使它们同时平滑。

具有足够多的数对(r,s)，使用高斯消去法，可以同时使某些r和相应s的乘积成为平方。
需要一个稍微强一些的条件-它们是数字中的平方范数，但是该条件也可以通过此方法来实现。
每个r都是a-r1b的范数，因此相应因子a-r1b的乘积是Z [r1]中的平方，
类似地，因子a-r2b的乘积是Z [r2]中的平方，并且也可以计算出“平方根”。
应该指出的是，使用高斯消去法不能给出算法的最佳运行时间。取而代之的是使用稀疏矩阵求解算法，例如Block Lanczos或Block Wiedemann。

由于m是f和g mod n的根，因此从环Z [r1]和Z [r2]到环Z / nZ（整数mod n）存在同态，它们将r1和r2映射到m，并且这些同态将把每个“平方根”（通常不表示为有理数）映射为其整数表示。
现在，可以通过两种方式将因子a-mb mod n的乘积作为一个平方来获得-每个同态一种。
因此，可以找到两个数字x和y，其中x^2- y^2被n整除，
并且又有可能至少有一半通过找到n和x-y的最大公约数而得到。

参见

参考

  • Lenstra, Arjen K.; Lenstra, H.W. Jr. (Eds.) (1993). The development of the number field sieve. Lecture Notes in Math. 1554. Springer-Verlag.
  • Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective (2001). 2nd edition, Springer. ISBN 0-387-25282-7. Section 6.2: Number field sieve, pp. 278–301.
检索自“https://zh.wikipedia.org/w/index.php?title=普通数域筛选法&oldid=78651089”