Novel bit-parallel multiplier for GF(2m)GF(2m) defined by all-one polynomial using generalized Karatsuba algorithm

• We construct a bit-parallel multiplier for AOP based on a generalized Karatsuba algorithm.
• We examine the influence about multiplier efficiency with respect to decomposition of polynomial degree.
• The lower bound of the space complexity is m2/2+O(m{3/2})+O(m)m2/2+O(m{3/2})+O(m).
• The time complexity nearly matches the fastest multiplier for AOP.

In this paper, a novel bit-parallel multiplier for finite field GF(2m)GF(2m) defined by irreducible all-one polynomial (AOP) is proposed. We utilize a generalized Karatsuba algorithm (KA) to reduce the number of coefficient multiplications and the redundant representation to simplify polynomial modular reduction. Explicit formulae with respect to the space and time complexity of the proposed multiplier are given. By evaluating the asymptotic lower bound of the complexity, the selection of the generalized KA and decomposition of m   are investigated to obtain the optimal result. Consequently, theoretical complexity analysis proved that our architecture requires even fewer logic gates than previous proposals, while it still maintains relatively low time delay. For a special class of GF(2m)GF(2m) generated with AOPs, it even matches the best known multipliers found in the literatures.