Presentation | 2016-11-07 Factorization of Composite Numbers having a Prime of Special Form with Elliptic Curve Method Masaaki Shirase, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | A previous work cite{Shirase16} considered when the elliptic curve method (ECM) successes with a scalar value $N$ for a composite number $N$ one would like to factor, and showed that if a special form of prime $p=(DV^2+1)/4 (V in Z,Din {3,11,19,43,67,163})$ divided $N$ and we could take $P in E(ZN)$ for an elliptic curve $E$ having a designated $j$-invariant then a polynomial time algorithm in the length of $N$ like the ECM could find a non-trivial divisor of $N$ with probability from $1/6$ to $1/2$. However, although taking $P in E$ is easy for $D=3$, it is not for other $D$'s. This paper considers $E$ as on a residue ring of a polynomial ring $(Z/NZ)[X]$ to easily take $P in E$, and improves the algorithm so that it can be repeatedly used until a non-trivial divisor of $N$ is found for $Din {11,19,43,67,163}$. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Elliptic curve method / Prime factorizetion / Anomalous curve / Residue ring |
Paper # | ISEC2016-54,SITE2016-44,LOIS2016-32 |
Date of Issue | 2016-10-31 (ISEC, SITE, LOIS) |
Conference Information | |
Committee | ISEC / LOIS / SITE |
---|---|
Conference Date | 2016/11/7(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Community Hall & AOSSA Mall, Fukui |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | Masahiro Mambo(Kanazawa Univ.) / Hiroyuki Nishi(Sojo Univ.) / Hitoshi Okada(NII) |
Vice Chair | Kazuto Ogawa(NHK) / Atsushi Fujioka(Kanagawa Univ.) / Tomohiro Yamada(NTT) / Tetsuya Morizumi(Kanagawa Univ.) / Masaru Ogawa(Kobe Gakuin Univ.) |
Secretary | Kazuto Ogawa(Toshiba) / Atsushi Fujioka(Tohoku Univ.) / Tomohiro Yamada(NTT) / Tetsuya Morizumi(Nagasaki Univ.) / Masaru Ogawa(Kyushu Univ.) |
Assistant | Toshihiro Ohigashi(Tokai Univ.) / Yuuji Suga(IIJ) / Atsuo Inomata(Tokyo Denki Univ.) / Yukihiro Nakamura(NTT) / Kanako Kawaguchi(Tokyo Univ. of the Arts) |
Paper Information | |
Registration To | Technical Committee on Information Security / Technical Committee on Life Intelligence and Office Information Systems / Technical Committee on Social Implications of Technology and Information Ethics |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Factorization of Composite Numbers having a Prime of Special Form with Elliptic Curve Method |
Sub Title (in English) | |
Keyword(1) | Elliptic curve method |
Keyword(2) | Prime factorizetion |
Keyword(3) | Anomalous curve |
Keyword(4) | Residue ring |
1st Author's Name | Masaaki Shirase |
1st Author's Affiliation | Future University Hakodate(FUN) |
Date | 2016-11-07 |
Paper # | ISEC2016-54,SITE2016-44,LOIS2016-32 |
Volume (vol) | vol.116 |
Number (no) | ISEC-289,SITE-290,LOIS-291 |
Page | pp.pp.19-26(ISEC), pp.19-26(SITE), pp.19-26(LOIS), |
#Pages | 8 |
Date of Issue | 2016-10-31 (ISEC, SITE, LOIS) |