An Efficient Overlap-Free Karatsuba Finite-Field Multiplier on FPGA

Finite field multipliers are widely used in various cryptography and coding system circuits. Due to their high complexity, the design quality of the multiplier determines the complexity and cost of the entire system. In order to reduce the complexity and cost of the multiplier, this paper proposes a finite field multiplier based on Overlap-free Karatsuba Algorithm (OKA). First, we analyze the theoretical number of gates and delays required for Schoolbook Multiplication Algorithm (SA), Karatsuba Algorithm (KA), and OKA. Then, we analyze the process of implementing the M-term KA algorithm when M is 3, 4, and 5. Next, we derive the Overlap-free Karatsuba Algorithm for M = 3, and use the three methods of SA, OKA2, and OKA3 for multi-level composition to implement an efficient multiplier (HA). Finally, we perform theoretical analysis and FPGA implementation on operands of 93-bit, 233-bit, and 409-bit. Our device utilization and delay indicate that the proposed HA multiplier is 20% faster than the SA multiplier, 34% faster than the standard KA multiplier, and 24% faster than the standard OKA multiplier, when compared in terms of the area-delay product (ADP). Compared with other multipliers in the literature, the proposed multiplier performs well in ADP performance evaluation.