IISc Logo    Title

etd AT Indian Institute of Science >
Division of Electrical Sciences >
Computer Science and Automation (csa) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2005/820

Title: Large Scale Implementation Of The Block Lanczos Algorithm
Authors: Srikanth, Cherukupally
Advisors: Veni Madhavan, C E
Keywords: Block Lanczos Algorithm
Algorithms (Computer Science)
Sieve Matrices
Number Field Sieve (NFS)
Wiedemann Algorithm
Sparse Matrices
Block Lanczos
Sieve Matrix
Submitted Date: Mar-2008
Series/Report no.: G22444
Abstract: Large sparse matrices arise in many applications, especially in the major problems of Cryptography of factoring integers and computing discrete logarithms. We focus attention on such matrices called sieve matrices generated after the sieving stage of the algorithms for integer factoring. We need to solve large sparse system of equations Bx = 0, with sieve matrices B arising in this context. The traditional Gaussian elimination, with a cubic run time, is not efficient for handling such matrices. Better algorithms for such input matrices are the quadratic runtime algorithms based on Block Lanczos(BL) or Wiedemann techniques. Of these two, BL is even better for large integer factoring algorithms. We carry out an efficient implementation of the Block Lanczos algorithm for finding the vectors in the null space of the the sieve matrix. We report our test results using our implementation for matrices of sizes up to 106. We plan to use this implementation in our ongoing projects on factoring the large RSA challenge integers of sizes 640 bits(called RSA-640) and beyond. So it is useful to exploit possible parallelism. We propose a scheme for parallelizing certain steps of the Block Lanczos method, taking advantage of structural properties of the sieve matrix. The sizes of matrices arising in integer factoring context are quite large. Hence we also discuss some techniques that are used to reduce the size of the sieve matrix. We also consider the last stage of the NFS Algorithm for finding square roots of large algebraic numbers and outline a sketch of our algorithm.
URI: http://etd.iisc.ernet.in/handle/2005/820
Appears in Collections:Computer Science and Automation (csa)

Files in This Item:

File Description SizeFormat
G22444.pdf288.74 kBAdobe PDFView/Open

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.


etd@IISc is a joint service of SERC & IISc Library ||
|| Powered by DSpace || Compliant to OAI-PMH V 2.0 and ETD-MS V 1.01