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

作者：罗贵文^*

来源：网络与信息安全学报, 2018, 4(12): 62-66.

• 整数分解
• 快速分解
• 椭圆曲线法
• 光滑参数

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

• 单位
  中国科学院大学; 信息安全国家重点实验室; 中国科学院信息工程研究所