普通數域篩選法

簡介

在數論中， 普通數域篩選法（GNFS）是已知效率最高的分解整數的算法。分解整數 n(由⌊logn⌋ + 1個比特位組成)需要

普通數域篩選法

步（參見L符號）。它是從特殊數域篩選法引申出來的。如果條件 數域篩沒有限定條件，就是指普通數域篩選。

方法

我們選擇兩個不可約的多項式 f(x)和 g(x)，令通根 mmod n；則他們會是 m階，同時次數 d和 e比較低。

參見

•整數分解