Solving Large Sparse Linear Systems over Finite Fields

Brian A. LaMacchia and Andrew M. Odlyzko


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.

Full Text


Brian A. LaMacchia
This page last updated: 18 Aug 2008