Low-Latency Digit-Serial Systolic Double Basis Multiplier over <formula formulatype="inline"> <tex Notation="TeX">$\mbi GF{(2^m})$</tex> </formula> Using Subquadratic Toeplitz Matrix-Vector Product Approach

Abstract

Recently in cryptography and security, the multipliers with subquadratic space complexity for trinomials and some specific pentanomials have been proposed. For such kind of multipliers, alternatively, we use double basis multiplication which combines the polynomial basis and the modified polynomial basis to develop a new efficient digit-serial systolic multiplier. The proposed multiplier depends on trinomials and almost equally space pentanomials (AESPs), and utilizes the subquadratic Toeplitz matrix-vector product scheme to derive a low-latency digit-serial systolic architecture. If the selected digit-size is <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$d$</tex> </formula> bits, the proposed digit-serial multiplier for both polynomials, i.e., trinomials and AESPs, requires the latency of <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$2\left\lceil \!{\sqrt {{m \over d}}} \right\rceil\! $</tex> </formula> , while traditional ones take at least <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$O\left({\left\lceil {{m \over d}} \right\rceil} \right)$</tex> </formula> clock cycles. Analytical and application-specific integrated circuit (ASIC) synthesis results indicate that both the area and the time <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$ \times $</tex> </formula> area complexities of our proposed architecture are significantly lower than the existing digit-serial systolic multipliers.