跳转到内容

普通数域筛选法

维基百科,自由的百科全书

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

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

方法

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

选择最高次项为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.