IEICE TRANSACTIONS on Fundamentals
Open Access
Elliptic Curve Method Using Complex Multiplication Method
-
Full Text Views
32
- Cite this
- Free PDF (1MB)
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.1 pp.74-80
- Publication Date
- 2019/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E102.A.74
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
Authors
Yusuke AIKAWA
Hokkaido University
Koji NUIDA
The University of Tokyo/Information Technology Research Institute,Future University Hakodate
Masaaki SHIRASE
Future University Hakodate
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yusuke AIKAWA, Koji NUIDA, Masaaki SHIRASE, "Elliptic Curve Method Using Complex Multiplication Method" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 1, pp. 74-80, January 2019, doi: 10.1587/transfun.E102.A.74.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.74/_p
Copy
@ARTICLE{e102-a_1_74,
author={Yusuke AIKAWA, Koji NUIDA, Masaaki SHIRASE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Elliptic Curve Method Using Complex Multiplication Method},
year={2019},
volume={E102-A},
number={1},
pages={74-80},
abstract={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.},
keywords={},
doi={10.1587/transfun.E102.A.74},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Elliptic Curve Method Using Complex Multiplication Method
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 74
EP - 80
AU - Yusuke AIKAWA
AU - Koji NUIDA
AU - Masaaki SHIRASE
PY - 2019
DO - 10.1587/transfun.E102.A.74
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2019
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+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.
ER -
English
