Low Space Complexity <inline-formula> <tex-math notation="LaTeX">$GF(2^m)$ </tex-math></inline-formula> Multiplier for Trinomials Using <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-Term Karatsuba Algorithm

We propose bit-parallel GF(2^m) multipliers for irreducible trinomials using an n-term Karatsuba algorithm and Mastrovito approach, which are generalizations of the newly proposed multiplication scheme for a specific trinomial. The complexities of the proposed multipliers for GF(2^m) depend on the choice of an irreducible trinomial x^m + x^k + 1 defining GF(2^m) and values n, m₀ such that m = nm₀ or m = nm₀ + 1. It is possible to achieve a space-time tradeoff by choosing proper values for k, n, and m₀. For the purpose of a specific comparison, we compare the proposed multipliers with the best-known multipliers for an odd m &#x2208; [399, 450] for which there exists an irreducible trinomial of degree m. As a result, the proposed multipliers achieve the lowest space complexities among similar bit-parallel multipliers (they have roughly 40% reduced space complexities compared with the fastest multiplier). On the other hand, their time complexities match or are at most 2T_X higher than the fastest multipliers, where T_X is the delay of one 2-input XOR gate.

Abstract licence: CC BY-NC-ND

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.