A parallel version of a binary method and vector addition chains precomputation for exponentiation in RSA / Siti Khatijah Nor Abdul Rahim and Siti Rozanae Ismail

Exponentiation is a fundamental operation that exists in most computational number theory. It is one of the dominant parts of algorithms for key exchange, electronic signatures and authentication in cryptography. Encryption and decryption in RSA is achieved through exponentiation. There are various approaches to achieve exponentiation. One of those is the Binary Method. In this project, we implemented a parallel version of this Binary Method. Exponentiation can be time consuming; however it depends on the algorithms and the implementation used. Precomputing some of the powers is an option to speed up exponentiation which can save time too. However, we also constructed an algorithm for a parallel version of Vector Addition Chains to enhance the performance. Prior to that, a study on the existing sequential version was conducted and analyzed. It has been proven that a significant speedup were achieved using this new approach.