Finding column depedencies in sparse matrices over $ F_ 2 $ by block Wiedemann

Large systems of linear equations over $mathbb{F_2$ with sparse coefficient matrices have to be solved as a part of integer factorization with sieve-based methods such as in the Number Field Sieve algorithm. In this report, we first discuss the Wiedemann algorithm to solve these systems and investigate the relation between the sparsity of the matrix and the performance of (a slightly adapted version of) the algorithm. Then we turn to the more efficient block algorithms and discuss a new version of the block Wiedemann algorithm, proposed by Villard, based on the FPHPS algorithm by Beckermann and Labahn. Finally we compare the performance of our implementation of this version of the algorithm with that of Lobo's implementation of the classical block Wiedemann algorithm and that of Montgomery's implementation of his block Lanczos algorithm. The latter is shown to be much faster, even more than expected theoretically.