Challenges in Solving Large Sparse Linear Systems over Finite Fields
Richard P. Brent · 2005
This talk outlines how very large, sparse linear systems arise in the solution of problems of interest in computational number theory and public-key cryptography, such as the integer factorization and discrete logarithm problems. The linear systems are over finite fields, often the field GF(2) of two elements. We describe some algorithms for solving large sparse linear systems over GF(2), and compare them with algorithms for the real field. In particular, some ”iterative” algorithms which are well-known to numerical analysts, such as the conjugate gradient and Lanczos algorithms, can be adapted to work over GF(2), but there are significant differences between algorithms for the real field and for GF(2).