Solving Large Sparse Linear Systems over Finite Fields

Brian A. LaMacchia and Andrew 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.

Full Text

 

Brian A. LaMacchia
bal@farcaster.com
This page last updated: 18 Aug 2008