Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Solving Large Sparse Linear Systems Over Finite Fields

B. A. LaMacchia and A. M. Odlyzko

Abstract

Many of the fast methods for factoring integers and computing discrete logarithms require the solution of large sparse linear systems of equations over finite fields. This paper presents the results of implementations of several linear algebra algorithms. It shows that very large sparse systems can be solved efficiently by using combina- tions of structured Gaussian elimination and the conjugate gradient, Lanczos, and Wiedemann methods.

Details

Publication typeInproceedings
Published inAdvances in Cryptography -- Proceedings of CRYPTO '90
Pages109-133
Volume537
PublisherSpringer Verlag
> Publications > Solving Large Sparse Linear Systems Over Finite Fields