Block Wiedemann algorithm
The block Wiedemann algorithm for computing kernel vectors of a matrix over a finite field is a generalization by Don Coppersmith of an algorithm due to Doug Wiedemann. Wiedemann's algorithm Let be an square matrix over some finite field F, let be a random vector of length , and let . Consider the sequence of vectors obtained by repeatedly multiplying the vector by the matrix ; let be any other vector of length , and consider the sequence of finite-field elements We know that the matrix has a minimal polynomial; by the Cayley–Hamilton theorem we know that this polynomial is of degree (which we will call ) no more than . Say . Then ; so the minimal polynomial of the matrix annihilates the sequence and hence . But the Berlekamp–Massey algorithm allows us to calculate relatively efficiently some sequence with . Our hope is that this sequence, which by construction annihilates , actually annihilates ; so we have . We then take advantage of the initial definition of to say and so is a hopefully non-zero kernel vector of . The block Wiedemann (or Coppersmith-Wiedemann) algorithm The natural implementation of sparse matrix arithmetic on a computer makes it easy