Parallel Block Lanczos for solving large binary systems
MetadataShow full item record
The Lanczos algorithm is very useful in solving a large, sparse linear system A x = y and then finding vectors in the kernel of A. Such a system may arise naturally through number factoring algorithms for example. In this thesis, we present a variant of the binary Lanczos algorithm that directly finds vectors in the kernel of A without first solving the system. The number factoring algorithms ultimately require us to find such vectors. Our adaptation combines ideas of Peter Montgomery and Don Coppersmith. We also discuss implementation issues, including parallelization.