| 講演名 | 2003/3/19 Block Lanczos法の粗粒度並列処理について(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会) 菅原 平, 小池 正修, 四方 順司, 松本 勉, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 現在,多くの公開鍵暗号の安全性は,素因数分解問題の困難性に依拠しているため,素因数分解問題の困難性に関する解析は非常に重要であるといえる.ここで素因数分解を行うためのアルゴリズムとして,現在知られている最も効果的なものは数体ふるい法であり,そのアルゴリズムの一部では,GF(2)上のsparseな行列で与えられる大規模な線形方程式を解くためにMontgomoryのBlock Lanczos法が利用されている.本論文では,Block Lanczos法の高速化を図ることを目的として,粗粒度タスク分割による並列化手法を提案する.そして,その提案手法をOpenMPによってDual CPUマシンへ実装実験を行った結果を報告する.実装結果としては,実際に1割から3割程度の速度向上が観測できた. |
| 抄録(英) | Currently, the security of many public key cryptosystems depend on the hardness of the integer factorization problem, and the analysis of the problem is one of highly important topics in cryptography. The currently known algorithm which most, effectively works for solving the integer factorization problem is the so-called Number Field Sieve (NFS), and the algorithm includes the Montgomery's Block Lanczos method, as a subalgorithm for solving a linear equation represented by a large sparse matrix over the field GF (2). In this paper, we propose a coarse grain task parallel processing method for the Block Lanczos method with the aim of achiving more efficiency. Also, we report implementation results of our method on Dual CPU machine using Open MP. Consequently, the proposed method provides the speed-up by about 10 to 30% over the previous one. |
| キーワード(和) | Block Lanczos法 / 並列化 / タスク分割 / OpenMP |
| キーワード(英) | Block Lanczos method / Parallelize / Task Dividing / OpenMP |
| 資料番号 | IT2002-60,ISEC2002-118,SST2002-166,ITS2002-143 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ITS |
|---|---|
| 開催期間 | 2003/3/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Intelligent Transport Systems Technology (ITS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Block Lanczos法の粗粒度並列処理について(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会) |
| サブタイトル（和） | |
| タイトル（英） | Coarse Grain Parallel Processing of Block Lanczos Method |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Block Lanczos法 / Block Lanczos method |
| キーワード(2)（和/英） | 並列化 / Parallelize |
| キーワード(3)（和/英） | タスク分割 / Task Dividing |
| キーワード(4)（和/英） | OpenMP / OpenMP |
| 第 1 著者 氏名（和/英） | 菅原 平 / Taira SUGAWARA |
| 第 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 |
| 発表年月日 | 2003/3/19 |
| 資料番号 | IT2002-60,ISEC2002-118,SST2002-166,ITS2002-143 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 747 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |