Low-Complexity Digit-Serial and Scalable SPB/GPB Multipliers Over Large Binary Extension Fields Using (b,2)-Way Karatsuba Decomposition

Shifted polynomial basis (SPB) and generalized polynomial basis (GPB) are two variations of polynomial basis representation. SPB/GPB have potential for efficient bit-level and digit-level implementations of multiplication over binary extension fields. This paper presents a (b,2)-way KA decomposition for digit-serial multiplication with low-space complexity. Based on the proposed parallel (b,2)-way KA scheme, we derive a novel scalable SPB/GPB multiplier. Analytical results show that the proposed multiplier could achieve the desired trade-off between space and time complexities. Our proposed multiplier is modular, regular, and suitable for very-large-scale integration (VLSI) implementations. It involves significantly less area complexity, less computation time and less energy consumption compared to the existing digit-serial and scalable multipliers.