Efficient M -ary Exponentiation over GF(2^) 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 a...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on circuits and systems. I, Regular papers Regular papers, 2014-11, Vol.61 (11), p.3125-3134
Main Authors: Chiou-Yng Lee, Meher, Pramod Kumar, Chien-Ping Chang
Format: Article
Language:English
Subjects:
Complexity theory
Computer architecture
Cryptography
Delays
Elliptic curves
Exponentiation
Karatsuba algorithm
Logic gates
Montgomery multiplication
Polynomials
three-operand multiplication
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 m-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 √m-1 multiplication delays, while traditional exponentiators require nearly m 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 m-ary exponentiator.
ISSN:1549-8328
1558-0806
DOI:10.1109/TCSI.2014.2334992