Efficient computations with special large sparse matrices

Abstract

Large sparse matrices find many applications in cryptography. A large sparse matrix is a matrix of huge dimensions but the number of nonzero entries per row of the matrix is very small. Most of the times, it is possible to modify the algorithms used for the normal dense matrices in such a way that they can handle the sparse matrices efficiently. Sparsity can be used to break the problem into two or more subproblems. This allows us to work on subproblems of smaller size and occasionally we can introduce parallelism. Here, we look at two challenging problems associated with a large sparse matrices. The first is reducing a large sparse lattice basis and the second is filtering the number field sieve(NFS) matrix. In the case of a large sparse lattice basis reduction, we propose a graph based heuristic which can be used to reduce the large sparse lattice basis effectively. We will show that the sparsity can be used to break the problem into subproblems and solve them effectively and in a parallel manner. In the case of filtering, we propose a new approach for filtering a very huge sieve matrix on a single high end machine as well as in parallel using multiple machines.