An Implementation of Karatsuba-based Montgomery Modular Multiplication with Only Half-size Additions
Zhen Gu, Shuguo Li · 2018
Karatsuba Multiplication constructs the product of two integers using half-size multiplications along with full-size and double-size additions. The propagation delay in full-size and double-size additions becomes an essential problem when the multiplication is iterated like in Montgomery Modular Multiplication. In this paper, we propose a method using only half-size additions to accelerate Karatsuba-based Montgomery Modular Multiplication. As a result, our implementations based on SMIC-65nm show that our method is efficient and has advantages in delay over normal implementations with similar area and power.