Block Wiedemann algorithm

The block Wiedemann algorithm for computing kernel vectors of a matrix over a finite field is a generalisation of an algorithm due to Don Coppersmith.

Let ${\displaystyle M}$ be an ${\displaystyle n\times n}$ square matrix over some finite field F, let ${\displaystyle x_{\mathrm {base} }}$ be a random vector of length ${\displaystyle n}$, and let ${\displaystyle x=Mx_{\mathrm {base} }}$. Consider the sequence of vectors ${\displaystyle S=\left[x,Mx,M^{2}x,\ldots \right]}$ obtained by repeatedly multiplying the vector by the matrix ${\displaystyle M}$; let ${\displaystyle y}$ be any other vector of length ${\displaystyle n}$, and consider the sequence of finite-field elements ${\displaystyle S_{y}=\left[y\cdot x,y\cdot Mx,y\cdot M^{2}x\ldots \right]}$

...
Wikipedia