普通数域筛选法

普通数域筛选法是一个来自数论数学子领域的术语。 它是已知最快的大数因式分解算法之一。

普通数域筛选法主要用于100位以上的数字，其他方法无法分解的数字。 通常，100 台计算机并行运行。

普通数域筛选法可以理解为方筛的推广。 一个重要的考虑因素是平滑数可能更频繁地出现在 Z {displaystyle mathbb {Z} } 以外的幺半群中，因此可以更快地找到。

普通数域筛选法的渐近运行时间无法准确证明。 然而，在一些被认为可能的假设下，这可以对数字 n 完成

e ( C + o ( 1 ) ) ( log ⁡ n ) 1 3 ( log ⁡ log ⁡ n ) 2 3 计算。 所以运行时间是次指数的，但仍然是超多项式的，在数字 n 的长度上。

常数 C 取决于使用的是特殊的还是一般的普通数域筛选法：

• 特殊普通数域筛选法：C=(32/9)
• 一般通用数域筛选法：C=(64/9)