Show simple item record

dc.contributor.advisorVeni Madhavan, C E
dc.contributor.authorSrikanth, Cherukupally
dc.date.accessioned2010-08-16T11:11:00Z
dc.date.accessioned2018-07-31T04:39:53Z
dc.date.available2010-08-16T11:11:00Z
dc.date.available2018-07-31T04:39:53Z
dc.date.issued2010-08-16
dc.date.submitted2008-03
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/820
dc.description.abstractLarge 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.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG22444en_US
dc.subjectBlock Lanczos Algorithmen_US
dc.subjectAlgorithms (Computer Science)en_US
dc.subjectSieve Matricesen_US
dc.subjectNumber Field Sieve (NFS)en_US
dc.subjectWiedemann Algorithmen_US
dc.subjectSparse Matricesen_US
dc.subjectBlock Lanczosen_US
dc.subjectSieve Matrixen_US
dc.subject.classificationComputer Scienceen_US
dc.titleLarge Scale Implementation Of The Block Lanczos Algorithmen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record