Efficient Large-Width Montgomery Modular Multiplier Design Based on Toom–Cook-5

Toom–Cook-n multiplication is an efficient large-width multiplication algorithm based on a divide-and-conquer strategy, widely used in modular multiplication operations for cryptographic algorithms. Theoretically, as the degree n increases, Toom–Cook-n can split the multiplicands into more sub-terms to further enhance the performance of the multiplier. However, constrained by the computational burden brought by the growing size of the interpolation matrix as the degree increases, current research predominantly focuses on Toom–Cook-4 and Toom–Cook-3. This paper proposes a Montgomery modular multiplication design based on Toom–Cook-5, which alleviates the computational difficulty of the interpolation step by introducing an interpolation matrix pre-simplification strategy. Additionally, the design incorporates and optimizes carry–save adder and Karatsuba multiplication, enabling Toom–Cook-5 multiplication to be applied in practical and efficient hardware implementation. This paper presents the ASIC implementation results of the hardware architecture under a 90nm process, demonstrating superior performance compared to previous works.