Polynomial multiplication performs as the most important task and is computationally extensive in cryptographic algorithms. Of the several polynomial multiplications, theoretically, the Toom-Cook multiplication is the most efficient. In this paper, an efficient four-way Toom-Cook (Toom-4) multiplication method has been presented that provides accurate result as the product and can be efficiently implemented in hardware. This is done by eliminating the effects of exact divisions present in the intermediate steps of the computation. In addition to these, the hardware implementation of the proposed work suggests that this multiplication method performs better in terms of resource utilization and delay minimization compared to other existing Toom-4 algorithm methods. Hardware implementation of the proposed Toom-4 multiplication architecture is done using a Virtex-7 FPGA device in Xilinx (now AMD) ISE platform. Here, the hardware implementation of the proposed multiplier is performed for 128 bits, 256 bits, and 512 bits with advantages in the area-time-product (ATP) over previous researches; ATP is the figure of merit in determining the performance of the design. Practically for 512 input bits, the percentage ATP of the proposed design is 98.810%, 23.537% and 57.316% better compared to Toom-2 (Karatsuba) multiplication, Hybrid Toom-2 (Karatsuba-Comba) multiplication, and existing Toom-4 multiplication, respectively. Moreover, ASIC implementation results on United Microelectronics Corporation (UMC) 65-nm technology demonstrate a notable reduction in area-time-product (ATP) and power-time-product (PTP) compared to state-of-the-art works.

The demand for efficient large integer polynomial multiplications in present day crypto-systems is the need of the hour. Toom-Cook multiplication algorithm being one of the most efficient multiplication algorithm is discussed in this work. The limitations of large integer polynomial multiplications using three-way Toom-Cook (Toom-3) multiplication algorithm and the methods to overcome it are presented in this paper. This is done by implementing two different division-free methods for symmetric Toom-3 multiplication as well as for asymmetric Toom-3 multiplication based on the input operand size (N). Hardware implementations of the proposed multiplication methods are done using Virtex-7 Field Programmable Gate Array (FPGA) device in Xilinx ISE platform. The trade-off between hardware utilization and speed is noted, and the overall performance of the proposed design methods are measured by calculating Area-Time-Product (ATP). Practically, it has been observed that both the proposed Toom-3 multiplication methods performs better compared to the existing state-of-the-art designs.