Exploration of Karatsuba Algorithm for Efficient Barrett Modular Multiplication
- 18 July 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 45 (2) , 867-881
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.
Keywords
This publication has 20 references indexed in Scilit:
- Efficient Reconfigurable Modular Multipliers for Post-Quantum Digital Signatures2024
- An Iterative Montgomery Modular Multiplication Algorithm With Low Area-Time ProductIEEE Transactions on Computers, 2022
- A High-Performance Low-Power Barrett Modular Multiplier for Cryptosystems2021
- A Novel Method of Modular Multiplication Based on Karatsuba-like Multiplication2020
- A High Performance Full-Word Barrett Multiplier Designed for FPGAs with DSP Resources2019
- A Design and Implementation of Montgomery Modular Multiplier2019
- Homomorphic Encryption for Arithmetic of Approximate Numbers2017
- Five, six, and seven-term Karatsuba-like formulaeIEEE Transactions on Computers, 2005
- Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor2000
- Modular multiplication without trial divisionMathematics of Computation, 1985