## 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).

## Abstract

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.
## Comments

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