Evaluation of Large Integer Multiplication Methods on Hardware

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)
7345 Downloads (Pure)


Multipliers requiring large bit lengths have a major impact on the performance of many applications, such as cryptography, digital signal processing (DSP) and image processing. Novel, optimised designs of large integer multiplication are needed as previous approaches, such as schoolbook multiplication, may not be as feasible due to the large parameter sizes. Parameter bit lengths of up to millions of bits are required for use in cryptography, such as in lattice-based and fully homomorphic encryption (FHE) schemes. This paper presents a comparison of hardware architectures for large integer multiplication. Several multiplication methods and combinations thereof are analysed for suitability in hardware designs, targeting the FPGA platform. In particular, the first hardware architecture combining Karatsuba and Comba multiplication is proposed. Moreover, a hardware complexity analysis is conducted to give results independent of any particular FPGA platform. It is shown that hardware designs of combination multipliers, at a cost of additional hardware resource usage, can offer lower latency compared to individual multiplier designs. Indeed, the proposed novel combination hardware design of the Karatsuba-Comba multiplier offers lowest latency for integers greater than 512 bits. For large multiplicands, greater than 16384 bits, the hardware complexity analysis indicates that the NTT-Karatsuba-Schoolbook combination is most suitable.
Original languageEnglish
Number of pages14
JournalIEEE Transactions on Computers
Early online date02 Mar 2017
Publication statusEarly online date - 02 Mar 2017


  • Large integer multiplication
  • FPGA
  • hardware complexity
  • fully homomorphic encryption


Dive into the research topics of 'Evaluation of Large Integer Multiplication Methods on Hardware'. Together they form a unique fingerprint.

Cite this