主题
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 数字

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上引用

数域筛法

请引用本文为

Weisstein, Eric W. "数域筛法。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/NumberFieldSieve.html

主题分类