O'Reilly logo

Public-key Cryptography: Theory and Practice by C. E. Veni Madhavan, Abhijit Das

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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(n3) and space O(n2). There are asymptotically faster algorithms like Strassen’s method [292] that takes time O(n2.807) and Coppersmith and Winograd’s method [60] having a running time of O(n2.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(n2)).

Luckily enough, cryptanalytic algorithms ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required