Public-key Cryptography: Theory and Practice

4.7. Solving Large Sparse Linear Systems over Finite Rings

So far we have seen many algorithms which require solving large systems of linear equations (or congruences). The number n of unknowns in such systems can be as large as several millions. Standard Gaussian elimination on such a system takes time O(n³) and space O(n²). There are asymptotically faster algorithms like Strassen’s method [292] that takes time O(n^2.807) and Coppersmith and Winograd’s method [60] having a running time of O(n^2.376). Unfortunately, these asymptotic estimates do not show up in the range of practical interest. Moreover, the space requirements of these asymptotically faster methods are prohibitively high (though still O(n²)).

Luckily enough, cryptanalytic algorithms ...