普通數域篩選法

在數論中,普通數域篩選法(GNFS)是已知效率最高的分解整數的算法。分解整數n需要

步(參見大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.