FPGA-Optimized Two-Term Karatsuba Multiplications for Large Integer Multiplications
Sumit Kumar, Saubi Patel, Shubham Singh, Monalisa Das, Babita Jajodia · 2024
The demand for efficient large integer polynomial multiplications in present day crypto-systems is the need of the hour. Karatsuba-like multiplication is one of the most efficient multiplication algorithm discussed in this work. However, this algorithm is mostly practically avoided due to the presence of complex sub-multiplications at the intermediate steps of computation. Thus, efforts has been made to implement two-term Karatsuba Multiplication (Method-I & Method-II), i.e., TTKM-I and TTKM-II in terms of speed and hardware utilization. The overall performance of the proposed design methods are also noted by calculating Area-Time-Product (ATP) and compared with conventional two-term Karatsuba multiplication (CTTKM) and existing state-of-the-art. Hardware implementations of both the proposed TTKM multiplication architectures are done using Virtex-7 FPGA device in Xilinx ISE platform. Compared with other state-of-the-art designs the performance of the proposed two-term Karatsuba multiplication (Method-I) based on ΔATP1is 11.108%, 98.686%, 15.561%, 72.012%, 95.122%. 6.009% and 24.601% better than Direct Multiplication (DM), Karat-suba Direct Multiplication (KDM), Karatsuba Comba Multiplication (KCM), Traditional Schoolbook Multiplication (Traditional SBM), SBM-I, SBM-II and CTTKM respectively for 512-bit inputs. Similarly the performance of the proposed two-term Karatsuba multiplication (Method-II) based on ΔATP2is 1.790%, 98.544%, 6.407%, 68.978%. 94.593% and 16.427% better than Direct Multiplication (DM), Karatsuba Direct Multiplication (KDM), Karatsuba Comba Multiplication (KCM), Traditional SBM, SBM-I, SBM-II, CTTKM respectively for 512-bit inputs. However comparing both the proposed methods of TTKM (Method-I and Method-II), it can be inferred that TTKM-I is 9.780% better than TTKM-II thus proving its area-time-product efficiency.