Novel bit-parallel multiplier for defined by all-one polynomial using generalized Karatsuba algorithm

详细信息    查看全文

• 作者：Xiao-ning Xie ; Gong-liang Chen ; Yin Li
• 关键词：Generalized Karatsuba algorithm ; Bit-parallel multiplier ; All-one polynomial ; Redundant representation ; Cryptography
• 刊名：Information Processing Letters
• 出版年：March, 2014
• 年：2014
• 卷：114
• 期：3
• 页码：140-146
• 全文大小：258 K

文摘

In this paper, a novel bit-parallel multiplier for finite field 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 generated with AOPs, it even matches the best known multipliers found in the literatures.