Presentation | 2003/3/19 Coarse Grain Parallel Processing of Block Lanczos Method Taira SUGAWARA, 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 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 Fiels 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Block Lanczos method / Parallelize / Task Dividing / OpenMP |
Paper # | IT2002-60,ISEC2002-118,SST2002-166,ITS2002-143 |
Date of Issue |
Conference Information | |
Committee | ISEC |
---|---|
Conference Date | 2003/3/19(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) | Coarse Grain Parallel Processing of Block Lanczos Method |
Sub Title (in English) | |
Keyword(1) | Block Lanczos method |
Keyword(2) | Parallelize |
Keyword(3) | Task Dividing |
Keyword(4) | OpenMP |
1st Author's Name | Taira SUGAWARA |
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 | 2003/3/19 |
Paper # | IT2002-60,ISEC2002-118,SST2002-166,ITS2002-143 |
Volume (vol) | vol.102 |
Number (no) | 743 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |