Abstract:

Karatsuba and Toom-3 are two popular algorithms in multiple-precision integer multiplication. The paper focuses on the hardware implementation of the two algorithms as there is few work concentrating on the comprehensive analysis of these two algorithms currently. Two high-performance multiple-precision multipliers of Karatsuba and Toom-3 are proposed, which are designed and implemented on Virtex-5 XC5VSX240T FPGA. The experiments show that the Toom-3 multiplier costs more area and latencies due to the data dependency and exact division operation, and Karatsuba multiplier performs better and takes up less area than Toom-3 in medium precision.

Key words: multiplier;FPGA;Karatsuba;Toom-3;exact division