Presentation | 2004/3/9 An Implementation of Block Lanczos Method by Parallel Processing Based on Matrix Partitioning Hiroaki TANAKA, Masanobu KOIKE, Junji SHIKATA, Tsutomu MATSUMOTO, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | integer factorization problem / Block Lanczos method / parallel proccessing / cluster / MPI |
Paper # | IT2003-80,ISEC2003-120,WBS2003-198 |
Date of Issue |
Conference Information | |
Committee | ISEC |
---|---|
Conference Date | 2004/3/9(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Information Security (ISEC) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | An Implementation of Block Lanczos Method by Parallel Processing Based on Matrix Partitioning |
Sub Title (in English) | |
Keyword(1) | integer factorization problem |
Keyword(2) | Block Lanczos method |
Keyword(3) | parallel proccessing |
Keyword(4) | cluster |
Keyword(5) | MPI |
1st Author's Name | Hiroaki TANAKA |
1st Author's Affiliation | Graduate School of Environment and Information Sciences Yokohama National University() |
2nd Author's Name | Masanobu KOIKE |
2nd Author's Affiliation | Graduate School of Environment and Information Sciences Yokohama National University |
3rd Author's Name | Junji SHIKATA |
3rd Author's Affiliation | Graduate School of Environment and Information Sciences Yokohama National University |
4th Author's Name | Tsutomu MATSUMOTO |
4th Author's Affiliation | Graduate School of Environment and Information Sciences Yokohama National University |
Date | 2004/3/9 |
Paper # | IT2003-80,ISEC2003-120,WBS2003-198 |
Volume (vol) | vol.103 |
Number (no) | 713 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |