For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Elliptic Curve Method Using Complex Multiplication Method
Yusuke AIKAWA Koji NUIDA Masaaki SHIRASE
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2019/01/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
integer factorization, elliptic curve method, complex multiplication method, class polynomials,
Full Text: FreePDF(1MB)
In 2017, Shirase proposed a variant of Elliptic Curve Method combined with Complex Multiplication method for generating certain special kinds of elliptic curves. His algorithm can efficiently factorize a given composite integer when it has a prime factor p of the form 4p=1+Dv2 for some integer v, where -D is an auxiliary input integer called a discriminant. However, there is a disadvantage that the previous method works only for restricted cases where the class polynomial associated to -D has degree at most two. In this paper, we propose a generalization of the previous algorithm to the cases of class polynomials having arbitrary degrees, which enlarges the class of composite integers factorizable by our algorithm. We also extend the algorithm to more various cases where we have 4p=t2+Dv2 and p+1-t is a smooth integer.