Date Added: Mar 2011
A parallel hardware architecture for the solution of linear equation systems implemented over finite fields is presented in this paper. This proposed hardware architecture could be efficiently employed in the Multivariate Public Key Cryptosystems for hardware implementation. A hardware-paralleled variant of the Gaussian elimination is adopted and is expressed as a series of multiplications with three inputs over finite fields, where the basic common computations can be shared to reduce computational complexity. Its average running time for solving a linear system Ax = b equals n clock cycles, where A is a n x n matrix with uniformly distributed entries. In other words, it reduces time complexity to O(n).