Random Krylov spaces over finite fields

201. R. P. Brent, S. Gao and A. G. B. Lauder, Random Krylov spaces over finite fields, SIAM Journal on Discrete Mathematics 16 (2003), 276-287. MR 1 982 139.

Preprint: dvi (25K), pdf (161K), ps (84K).


Motivated by a connection with block iterative methods for solving linear systems over finite fields, we consider the probability that the Krylov space generated by a fixed linear mapping and a random set of elements in a vector space over a finite field equals the space itself. We obtain an exact formula for this probability, and from it we derive good lower bounds that approach 1 exponentially fast as the size of the set increases.


The problem is relevant to Krylov subspace methods for solving large sparse linear systems over finite fields. Such systems arise, for example, in the MPQS and NFS methods for integer factorisation [196]. The methods of [94] are relevant to the proof of Lemma 4.

Go to next publication

Return to Richard Brent's index page