| 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) |