Cryptology ePrint Archive: Report 2020/438

Fast hybrid Karatsuba multiplier for Type II pentanomials

Yin Li and Yu Zhang and Wei He

Abstract: We continue the study of Mastrovito form of Karatsuba multipliers under the shifted polynomial basis (SPB), recently introduced by Li et al. (IEEE TC (2017)). A Mastrovito-Karatsuba (MK) multiplier utilizes the Karatsuba algorithm (KA) to optimize polynomial multiplication and the Mastrovito approach to combine it with the modular reduction. The authors developed a MK multiplier for all trinomials, which obtain a better space and time trade-off compared with previous non-recursive Karatsuba counterparts. Based on this work, we make two types of contributions in our paper.

FORMULATION. We derive a new modular reduction formulation for constructing Mastrovito matrix associated with Type II pentanomial. This formula can also be applied to other special type of pentanomials, e.g. Type I pentanomial and Type C.1 pentanomial. Through related formulations, we demonstrate that Type I pentanomial is less efficient than Type II one because of a more complicated modular reduction under the same SPB; conversely, Type C.1 pentanomial is as good as Type II pentanomial under an alternative generalized polynomial basis (GPB).

EXTENSION. We introduce a new MK multiplier for Type II pentanomial. It is shown that our proposal is only one $T_X$ slower than the fastest bit-parallel multipliers for Type II pentanomial, but its space complexity is roughly 3/4 of those schemes, where $T_X$ is the delay of one 2-input XOR gate. To the best of our knowledge, it is the first time for hybrid multiplier to achieve such a time delay bound.

Category / Keywords: implementation / Karatsuba algorithm, hybrid multiplier, Mastrovito, Shifted polynomial basis, Type II pentanomial

Date: received 15 Apr 2020, last revised 27 Jul 2020

Contact author: yunfeiyangli at gmail com

Available format(s): PDF | BibTeX Citation

Note: Fix some formulation errors

Version: 20200728:034545 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]