Exploration of Karatsuba Algorithm for Efficient Barrett Modular Multiplication

As a key operation in contemporary cryptosystems, modular multiplication occupies non-negligible latency and area. We first show optimizations of the k-term Karatsuba algorithm for AB/rk and ABmodrk that play a significant role in modular multiplication. We prove the bijective mapping between AB/rk and ABmodrk, and propose four methods to build efficient Karatsuba multiplications with arbitrary k values. For k1,32, the multiplication cost for AB/rk and ABmodrk is 25.04% less than that for AB on average. Furthermore, we investigate the correlation between operand bitwidth N of modular multiplication and decomposition factor k of the Karatsuba algorithm. Karatsuba multiplication with a larger k needs less area in the multiplication phase, but also has a more complex implementation in the evaluation and interpolation phases. Experimental results for Barrett modular multiplication with N=32, 64, 128, 256 and k=1, 2, 4, 8 show that modular multiplication achieves the minimal area when N/k=32. For instance, our proposed design when N=256 saves 21.57% area and 25.71% area/throughput, compared with state-of-art designs.