| 講演名 | 2008/7/29 複数多項式によるMBPSの改善とHITACHI SR11000/J2での実装評価(並列計算,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ) 吉田 仁, 黒田 久泰, 後 保範, 金田 康正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 現在,インターネットにおけるSSL通信をはじめとして広く用いられている公開鍵暗号システムの一つであるRSA暗号のように,素因数分解の難しさを安全性の根拠にしている暗号システムが多数あり,その安全性の指標として高速な素因数分解の研究が行われてきている.本研究では,一般数体飾法に代わる新たな因数分解方法として提案している多数基底多項式篩法(MBPS; Multiple Base Polynomial Sieve)で多項式を複数用いる手法の提案と,複数多項式による効率の変化について調査を行った.実験の結果,多項式を複数用いることで,小さな素因数で分解可能なデータの割り合いが多項式を1つしか用いない場合と比較して最大で20倍になることが確認された. |
| 抄録(英) | Some cryptography system uses public-key authorize. SSL protocol in the internet is an example for it. It is a barometer of public-key cryptography systems how hard to factorize a large number. We are developing a new factorizing algorithm, called MBPS (Multiple Base Polynomial Sieve), and improving it. In this report, we intensively studied to use multiple polynomials in MBPS, and multiple polynomials improve the possibility to get data with small factors. As a result, sieving with multiple polynomials gets almost 20 times as many useful data as sieving with single polynomial. |
| キーワード(和) | 素因数分解 / MBPS / GNFS / 並列計算 |
| キーワード(英) | prime factoring / MBPS / GNFS / parallel computing |
| 資料番号 | CPSY2008-28 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CPSY |
|---|---|
| 開催期間 | 2008/7/29(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Computer Systems (CPSY) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 複数多項式によるMBPSの改善とHITACHI SR11000/J2での実装評価(並列計算,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ) |
| サブタイトル（和） | |
| タイトル（英） | Improvement and Evaluation of MBPS Using Multiple Polynomials on HITACHI SR11000/J2 |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 素因数分解 / prime factoring |
| キーワード(2)（和/英） | MBPS / MBPS |
| キーワード(3)（和/英） | GNFS / GNFS |
| キーワード(4)（和/英） | 並列計算 / parallel computing |
| 第 1 著者 氏名（和/英） | 吉田 仁 / Hitoshi YOSHIDA |
| 第 1 著者 所属（和/英） | 東京大学大学院新領域創成科学研究科 Graduate School of Frontier Sciences, The University of Tokyo |
| 第 2 著者 氏名（和/英） | 黒田 久泰 / Hisayasu KURODA |
| 第 2 著者 所属（和/英） | 東京大学情報基盤センター Information Technology Center, The University of Tokyo |
| 第 3 著者 氏名（和/英） | 後 保範 / Yasunori USHIRO |
| 第 3 著者 所属（和/英） | 東京工芸大学工学部 Faculty of Engineering, Tokyo Polytechnic University |
| 第 4 著者 氏名（和/英） | 金田 康正 / Yasumasa KANADA |
| 第 4 著者 所属（和/英） | 東京大学情報基盤センター Information Technology Center, The University of Tokyo |
| 発表年月日 | 2008/7/29 |
| 資料番号 | CPSY2008-28 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 180 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |