Scheme of extending elliptic curve method to three phases

Guiwen LUO

doi:10.11959/j.issn.2096-109x.2018101

您当前的位置：

首页 >

文章列表页 >

Scheme of extending elliptic curve method to three phases

Papers | 更新时间：2024-06-03

- Scheme of extending elliptic curve method to three phases
- Chinese Journal of Network and Information Security Vol. 4, Issue 12, Pages: 62-66(2018)
- 作者机构：
  
  1. 中国科学院大学网络空间安全学院，北京 100049
  2. 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2018101
  CLC： TP301
- Online First：2018-12，
  
  Published：15 December 2018
- 稿件说明：
移动端阅览
Guiwen LUO. Scheme of extending elliptic curve method to three phases[J]. Chinese Journal of Network and Information Security, 2018, 4(12): 62-66.
DOI：

Guiwen LUO. Scheme of extending elliptic curve method to three phases[J]. Chinese Journal of Network and Information Security, 2018, 4(12): 62-66. DOI： 10.11959/j.issn.2096-109x.2018101.

摘要

椭圆曲线法是目前使用最广泛的整数分解算法之一，最早由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”.

关键词

Keywords

references

LENSTRA H . Factoring integer with elliptic curves [J ] . Ann of Math , 1987 :126.

BRENT R P . Some integer factorization algorithms using elliptic curves [J ] . Australian National University Technical Report , 1985 , 8 : 149 - 163 .

MONTGOMERY P L . Speeding the pollard and elliptic curve methods of factorization [J ] . Mathematics of Computation , 1987 , 48 ( 177 ): 243 - 264 .

MONTGOMERY P L . An FFT extension of the elliptic curve method of factorization [M ] . University of California at Los Angeles , 1992 .

ZIMMERMANN P , DODSON B . 20 years of ECM [C ] // International Algorithmic Number Theory Symposium . 2006 : 525 - 542 .

The gmp-ecm development team,GMP-ECM,an implementation of the elliptic curve method algorithm,release 7.0.4 [R ] . 2017 .

OKEYA K , KURUMATANI H , SAKURAI K . Elliptic curves with the montgomery-form and their cryptographic applications [C ] // International Workshop on Practice ＆ Theory in Public Key Cryptography:Public Key Cryptography . 2000 .

MONTGOMERY P L . Evaluating recurrences of form x m+n =f(x m ,x n ,x m−n )via Lucas chains [M ] . 1983 .

TALL A . A generalization of the Lucas addition chains [J ] . Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie , 2012 : 79 - 93 .

MONTGOMERY P L . An FFT extension of the elliptic curve method of factorization [D ] . Los Angeles:University of California , 1992 .

JOACHIM V Z G , GERHARD J . Modern computer algebra [M ] . Modern Computer Algebra . 2001 .

HANROT G , QUERCIA M , ZIMMERMANN P . The middle product algorithm I [J ] . Applicable Algebra in Engineering,Communication and Computing , 2004 , 14 ( 6 ): 415 - 438 .

BERNSTEIN D , BIRKNER P , LANGE T , et al . ECM using edwards curves [J ] . Mathematics of Computation , 2012 , 82 ( 282 ):16.

BERNSTEIN D J , BIRKNER P , JOYE M , et al . Twisted edwards curves [J ] . Lecture Notes in Computer Science , 2008 , 5023 : 389 - 405 .

BERNSTEIN D J , HENINGER N , LOU P , et al . Post-quantum RSA [C ] // International Workshop on Post-Quantum Cryptography . 2017 : 311 - 329 .

Views

1006

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰