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.

Coppersmith's algorithm

Let M be an $n\; imes\; n$ square matrix over some finite field F, let $x\_\{mathrm\; \{base$ be a random vector of length n, and let $x\; =\; M\; x\_\{mathrm\; \{base$. Consider the sequence of vectors $S\; =\; left\; [x,\; Mx,\; M^2x,\; ldots\; ight]$ 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 $S\_y\; =\; left\; [y\; cdot\; x,\; y\; cdot\; Mx,\; y\; cdot\; M^2x\; ldots\; ight]$

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

But the Berlekamp-Massey algorithm allows us to calculate relatively efficiently some sequence $q\_0\; ldots\; q\_L$ with $sum\_\{i=0\}^L\; q\_i\; S\_y\; [\{i+r\}]\; =0\; forall\; r$. Our hope is that this sequence, which by construction annihilates $y\; cdot\; S$, actually annihilates $S$; so we have $sum\_\{i=0\}^L\; q\_i\; M^i\; x\; =\; 0$. We then take advantage of the initial definition of $x$ to say $M\; sum\_\{i=0\}^L\; q\_i\; M^i\; x\_\{mathrm\; \{base\; =\; 0$ and so $sum\_\{i=0\}^L\; q\_i\; M^i\; x\_\{mathrm\; \{base$ is a hopefully non-zero kernel vector of $M$.

The Block Wiedemann algorithm

The natural implementation of sparse matrix arithmetic on a computer makes it easy to compute the sequence S in parallel for a number of vectors equal to the width of a machine word - indeed, it will normally take no longer to compute for that many vectors than for one. If you have several processors, you can compute the sequence S for a different set of random vectors in parallel on all the computers.

It turns out, by a generalisation of the Berlekamp-Massey algorithm to provide a sequence of small matrices, that you can take the sequence produced for a large number of vectors and generate a kernel vector of the original large matrix. You need to compute $y\_i\; cdot\; M^t\; x\_j$ for some $i\; =\; 0\; ldots\; i\_max,\; j=0\; ldots\; j\_max,\; t\; =\; 0\; ldots\; t\_max$ where $i\_max,\; j\_max,\; t\_max$ need to satisfy $t\_max\; >\; frac\{d\}\{i\_max\}\; +\; frac\{d\}\{j\_max\}\; +\; O(1)$ and $y\_i$ are a series of vectors of length n; but in practice you can take $y\_i$ as a sequence of unit vectors and simply write out the first $i\_max$ entries in your vectors at each time t.

References

Villard's 1997 research report 'A study of Coppersmith's block Wiedemann algorithm using matrix polynomials' (available at [http://citeseer.ist.psu.edu/cache/papers/cs/4204/ftp:zSzzSzftp.imag.frzSzpubzSzCALCUL_FORMELzSzRAPPORTzSz1997zSzRR975.pdf/villard97study.pdf] - the cover material is in French but the content in English) is a reasonable description.

Thomé's paper 'Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm' (available at [http://citeseer.ist.psu.edu/rd/13850609%2C564537%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/27081/http:zSzzSzwww.lix.polytechnique.frzSzLabozSzEmmanuel.ThomezSzpubliszSzjsc.pdf/subquadratic-computation-of-vector.pdf] ) uses a more sophisticated FFT-based algorithm for computing the vector generating polynomials, and describes a practical implementation with $i\_max\; =\; j\_max\; =\; 4$ used to compute a kernel vector of a 484603x484603 matrix of entries modulo 2⁶⁰⁷-1, and hence to compute discrete logarithms in the field $GF(2^\{607\})$.