Systolic finite field multiplier over GF(2m), because of its superior features such as high throughput and regularity, is highly desirable for many demanding cryptosystems. On the other side, however, obtaining high-performance systolic multiplier with relatively low hardware cost is still a challenging task due to the fact that the systolic structure usually involves large area complexity. Based on this consideration, in this paper, we propose to carry out two novel coherent interdependent efforts. First, a new digit-serial multiplication algorithm based on polynomial basis over binary field (GF(2m)) is proposed. Novel Toeplitz matrix-vector product (TMVP)-based decomposition strategy is employed to derive an efficient subquadratic space complexity. Second, The proposed algorithm is then innovatively mapped into a low-complexity systolic multiplier, which involves less area-time complexities than the existing ones. A series of resource optimization techniques also has been applied on the multiplier which optimizes further the proposed design (it is the first report on digit-serial systolic multiplier based on TMVP approach covering all irreducible polynomials, to the best of our knowledge). The following complexity analysis and comparison confirm the efficiency of the proposed multiplier, that is, it has lower area-delay product (ADP) than the existing ones. The extension of the proposed multiplier for bit-parallel implementation is also considered in this paper.

A bit-parallel systolic multiplier in the finite field GF(2^m) over the polynomial basis, where irreducible trinomials x^m+xⁿ+1 generate the fields GF(2^m) is presented. The latency of the proposed multiplier requires only 2m−1 clock cycles. The architecture has the advantage of low latency, low circuit complexity and high throughput, as compared with traditional systolic multipliers. Moreover, the multiplier is highly regular, modular, and therefore, well-suited for VLSI implementation.

For cryptographic algorithms, such as elliptic curve digital signature algorithm (ECDSA) and pairing algorithm, the crypto-processors are required to perform large number of additions and multiplications over finite fields of large orders. To have a balanced trade-off between space complexity and time complexity, in this paper, novel digit-serial and digit-parallel systolic structures are presented for computing multiplication over GF(2^m). Based on novel decomposition algorithm, we have derived an efficient digit-serial systolic architecture, which involves latency of O(√{m/d}) clock cycles, while the existing digit-serial systolic multipliers involve at least O(m/d) latency for digit-size d. The proposed digit-serial design could be used for AESP-based fields with the same digit-size as the case of trinomial-based fields with a small increase in area. We have also proposed digit-parallel systolic architecture employing n-term Karatsuba-like method, where the latency can be reduced from O(√{m/d}) to O(√{m/nd}). This feature would be a major advantage for implementing multiplication for the fields of large orders. From synthesis results, it is shown that the proposed architectures have significantly lower time complexity, lower area-delay product, and higher bit-throughput than the existing digit-serial multipliers.

Normal and dual bases are two popular representation bases for elements in GF(2m). In general, each distinct representation basis has its associated different hardware architecture. In this paper, we will present a unified systolic array multiplication architecture for both normal and dual bases, such a unified multiplication architecture is termed a Hankel multiplier. The Hankel multiplier has lower space complexity while compared with other existing normal basis multipliers and dual basis multipliers.

A Montgomery's algorithm in GF(2^m) based on the Hankel matrix–vector representation is proposed. The hardware architecture obtained from this algorithm indicates low-complexity bit-parallel systolic multipliers with irreducible trinomials. The results reveal that the proposed multiplier saves approximately 36% of space complexity as compared to an existing systolic Montgomery multiplier for trinomials. A scalable and systolic Montgomery multiplier is also developed by applying the block-Hankel matrix–vector representation. The proposed scalable systolic architecture is demonstrated to have significantly less time–area product complexity than existing digit-serial systolic architectures. Furthermore, the proposed architectures have regularity, modularity and local interconnectability, making them highly appropriate for VLSI implementation.