An analysis on efficient polynomial multiplication algorithms for cryptographic purposes

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Uygulamalı Matematik Enstitüsü, Kriptografi Anabilim Dalı, Türkiye

Tezin Onay Tarihi: 2016

Öğrenci: MURAT BURHAN İLTER

Danışman: MURAT CENK

Özet:

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.