一種篩選程式,可以與 Dixon 因式分解法 結合使用,以分解大數 。選擇由下式給出的
值
|
(1)
|
其中 , 2, ...,且
是 向下取整函式。然後我們尋找因子
,使得
|
(2)
|
這意味著只需要考慮勒讓德符號 勒讓德符號 的數字(對於 試除法 因子
,小於
,其中
是 素數計數函式)。滿足此條件的 素數 集合稱為 因子基。接下來,必須求解每個
在 因子基 中的同餘式
|
(3)
|
必須為因子基中的每個 求解。最後,應用篩選法來找到
的值,這些值可以使用因子基完全分解。然後像在 Dixon 因式分解法 中一樣使用 高斯消元法,以找到
s 的乘積,從而產生一個 完全平方數。
該方法大約需要 步,透過去除 平方根 下的 2,改進了 連分數因式分解演算法(Pomerance 1996)。使用多個 多項式 可以提高因式分解的成功率,需要更短的篩選間隔,並且非常適合並行處理。
二次篩法的一種型別也可以用於生成素數,透過考慮 拋物線 。考慮對於
, 3, ... 位於拋物線上且具有整數座標
的點。現在連線位於拋物線兩個分支上、x 軸上方和下方的整數點對。然後,這些線與
-軸的 交點 對應於合數,而正
-軸上未被任何線穿過的那些整數點是素數。