网络与信息安全学报 ›› 2018, Vol. 4 ›› Issue (12): 62-66.doi: 10.11959/j.issn.2096-109x.2018101

• 学术论文 • 上一篇    

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

罗贵文1,2()   

  1. 1 中国科学院大学网络空间安全学院,北京 100049
    2 中国科学院信息工程研究所信息安全国家重点实验室,北京 100093
  • 修回日期:2018-11-28 出版日期:2018-12-01 发布日期:2018-12-30
  • 作者简介:罗贵文(1993-),男,重庆人,中国科学院大学硕士生,主要研究方向为椭圆曲线密码学。
  • 基金资助:
    国防科技创新特区基金资助项目(Y7H0041102)

Scheme of extending elliptic curve method to three phases

Guiwen LUO1,2()   

  1. 1 School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China
    2 State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China
  • Revised:2018-11-28 Online:2018-12-01 Published:2018-12-30
  • Supported by:
    The National Defense Science and Technology Innovation Foundation(Y7H0041102)

摘要:

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

关键词: 整数分解, 快速分解, 椭圆曲线法, 光滑参数

Abstract:

Elliptic curve method for integer factorization (ECM) is one of the most popular integer factorization algorithms,and it was firstly proposed by Lenstra in 1985.The original ECM contained just first phase.Since its invention,researches about the algorithm and implementation emerged up,among which the most important improvement is the extension to two phases proposed by Brent and Montgomery.This improvement tremendously strengthened ECM's capacity and efficiency.Elliptic curve method was extended to three phases.Extension method is kind of like “mixing together” the first phase and second phase.Compared to the best current two phases ECM,the new algorithm shows 2 advantages.First,under the same factorization parameters,the proposed algorithm improves the probability of finding out prime factor at the expense of negligible increasement of time.Second,when searching the same prime factor,the proposed algorithm can utilize smaller “smoothness parameters”.

Key words: integer factorization, fast factorization, elliptic curve method, smoothness parameter

中图分类号: 

No Suggested Reading articles found!