Abstract
As a key operation in contemporary cryptosystems, modular multiplication (MM) occupies non-negligible latency and area. We first show optimizations of the k-term Karatsuba algorithm for $ \lfloor AB/r^{k} \rfloor $ and $AB \text {mod}~r^{k}$ that play a significant role in MM. We prove the bijective mapping between $ \lfloor AB/r^{k} \rfloor $ and $AB \text {mod}~r^{k}$ , and propose four methods to build efficient Karatsuba multiplications with arbitrary k values. For $k\in [{1, 32}]$ , the multiplication cost for $ \lfloor AB/r^{k} \rfloor $ and $AB \text {mod}~r^{k}$ is 25.04% less than that for AB on average. Furthermore, we investigate the correlation between operand bitwidth N of MM 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 MM with $N=32$ , 64, 128, 256 and $k=1$ , 2, 4, 8 show that MM 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.