Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract)
Gilles Villard · 1997
We analyse the probability of success of the block algorithm proposed by Coppersmith for solving large sparse systems Aw = O of linear equations over a field K. Itis based on a modification of a scheme proposed by Wiedemann.An open question was to prove that the block algorithm may produce a solution for small finite fields e.g. for K =GF(2).Our investigations allow us to answer this question nearly completely.We prove that the input parameters of the algorithm may be tuned such that, for any input system, a solution is computed with high probability for any field.Conversely, for particular input systems, we show that the conditions on the input parameters may be relaxed to ensure the success.We also improve the previous probability measurements in the case of large cardkmlity fields. 'The whole proofs has been sent to the referees.They may be found in [30]