Parallel Algorithm for Polynomial Basis Multiplier in GF(2 m

Fast multiplication in a finite field GF(2m) is a basis step in communications engineering applications, such as error-correcting codes or cryptograph algorithms. A new parallel algorithm on the polynomial basis bit-parallel multiplier is presented. This new parallel algorithm saves about 25% execution time while comparing with the conventional algorithms. The hardware version for the proposed parallel algorithm is also invented. The new hardware structure requires only the space complexity of O(m) while existing multipliers need the space complexity of O(m2). The time complexity of the proposed multiplier takes only about half of the time complexity of the existing Lee’s multiplier