Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study
Files
Publication date
2006
Authors
Bisseling, R.H.
Flesch, I.
Editors
Joubert, G.R.
Nagel, W.E.
Peters, F.J.
Plata, O.
Tirado, P.
Zapata, E.
Advisors
Supervisors
DOI
Document Type
Part of book
Metadata
Show full item recordCollections
License
Abstract
A case study is presented demonstrating the application of the Mondriaan package for sparse matrix partitioning to the field of cryptology. An important step in an integer factorisation attack on the RSA public-key cryptosystem is the solution of a large sparse linear system with 0/1 coefficients, which can be done by the block Lanczos algorithm proposed by Montgomery. We parallelise this algorithm using Mondriaan partitioning and discuss the high-level components needed. A speedup of 10 is obtained on 16 processors of a Silicon Graphics Origin 3800 for the factorisation of an integer with 82 decimal digits, and a speedup of 7 for 98 decimal digits.
Keywords
Mathematics, Wiskunde en computerwetenschappen, Landbouwwetenschappen, Wiskunde: algemeen
Citation
Bisseling, R H & Flesch, I 2006, Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Laczos algorith - a case study. in G R Joubert, W E Nagel, F J Peters, O Plata, P Tirado & E Zapata (eds), Parallel computing : Current and Future Issues of High-end Computing, Proceedings ParCo 2005. NIC series, vol. 33, John von Neumann Institute for Computing, Jülich, Germany, pp. 819-826.