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