简介
8822·cf 是一种高效的质数分解算法，由肖尔在 1994 年提出。它使用继续分数逼近和椭圆曲线来分解大整数。
多级标题
算法步骤
1. 预处理
将要分解的整数 n 表示成连分数形式 [a0; a1, a2, ..., an]
计算连分数截断到第 i 项时的近似值 qi / pi，其中 qi 和 pi 是整数
2. 椭圆曲线
选择一条椭圆曲线 E，使得它的阶数与 n 有公共因数
在 E 上进行点加运算，直到得到一个 p1·Q = P2 的点，其中 p1 和 P2 是整数
3. 因子分解
从 p1 和 P2 中提取出 n 的因子
如果 n 仍未被完全分解，则将连分数截断至下一项并重复步骤 2 和 3
内容详细说明
肖尔算法利用了以下事实：如果整数 n 可以表示为 p·q 的乘积，那么 [√n] 的连分数会以数字 p 开始。因此，算法首先通过计算连分数来寻找 n 的可能因子。然后，算法使用椭圆曲线来验证这些可能的因子是否正确。椭圆曲线是一类特殊的代数曲线，具有称为阶数的特定属性。肖尔算法选择一条阶数与 n 有公共因数的椭圆曲线。在椭圆曲线上进行点加运算时，如果结果点恰好是整数倍的原点，则表明 n 具有该整数倍作为因子。通过重复此过程，算法可以找到 n 的所有质因子。
优势
比传统的质数分解算法（如 Pollard-Rho）更有效
对于某些类型的整数，其复杂度比指数时间更低
可用于对 RSA 加密进行攻击
局限性
对于所有类型的整数都不一定是最有效的
对于非常大的整数来说，仍然可能是计算密集型的