Scholarlink

<p>Toom-Cook multiplication algorithm is one of the most efficient method compared to other traditional large-integer multiplication algorithms. However, in most cases, implementation of this algorithm in hardware is practically avoided due to presence of exact-divisions at intermediate steps of computation. Thus this paper proposes ways to overcome the limitation by designing a hardware-optimized, division-free Toom-4 multiplication algorithm. This is done by eliminating the effects of division due to odd factors in the denominator using a scaling factor, at the interpolation step of the algorithm. Further optimization is done by replacing the direct point-wise multiplication with an optimized Schoolbook multiplication. The overall performance of the proposed architecture is estimated using Area-Time-Product (ATP) and hardware implementation is done using Virtex-7 FPGA device in Xilinx-ISE platform. Practically, the proposed design performs better in terms of speed and resource utilization for higher input bits compared to other state-of-the-art designs; for example for 512 input bits, the percentage ATP of the proposed design is 75.077%, 98.822% and 57.316% superior performance compared to Traditional Schoolbook Multiplication, Karatsuba (Toom-2) multiplication and Toom-4 multiplication respectively.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

ATP-Optimized Implementation of Four-Way Toom-Cook Multiplications on FPGAs for Large Integer Arithmetic

  • 期刊论文

  • 发表日期：

    2025年1月9日

查看全文
  • Monalisa Das,
  • Babita Jajodia

摘要

Toom-Cook multiplication algorithm is one of the most efficient method compared to other traditional large-integer multiplication algorithms. However, in most cases, implementation of this algorithm in hardware is practically avoided due to presence of exact-divisions at intermediate steps of computation. Thus this paper proposes ways to overcome the limitation by designing a hardware-optimized, division-free Toom-4 multiplication algorithm. This is done by eliminating the effects of division due to odd factors in the denominator using a scaling factor, at the interpolation step of the algorithm. Further optimization is done by replacing the direct point-wise multiplication with an optimized Schoolbook multiplication. The overall performance of the proposed architecture is estimated using Area-Time-Product (ATP) and hardware implementation is done using Virtex-7 FPGA device in Xilinx-ISE platform. Practically, the proposed design performs better in terms of speed and resource utilization for higher input bits compared to other state-of-the-art designs; for example for 512 input bits, the percentage ATP of the proposed design is 75.077%, 98.822% and 57.316% superior performance compared to Traditional Schoolbook Multiplication, Karatsuba (Toom-2) multiplication and Toom-4 multiplication respectively.