An analysis on efficient polynomial multiplication algorithms for cryptographic purposes

Thesis Type: Postgraduate

Institution Of The Thesis: Orta Doğu Teknik Üniversitesi, Institute of Applied Mathematics, Cryptography, Turkey

Approval Date: 2016


Supervisor: MURAT CENK


The idea of Public Key Cryptography showed up after the studies conducted by W. Diffie and M. Hellman in 1976. In the light of these works, RSA, the first Public Key Cryptography algorithm, came into play. In this algorithm, modular exponentiation is highly costly. In addition to this, key sizes of public key cryptography algorithms has become longer in order to ensure the security as the time passes. For these reasons, the speed of algorithms is relatively slower when it is compared to the speed of ones in Symmetric Key Cryptography algorithms. However, Public Key Cryptography algorithms have a wide area of utilization. Thus, it is highly crucial to accelerate these algorithms. Making use of fast multiplication algorithms is an effective way to reduce the cost. In this thesis, the main point is to analyze some multiplication algorithms with respect to their time complexities. Before the invention of Karatsuba method, time complexity of multiplying two polynomials was known to be $O(n^2)$. After this invention lots of research has been done in this field. For example, Fast Fourier Transform is used for designing fast multiplication algorithms. However, this method is not efficient enough for cryptographic demands in today's world. For this reason, existing methods such as Karatsuba and its variations, Montgomery, and hybrid methods are investigated.