A Parallel Hardware Architecture for fast Gaussian Elimination over GF(2)

Andrey Bogdanov, M. Mertens, Chris­tof Paar, Jan Pelzl, Andy Rupp

IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2006, Napa, CA, USA, April 24-26, 2006.


This paper presents a new variant of the well-known Gaussian elimination for solving linear systems of equations (LSEs) over GF(2) and its highly ef?cient implementation in hardware. The proposed hardware architecture can solve any regular and (uniquely solvable) overdetermined LSE and is not limited to matrices of a certain structure. Its average running time for nnmatrices with uniformly distributed entries equals 2n (clock cycles) as opposed to about 1 4 n 3 in software. Moreover, the average running time remains very close to 2n for random matrices with densities much greater or lower than 0:5. Our architecture has a worst-case time complexity of O(n 2 ) and also a space complexity of O(n 2 ). With these characteristics the architecture is particularly suited to ef?- ciently solve medium-sized LSEs as they frequently appear in, e.g., cryptanalysis of stream ciphers.