Efficient $M$ -ary Exponentiation over $GF(2^{m})$ Using Subquadratic KA-Based Three-Operand Montgomery Multiplier

摘要

Karatsuba algorithm (KA) is popularly used for high-precision multiplication of long binary polynomials. The only well-known subquadratic multipliers using KA scheme are, however, based on conventional two-operand polynomial multiplication. In this paper, we propose a novel approach based on 2-way and 3-way KA decompositions for computing three-operand polynomial multiplications. Using these novel KA decompositions, we present here a new subquadratic Montgomery multiplier. Our proposed multiplier involves less area and less delay compared to the schoolbook three-operand multiplier as well as the two-operand multipliers based on conventional KA decomposition. We have used the proposed three-operand Montgomery multiplication to derive a novel efficient scheme for -ary exponentiation, and proposed a novel architecture for exponentiation. We have analyzed the complexities of proposed design, and shown that the proposed exponentiator can have a small lower bound on time complexity amounting to multiplication delays, while traditional exponentiators require nearly multiplication delays. From synthesis results, it is shown that the proposed exponentiator using subquadratic three-operand multiplier approach has significantly less time complexity, less area-delay product, and less power consumption than the existing exponentiators. Moreover, exponentiation-based cryptosystems, such as pairing based cryptography, could achieve high-speed operation using by our proposed multiplier and -ary exponentiator.