Design Of GF(2~m) Multiplier Based On Extended Karatsuba Algorithm

Efficient hardware implementation of the finite field arithmetic,especially for GF（2^m）,is frequently desired in coding theory and public-key cryptosystems.Among these arithmetic operations in GF（2^m）,multiplication is one of the most critical operations,as other complicated field operations such as exponentiation and inversion,which can be carried out by iterative multiplications.Thus,designing an efficient multiplier algorithm is the basis for quickly implementing cryptographic algorithms and coding theory.Time complexity and space complexity are two important indicators for measuring the efficiency of a multiplier.Reducing these two indicators is a main goal of constructing an efficient multiplier.Based on the three-term or n-term Karatsuba algorithm and the Mastrovito method,this paper proposes four GF（2^m）bit-parallel hybrid multipliers.This type of multiplier has greater improvements in space-time complexity than the classic scheme.Part of the results reached the best indicators of currently known results.Firstly,for GF（2^m）defined by a special irreducible trinomial x^m+x^k+1,m=3k,the three-term Karatsuba algorithm and shift polynomial basis are used to design a bit-parallel multiplier with better space-time complexity.Compared with the classic multiplier,this multiplier saves about 1/3 of the logic circuit gate,and its time complexity is almost the same as the classic multiplier.This is also the first time that the optimal space complexity result has been achieved without increasing the delay.Secondly,the above method is generalized to GF（2^m）defined by the more general irreducible trinomial x^m+x^k+1,m=3k+1,m=3k+2.The space complexity of the designed efficient multiplier is almost the same as that of the solution when m=3k.Finally,a new type of Mastrovito multiplier is designed for the irreducible trinomial x^m+x^k+1,m=nk by further using the n-term Karatsuba algorithm.This scheme takes full advantage of the characteristics of the trinomial and n-term Karatsuba algorithm,which greatly reduces the complexity of the modulo operation and simplifies the complexity of the multiplier.The lower limit of the space complexity of the designed efficient multiplier is approximately O(m²/2+m^3/2).At the same time,the time complexity is the same as the best known Karatsuba algorithm multiplier.