학술논문
FPGA-Optimized Two-Term Karatsuba Multiplications for Large Integer Multiplications
Document Type
Conference
Source
2024 11th International Conference on Signal Processing and Integrated Networks (SPIN) Signal Processing and Integrated Networks (SPIN), 2024 11th International Conference on. :274-278 Mar, 2024
Subject
Language
ISSN
2688-769X
Abstract
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 ΔATP 1 is 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 ΔATP 2 is 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.