Title :
A new architecture for a parallel finite field multiplier with low complexity based on composite fields
Author_Institution :
Dept. of Electr. & Comput. Eng., Worcester Polytech. Inst., MA
fDate :
7/1/1996 12:00:00 AM
Abstract :
A bit parallel structure for a multiplier with low complexity in Galois fields is introduced. The multiplier operates over composite fields GF((2n)m), with k=nm. The Karatsuba-Ofman algorithm (A. Karatsuba and Y. Ofmanis, 1963) is investigated and applied to the multiplication of polynomials over GF(2n). It is shown that this operation has a complexity of order O(klog23 ) under certain constraints regarding k. A complete set of primitive field polynomials for composite fields is provided which perform module reduction with low complexity. As a result, multipliers for fields GF(2k) up to k=32 with low gate counts and low delays are listed. The architectures are highly modular and thus well suited for VLSI implementation
Keywords :
Galois fields; computational complexity; parallel algorithms; parallel architectures; polynomials; Galois fields; VLSI implementation; bit parallel structure; composite fields; gate counts; low complexity; module reduction; parallel finite field multiplier; polynomial multiplication; primitive field polynomials; Cryptography; Delay; Digital communication; Error correction codes; Galois fields; Graphics; Hardware; Information theory; Polynomials; Very large scale integration;
Journal_Title :
Computers, IEEE Transactions on
