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.

In  Advances in Cryptography -- Proceedings of CRYPTO '90

Publisher  Springer Verlag
All copyrights reserved by Springer 2007.

Details