Performance Comparison of Vedic and Karatsuba Algorithm for 64-Bit Barrett Modular Multiplication
Handy Jonarta, Rafael Aditya Cahyo W, Muhammad Ogin Hasanuddin, Infall Syafalni, Nana Sutisna, Wildan Trusaji, Trio Adiono · 2024
Modular multiplication finds application in various fields that rely on cryptographic and finite-field arithmetic. Basically, modular multiplication are consist of two main parts namely integer multiplication, and modular reduction. In this paper we examine two of well known integer multiplication namely, vedic and karatsuba for integer multiplication, and we use barrett reduction for modular reduction part. For comparison we use 64-bit as parameter size for modulus bit size, and we implement using target board alveo 250. As the result show that our implementation of the Vedic-based modular multiplier demonstrates a 23.08% improvement in area usage compared to the Karatsuba method, while the Karatsuba-based approach achieves a 29.41% improvement in efficiency. These results highlight the potential for optimizing modular multiplication in cryptographic applications by selecting appropriate algorithms based on specific performance requirements.