Solving sparse linear equations over finite fields

A "coordinate recurrence" method for solving sparse systems of linear equations over finite fields is described. The algorithms discussed all require field operations, where is the maximum dimension of the coefficient matrix, is approximately the number of field operations required to apply the matrix to a test vector, and the value of depends on the algorithm. A probabilistic algorithm is shown to exist for finding the determinant of a square matrix. Also, probabilistic algorithms are shown to exist for finding the minimum polynomial and rank with some arbitrarily small possibility of error.