Block Wiedemann algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

Let M be an n\times 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\right] 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\right]

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[edit]

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 generalization 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[edit]

Villard's 1997 research report 'A study of Coppersmith's block Wiedemann algorithm using matrix polynomials' (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' uses a more sophisticated FFT-based algorithm for computing the vector generating polynomials, and describes a practical implementation with imax = jmax = 4 used to compute a kernel vector of a 484603×484603 matrix of entries modulo 2607−1, and hence to compute discrete logarithms in the field GF(2607).