Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm

摘要

In this paper we describe how the half-gcd algorithm can be adapted in order to speed up the sequential stage of Coppersmith's block Wiedemann algorithm for solving large sparse linear systems over any finite field. This very stage solves a sub-problem than can be seen as the computation of a linear generator for a matrix sequence. Our primary realm of interest is the field Fq for large prime power q. For the solution of a N × N system, the complexity of this sequential part drops from &Ogr;(N²) to &Ogr;(M(N) log N) where M(d) is the cost for multiplying two polynomials of degree d. We discuss the implications of this improvement for the overall cost of the block Wiedemann algorithm and how its parameters should be chosen for best efficiency.