M.A. Cherepniov: Version of block Lanczos-type algorithm for solving sparse linear systems, p.225-230

Abstract:

A new version of block algorithm for solving sparse systems of linear equations over $GF(2)$ is described in the talk. The algorithm involves block Pade approximations. The running time of the algorithm can be made less then running time of the known Wiedemann-Coppersmith algorithm by selection larger value of block factor with fixed RAM volume.

Key Words: Linear sparse systems over GF(2), Padé approximations, Lanczos-type algorithm, Integer factorization.

2000 Mathematics Subject Classification: Primary: 11Y05;
Secondary: 11-02.

Download the paper in pdf format here.