Record Details

Large Scale Implementation Of The Block Lanczos Algorithm

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Large Scale Implementation Of The Block Lanczos Algorithm
 
Creator Srikanth, Cherukupally
 
Subject Block Lanczos Algorithm
Algorithms (Computer Science)
Sieve Matrices
Number Field Sieve (NFS)
Wiedemann Algorithm
Sparse Matrices
Block Lanczos
Sieve Matrix
Computer Science
 
Description 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.
 
Contributor Veni Madhavan, C E
 
Date 2010-08-16T11:11:00Z
2010-08-16T11:11:00Z
2010-08-16
2008-03
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/820
 
Language en_US
 
Relation G22444