Comparing Partial and Full Return Spectral Methods
İhsan Haluk Akın1, Gökay Saldamlı2, Murat Aydos31Fatih Üniversitesi, Mühendislik Fakültesi, Bilgisayar Müh. Bölümü, İstanbul2Boğaziçi Üniversitesi, Uygulamalı Bilimler Yüksekokulu, Yönetim Bilişim Sistemleri Bölümü, İstanbul
3Pamukkale Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Denizli
An analysis on the arithmetic complexity of recently proposed spectral modular arithmetic – in particular spectral modular multiplication- is presented through a step-by-step evaluation. Standart use of spectral methods in computer arithmetic instructs to utilize separated multiplication and reduction steps taking place in spectrum and time domains respectively. Such a procedure clearly needs full return (forward and backward) DFT calculations. On the other hand, by calculating some partial values on-the-fly, new methods adopt an approach that keeps the data in the spectrum at all times, including the reduction process. After comparing the timing performances of these approaches, it is concluded that full return algorithms perform better than the recently proposed methods.
Keywords: Spectral modular arithmetic, Modular reduction, Modular multiplication, Montgomery reduction.Kısmi ve Tam Dönümlü Spektral Metotların Karşılaştırması
İhsan Haluk Akın1, Gökay Saldamlı2, Murat Aydos31Fatih Üniversitesi, Mühendislik Fakültesi, Bilgisayar Müh. Bölümü, İstanbul2Boğaziçi Üniversitesi, Uygulamalı Bilimler Yüksekokulu, Yönetim Bilişim Sistemleri Bölümü, İstanbul
3Pamukkale Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Denizli
Bu çalışmada, yakın zamanda sunulmuş spektral modüler aritmetik işlemlerinin aritmetik karmaşıklığı üzerindeki bir analiz adım adım değerlendirme yöntemi ile karşılaştırılmıştır. Bilgisayar aritmetiğinde spektral yöntemlerin standart kullanımı çarpma ve indirgeme adımlarının spektrum ve zaman uzayında birbirinden ayrı olarak gerçekleştirilmesi gerektiğini belirtmektedir. Bu tarz bir prosedür ise açıkça tam dönümlü (ileri ve geri yönde) DFT hesaplamalarına ihtiyaç duymaktadır. Öte yandan, bazı kısmı değerlerin işlem sırasında hesaplanması ile, yeni yöntemler indirgeme işlemi de dahil olmak üzere tüm verilerin tüm zamanlarda spektrumda tutulmasını gerektiren bir yaklaşımı benimsemişlerdir. Tüm bu yaklaşımların işlem süresi performanslarını karşılaştırdığımızda, tam dönümlü algoritmaların son zamanlarda önerilmiş yöntemlerden daha iyi performans gösterdiğini bu çalışmada göstermiş bulunmaktayız.
Anahtar Kelimeler: Spektral modüler aritmetik, Modüler indirgeme, Modüler çarpma, Montgomery indirgeme.Corresponding Author: Murat Aydos
Manuscript Language: English