将椭圆曲线分解算法扩展为三阶段的方案

椭圆曲线法是目前使用最广泛的整数分解算法之一,最早由Lenstra于1985年提出,原始的算法只有第一阶段。自其提出以来,围绕算法和实现的研究层出不穷,最重要的改进是 Brent 和 Montgomery 提出椭圆曲线法的第二阶段,这极大地提升了椭圆曲线算法的分解能力和效率。将椭圆曲线法扩展为三阶段,采用的方法是将第一阶段和第二阶段进行“融合”。对比目前流行的两阶段椭圆曲线法,改进后的算法有两方面的优点:一是在保持同两阶段椭圆曲线法参数相同的情况下,通过增加微不足道的消耗,提升找到因子的概率;二是在搜寻同一个因子时,可以使用较小的“光滑参数”。