| 講演名 | 2004/3/9 行列の分割処理によるBlock Lanczos法の並列実装(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会) 田中 寛晃, 小池 正修, 四方 順司, 松本 勉, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 現在,多くの公開鍵暗号方式の安全性は,素因数分解問題の困難性に基づいており,この問題に関する困難性評価を行うことは非常に重要であると言える.数体ふるい法は現在最も高速な素因数分解アルゴリズムとして知られているが,その過程において,GF(2)上のsparseな行列で与えられる大規模な線形方程式を解く必要がある.MontgomeryのBlock Lanczos法はこのような線形方程式を高速に解く手法として知られており,本稿では,このBlock Lanczos法に注目し,行列を分割して演算を行う並列化手法の実装を目的とする.そして我々の実装では,RSA Factoring Challengeの記録に対し実行時間を60～70%に削減できたので,その成果を報告する. |
| 抄録(英) | Currently, the security in many public-key cryptographic techniques is based on the difficulty of the integer factorization problem. Therefore, it is important to evaluate how this problem is actually intractable. Currently, the Number Field Sieve is known as the most effective algorithm for computing the integer factorization. This algorithm includes a procedure to solve a linear equation represented by a large sparse matrix over the field GF(2). Montgomery's Block Lanczos method is currently known to be an effective algorithm to solve such a large linear equation. In this paper, we focus on Montgomery's Block Lanczos method and propose parallel processing by partitioning matricies in calculation. Our method reduced the execution time to around 60 ～ 70 % compared with the record of the RSA Factoring Challenge. |
| キーワード(和) | 素因数分解 / Block Lanczos法 / 並列化 / クラスタ / MPI |
| キーワード(英) | integer factorization problem / Block Lanczos method / parallel proccessing / cluster / MPI |
| 資料番号 | IT2003-80,ISEC2003-120,WBS2003-198 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2004/3/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 行列の分割処理によるBlock Lanczos法の並列実装(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会) |
| サブタイトル（和） | |
| タイトル（英） | An Implementation of Block Lanczos Method by Parallel Processing Based on Matrix Partitioning |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 素因数分解 / integer factorization problem |
| キーワード(2)（和/英） | Block Lanczos法 / Block Lanczos method |
| キーワード(3)（和/英） | 並列化 / parallel proccessing |
| キーワード(4)（和/英） | クラスタ / cluster |
| キーワード(5)（和/英） | MPI / MPI |
| 第 1 著者 氏名（和/英） | 田中 寛晃 / Hiroaki TANAKA |
| 第 1 著者 所属（和/英） | 横浜国立大学大学院環境情報研究院 Graduate School of Environment and Information Sciences Yokohama National University |
| 第 2 著者 氏名（和/英） | 小池 正修 / Masanobu KOIKE |
| 第 2 著者 所属（和/英） | 横浜国立大学大学院環境情報研究院 Graduate School of Environment and Information Sciences Yokohama National University |
| 第 3 著者 氏名（和/英） | 四方 順司 / Junji SHIKATA |
| 第 3 著者 所属（和/英） | 横浜国立大学大学院環境情報研究院 Graduate School of Environment and Information Sciences Yokohama National University |
| 第 4 著者 氏名（和/英） | 松本 勉 / Tsutomu MATSUMOTO |
| 第 4 著者 所属（和/英） | 横浜国立大学大学院環境情報研究院 Graduate School of Environment and Information Sciences Yokohama National University |
| 発表年月日 | 2004/3/9 |
| 資料番号 | IT2003-80,ISEC2003-120,WBS2003-198 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 713 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |