Block Wiedemann algorithm

The Block Wiedemann algorithm for computing the nullspace of a matrix over a finite field is a generalisation of an algorithm due to Don Coppersmith.

Coppersmith's algorithm

Let M be an nxn square matrix over some finite field F, and let x be a random vector of length n. Consider the sequence S = x, Mx, M^2x obtained by repeatedly multiplying the vector by the matrix M; let y be any other vector of length n, and consider the sequence of finite-field elements y.x, y.Mx, y.M^2x ...

We know that the matrix M has a minimal polynomial; by the Cayley-Hamilton Theorem we know that this polynomial is of degree no more than n. Say $\sum _{r=0}^{n}p_{r}M^{r}=0$. Then $\sum _{r=0}^{n}y\cdot (p_{r}(M^{r}x))=0$; so the minimal polynomial of the matrix annihilates the sequence S.

But the Berlekamp-Massey algorithm allows us to calculate relatively efficiently some polynomial with $\sum _{i=0}^{m}q_{i}S_{i+r}=0\forall r$.