Karatsuba Algorithm: Parallelization using CUDA

In arbitrary arithmetic computation and computational science, multiplying large integers is a widely used operation.Numerous cryptographic techniques involve operations on extremely large subsets of the integer numbers, including the Diffie-Hellman key exchange, RSA, ECC, and others.These techniques employ safe message encryption, decryption, and key exchange using security keys with a size of at least 1024 bits.Exponentiation and multiplication are necessary in order to carry out encryption, decryption, and key exchange.The Karatsuba algorithm is a fast and efficient method for multiplying large numbers, that reduces the number of multiplications from four to three at each recursive step.In this paper, we conduct a comprehensive assessment of the Karatsuba algorithm's performance when applied to both sequential and parallel contexts.We utilize the power of Nvidia Graphics Processing Unit (GPU) with Compute Unified Device Architecture (CUDA) programming to gauge the speedup of the parallel implementation and processor configurations.The speedup achieved by the Karatsuba algorithm running on Nvidia GPU CUDA platform over the sequential is 30.12.There exists an improvement in performance by making use of available GPU cores.The findings emphasize the potential advantages of parallelization in reducing the overall computation time.