普通数域筛选法

数学中，普通数域筛选法是已知效率最高的分解整数的算法。分解整数n需要

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

步（参见大O符号）。它是从特殊数域筛选法引申出来的。如果条件数域筛没有限定条件，就是指普通数域筛选。

方法

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

参考

• 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 Sieves。Notices of the AMS 1996, 1473–1485.