Bernstein's Factorization Method Helped Factor RSA-240 in 2020
4 hours ago
- 伯恩斯坦算法用于找出整数列表中小于界限B的所有小质因数，称为批量平滑性检测。
- 它在2020年由Boudot等人将RSA-240（一个795位数）的分解时间减少了25%。
- 该算法使用乘积树和2-adic除法，无需昂贵的除法运算即可高效计算模约简。
- Python实现包含辅助算法：TwoAdicInverse、TwoAdicDivision、ConstructProductTree、FindDividingPrimes以及主算法BernsteinFactorization。
- 代码通过一个数值示例演示：使用不超过19的质数分解小整数[492, 2567, 3135, 5889]，得到正确的因子列表。
- 该算法是“程序员实用数域筛法”系列的一部分，专注于整数分解和离散对数计算。