Spectral modular multiplication

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Edebiyat Fakültesi, Matematik Bölümü, Türkiye

Tezin Onay Tarihi: 2009

Öğrenci: İHSAN HALUK AKIN

Danışman: ALİ DOĞANAKSOY

Özet:

Spectral methods have been widely used in various fields of engineering and applied mathematics. In the field of computer arithmetic: data compression, polynomial multiplication and the spectral integer multiplication of Sch¨onhage and Strassen are among the most important successful utilization. Recent advancements in technology report the spectral methods may also be beneficial for modular operations heavily used in public key cryptosystems. In this study, we evaluate the use of spectral methods in modular multiplication. We carefully compare their timing performances with respect to the full return algorithms. Based on our evaluation, we introduce new approaches for spectral modular multiplication for polynomials and exhibit standard reduction versions of the spectral modular multiplication algorithm for polynomials eliminating the overhead of Montgomery’s method. Moreover, merging the bipartite method and standard approach, we introduce the bipartite spectral modular multiplication to improve the hardware performance of spectral modular multiplication for polynomials. Finally, we introduce Karatsuba combined bipartite method for polynomials and its spectral version.