Block Wiedemann algorithm

The block Wiedemann algorithm, also called the Coppersmith-Wiedemann algorithm, computes kernel vectors of a matrix over a finite field. It is a generalization by Don Coppersmith of an algorithm due to Doug Wiedemann. Wiedemann's original method takes a random vector, builds the sequence of vectors obtained by repeatedly multiplying it by the matrix, and uses the Berlekamp-Massey algorithm to find a sequence that annihilates it, which yields a hopefully non-zero kernel vector. The block version computes the sequences for many vectors at once, taking advantage of the fact that sparse matrix arithmetic on a computer handles as many vectors as the width of a machine word in no more time than one, and that several processors can work on different sets of random vectors in parallel. A generalization of the Berlekamp-Massey algorithm that produces a sequence of small matrices then recovers a kernel vector of the large matrix.