网络与信息安全学报 (Dec 2018)
Scheme of extending elliptic curve method to three phases
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”.
