ABSTRACT
Algorithms for solving large sparse linear systems over the finite rings ZM constitute the basic theme for this chapter. Arguably, this is not part of number theory. However, given the importance of our ability to quickly solve such systems in connection with factoring and discrete-logarithm algorithms, a book on computational number theory has only little option to ignore this topic. The sieving phases of factoring and discrete-log algorithms are massively parallelizable. On the contrary, the linear-algebra phases resist parallelization efforts, and may turn out to be the bottleneck in practical implementations.
