主題
Search

二次篩法


一種篩選程式,可以與 Dixon 因式分解法 結合使用,以分解大數 n。選擇由下式給出的 r

 r=|_sqrt(n)_|+k,
(1)

其中 k=1, 2, ...,且 |_x_|向下取整函式。然後我們尋找因子 p,使得

 n=r^2 (mod p),
(2)

這意味著只需要考慮勒讓德符號 勒讓德符號 (n/p)=1 的數字(對於 試除法 因子 d,小於 N=pi(d),其中 pi(d)素數計數函式)。滿足此條件的 素數 集合稱為 因子基。接下來,必須求解每個 p因子基 中的同餘式

 x^2=n (mod p)
(3)

必須為因子基中的每個 p 求解。最後,應用篩選法來找到 f(r)=r^2-n 的值,這些值可以使用因子基完全分解。然後像在 Dixon 因式分解法 中一樣使用 高斯消元法,以找到 f(r)s 的乘積,從而產生一個 完全平方數

該方法大約需要 exp(sqrt(lnnlnlnn)) 步,透過去除 平方根 下的 2,改進了 連分數因式分解演算法(Pomerance 1996)。使用多個 多項式 可以提高因式分解的成功率,需要更短的篩選間隔,並且非常適合並行處理。

QuadraticSieve

二次篩法的一種型別也可以用於生成素數,透過考慮 拋物線 x=y^2。考慮對於 y=2, 3, ... 位於拋物線上且具有整數座標 (y^2,y) 的點。現在連線位於拋物線兩個分支上、x 軸上方和下方的整數點對。然後,這些線與 x-軸的 交點 對應於合數,而正 x-軸上未被任何線穿過的那些整數點是素數。


另請參閱

數域篩法, 素因數分解演算法, 二次, 平滑數

使用 探索

參考文獻

Alford, W. R. 和 Pomerance, C. "在分散式網路上實現自初始化二次篩法。" 在 計算機科學中的數論和代數方法,國際莫斯科會議論文集,1993年6-7月 (Ed. A. J. van der Poorten, I. Shparlinksi, 和 H. G. Zimer)。新加坡:World Scientific, pp. 163-174, 1995。Boender, H. 和 te Riele, H. J. J. "使用二次篩法分解具有大素數變體的整數。" 預印本。Centrum voor Wiskunde en Informatica, No. NM-R9513, 1995。Brent, R. P. "整數因式分解的並行演算法。" 在 數論與密碼學 (Ed. J. H. Loxton)。紐約:Cambridge University Press, 26-37, 1990。Bressoud, D. M. Ch. 8 in 因式分解與素性測試。 紐約:Springer-Verlag, 1989。Gerver, J. "使用二次篩法分解大數。" Math. Comput. 41, 287-294, 1983。Lenstra, A. K. 和 Manasse, M. S. "透過電子郵件進行因式分解。" 在 密碼學進展--歐洲密碼學會議 '89 (Ed. J.-J. Quisquarter 和 J. Vandewalle)。柏林:Springer-Verlag, pp. 355-371, 1990。Pomerance, C. "二次篩法因式分解演算法。" 在 密碼學進展:EUROCRYPT 84 會議論文集 (Ed. T. Beth, N. Cot, 和 I. Ingemarsson)。紐約:Springer-Verlag, pp. 169-182, 1985。Pomerance, C. "兩種篩法的故事。" Not. Amer. Math. Soc. 43, 1473-1485, 1996。Pomerance, C.; Smith, J. W.; 和 Tuler, R. "使用二次篩法分解大整數的流水線架構。" SIAM J. Comput. 17, 387-403, 1988。Silverman, R. D. "多項式二次篩法。" Math. Comput. 48, 329-339, 1987。

在 中被引用

二次篩法

請引用為

Weisstein, Eric W. "二次篩法。" 來自 Web 資源。 https://mathworld.tw/QuadraticSieve.html

主題分類