TY - JOUR

T1 - Elliptic curve method using complex multiplication method

AU - Aikawa, Yusuke

AU - Nuida, Koji

AU - Shirase, Masaaki

N1 - Funding Information:
The first author was supported by National Institute of Advanced Industrial Science and Technology (AIST) during this work. The second author was supported during this work by JST CREST Grant Number JPMJCR14D6, Japan. The third author was supported during this work by JSPS KAKENHI Grant Number 16K00188.
Publisher Copyright:
Copyright © 2019 The Institute of Electronics, Information and Communication Engineers

PY - 2019/1

Y1 - 2019/1

N2 - 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 + Dv 2 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 = t 2 + Dv 2 and p + 1 − t is a smooth integer.

AB - 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 + Dv 2 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 = t 2 + Dv 2 and p + 1 − t is a smooth integer.

UR - http://www.scopus.com/inward/record.url?scp=85059972246&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059972246&partnerID=8YFLogxK

U2 - 10.1587/transfun.E102.A.74

DO - 10.1587/transfun.E102.A.74

M3 - Article

AN - SCOPUS:85059972246

SP - 74

EP - 80

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

SN - 0916-8508

IS - 1

ER -