Exploration of Karatsuba Algorithm for Efficient Barrett Modular Multiplication

Recommended citation: Exploration of Karatsuba Algorithm for Efficient Barrett Modular Multiplication. Bo Zhang, Mingzhe Zhang, Shoumeng Yan. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD).

Abstract

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.

Abstract source