Area and Delay Trade-Offs in Three-Way Toom-Cook Large Integer Multipliers Implemented on FPGAs

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.