Chinese Journal of Network and Information Security ›› 2018, Vol. 4 ›› Issue (12): 62-66.doi: 10.11959/j.issn.2096-109x.2018101

• Papers • Previous Articles    

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)


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

CLC Number: 

No Suggested Reading articles found!