主題
Search

數域篩法

由 Pollard 開發的一種極快速的因數分解方法，曾用於分解 RSA-130 數字。這種方法是目前已知的分解一般數字最有效的方法，其複雜度為

O{exp[c(logn)^(1/3)(loglogn)^(2/3)]},
(1)

降低了 c 指數，優於 連分數因式分解演算法 和 二次篩法。對於該方法的不同變體，有三個相關的 c 值（Pomerance 1996）。對於應用於接近大 冪 的數字的演算法的“特殊”情況，

c=((32)/9)^(1/3)=1.526285...,
(2)

對於適用於任何非 冪 的 奇 正 數的“一般”情況，

c=((64)/9)^(1/3)=1.922999...,
(3)

以及對於使用多個 多項式 的版本（Coppersmith 1993），

c=1/3(92+26sqrt(13))^(1/3)=1.901883....
(4)

參見

通用數域篩法, 二次篩法, RSA 數字

使用 探索

參考文獻

Coppersmith, D. "數域篩法的改進。" J. Cryptology 6, 169-180, 1993.Coppersmith, D.; Odlyzko, A. M.; 和 Schroeppel, R. "GF(p) 中的離散對數。" Algorithmics 1, 1-15, 1986.Cowie, J.; Dodson, B.; Elkenbracht-Huizing, R. M.; Lenstra, A. K.; Montgomery, P. L.; Zayer, J. A. "世界範圍數域篩法分解記錄：邁向 512 位。" 在 密碼學進展——亞洲密碼學會議 '96 (慶州) (Ed. K. Kim 和 T. Matsumoto.) New York: Springer-Verlag, pp. 382-394, 1996.Elkenbracht-Huizing, R.-M. "多項式通用數域篩法。" 演算法數論 (塔朗斯, 1996). New York: Springer-Verlag, pp. 99-114, 1996.Elkenbracht-Huizing, R.-M. "數域篩法的實現。" Experiment. Math. 5, 231-253, 1996.Elkenbracht-Huizing, R.-M. "數域篩法分解方法的歷史背景。" Nieuw Arch. Wisk. 14, 375-389, 1996.Elkenbracht-Huizing, R.-M. 使用數域篩法分解整數。 博士論文，萊頓大學，1997.Lenstra, A. K. 和 Lenstra, H. W. Jr. "數論中的演算法。" 在 理論計算機科學手冊，A 卷：演算法與複雜性 (Ed. J. van Leeuwen). New York: Elsevier, pp. 673-715, 1990.Lenstra, A. K. 和 Lenstra, H. W. Jr. 數域篩法的發展。 Berlin: Springer-Verlag, 1993.Pomerance, C. "兩個篩子的故事。" Not. Amer. Math. Soc. 43, 1473-1485, 1996.

在 上引用

數域篩法

請引用本文為

Weisstein, Eric W. "數域篩法。" 來自 網路資源。 https://mathworld.tw/NumberFieldSieve.html

主題分類