| 講演名 | 2016-11-07 特別な形の素因数を持つ合成数の楕円曲線法による素因数分解 白勢 政明(公立はこだて未来大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 先行研究cite{Shirase16}は，素因数分解したい合成数$N$に対して，楕円曲線法(ECM)におけるスカラー値を$N$とする時にECMが成功するための条件を考察し，$N$が$p=(DV^2+1)/4 (V in Z，Din {3,11,19,43,67,163})$という特別な形の素因数を持つ場合，指定した$j$-不変数を持つ楕円曲線$E$に対して$P in E(ZN)$をとることができるならば$N$の非自明な約数を確率$1/6 sim 1/2$で見つける$N$の長さに関する多項式時間アルゴリズム提案した．しかしながら，$D=3$に対しては簡単に$P in E(ZN)$をとれるが，他の$D$ではこれは簡単ではない．本稿は$E$を多項式環$(Z/NZ)[X]$の剰余環上で考えることで，$Din {11,19,43,67,163}$に対して$P in E$が簡単にとれ，このアルゴリズムを$N$の非自明な約数が見つかるまで繰り返すことができるように改良できる． |
| 抄録(英) | 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}$. |
| キーワード(和) | 楕円曲線法 / 素因数分解 / アノマラス曲線 / 剰余環 |
| キーワード(英) | Elliptic curve method / Prime factorizetion / Anomalous curve / Residue ring |
| 資料番号 | ISEC2016-54,SITE2016-44,LOIS2016-32 |
| 発行日 | 2016-10-31 (ISEC, SITE, LOIS) |
| 研究会情報 | |
| 研究会 | ISEC / LOIS / SITE |
|---|---|
| 開催期間 | 2016/11/7(から2日開催) |
| 開催地（和） | 福井市地域交流プラザ AOSSA 6階601（BC）研修室 |
| 開催地（英） | Community Hall & AOSSA Mall, Fukui |
| テーマ（和） | 情報セキュリティ，ライフログ活用技術，ライフインテリジェンス，オフィス情報システム，一般 |
| テーマ（英） | |
| 委員長氏名（和） | 満保 雅浩(金沢大) / 西 宏之(崇城大) / 岡田 仁志(NII) |
| 委員長氏名（英） | Masahiro Mambo(Kanazawa Univ.) / Hiroyuki Nishi(Sojo Univ.) / Hitoshi Okada(NII) |
| 副委員長氏名（和） | 小川 一人(NHK) / 藤岡 淳(神奈川大) / 山田 智広(NTT) / 森住 哲也(神奈川大) / 小川 賢(神戸学院大) |
| 副委員長氏名（英） | Kazuto Ogawa(NHK) / Atsushi Fujioka(Kanagawa Univ.) / Tomohiro Yamada(NTT) / Tetsuya Morizumi(Kanagawa Univ.) / Masaru Ogawa(Kobe Gakuin Univ.) |
| 幹事氏名（和） | 駒野 雄一(東芝) / 水木 敬明(東北大) / 渡部 智樹(NTT) / 一藤 裕(長崎大) / 多川 孝央(九大) / 芳賀 高洋(岐阜聖徳学園大) |
| 幹事氏名（英） | Yuichi Komano(Toshiba) / Takaaki Mizuki(Tohoku Univ.) / Tomoki Watanabe(NTT) / Yu Ichifuji(Nagasaki Univ.) / Takahiro Tagawa(Kyushu Univ.) / Takahiro Haga(Gifu Shotoku Gakuen Univ.) |
| 幹事補佐氏名（和） | 大東 俊博(東海大) / 須賀 祐治(インターネットイニシアティブ) / 猪俣 敦夫(東京電機大) / 中村 幸博(NTT) / 川口 嘉奈子(東京藝術大) |
| 幹事補佐氏名（英） | Toshihiro Ohigashi(Tokai Univ.) / Yuuji Suga(IIJ) / Atsuo Inomata(Tokyo Denki Univ.) / Yukihiro Nakamura(NTT) / Kanako Kawaguchi(Tokyo Univ. of the Arts) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Security / Technical Committee on Life Intelligence and Office Information Systems / Technical Committee on Social Implications of Technology and Information Ethics |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 特別な形の素因数を持つ合成数の楕円曲線法による素因数分解 |
| サブタイトル（和） | |
| タイトル（英） | Factorization of Composite Numbers having a Prime of Special Form with Elliptic Curve Method |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 楕円曲線法 / Elliptic curve method |
| キーワード(2)（和/英） | 素因数分解 / Prime factorizetion |
| キーワード(3)（和/英） | アノマラス曲線 / Anomalous curve |
| キーワード(4)（和/英） | 剰余環 / Residue ring |
| 第 1 著者 氏名（和/英） | 白勢 政明 / Masaaki Shirase |
| 第 1 著者 所属（和/英） | 公立はこだて未来大学(略称：公立はこだて未来大) Future University Hakodate(略称：FUN) |
| 発表年月日 | 2016-11-07 |
| 資料番号 | ISEC2016-54,SITE2016-44,LOIS2016-32 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | ISEC-289,SITE-290,LOIS-291 |
| ページ範囲 | pp.19-26(ISEC), pp.19-26(SITE), pp.19-26(LOIS), |
| ページ数 | 8 |
| 発行日 | 2016-10-31 (ISEC, SITE, LOIS) |