普通数域筛选法

维基百科,自由的百科全书
跳转至: 导航搜索

在数论中,普通数域筛选法(GNFS)是已知效率最高的分解整数的算法。分解整数n需要

O\left\{\exp\left[\left({64\over9}\log n\right)^{1\over3} (\log \log n)^{2\over3}\right]\right\}

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

方法[编辑]

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

参见[编辑]

参考[编辑]

  • Lenstra, Arjen K.; Lenstra, H.W. Jr. (Eds.) (1993). The development of the number field sieve. Lecture Notes in Math. 1554. Springer-Verlag.
  • Pomerance, Carl (1996). A Tale of Two SievesNotices of the AMS 1996, 1473–1485.