Spectral modular multiplication

Abstract

Spekral metodlar mühendisliğin ve uygulamalı matematiğin çeşitli alanlarında yaygın olarakkullanılmaktadır. Veri sıkıştırma, polinom çarpması ve Schönhage and Strassen' ın spektraltamsayılar çarpması bilgisayar aritmetik alanında en başarılı uygulamalardandır. Sonteknolojik araştırmalar spektral metodların modular operasyonların yoğun olarak kullanıldığıaçık anahtarlı sistemlerde faydalı olabiliceğini söylüyor.Bu çalışmada, spektral metodların modular çarpmada kullanımlarını değerlendirdik. Bu yöntemlerinzaman performanslarını tam dönüşlü algoritmalara karşı dikkatli şekilde karşılaştırdık.Değerlendirmemizi baz alarak, polinomlar için spektral modular çarpmaya dair yeniyaklaşımlar sunduk ve Montgomery' nin metodunun yükünü ortadan kaldıran polinomlar içinspektral modular çarpmanın standart versiyonunu sunduk.Bunun yanında, polinomlar için spektral modular çarpmanın donanım performansını geliştirmekiçin iki taraflı ve standart yaklaşımları birleştirerek iki taraflı spektal modular çarmayısunduk. Son olarak polinomlar için Karatsuba ile birleştirilmiş iki taraflı metodunu ve bununspektral versiyonunu sunduk.

Spectral methods have been widely used in various fields of engineering and applied mathematics.In the field of computer arithmetic: data compression, polynomial multiplication andthe spectral integer multiplication of Sch¨onhage and Strassen are among the most importantsuccessful utilization. Recent advancements in technology report the spectral methods mayalso 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 carefullycompare their timing performances with respect to the full return algorithms. Based on ourevaluation, we introduce new approaches for spectral modular multiplication for polynomialsand exhibit standard reduction versions of the spectral modular multiplication algorithm forpolynomials eliminating the overhead of Montgomery?s method.Moreover, merging the bipartite method and standard approach, we introduce the bipartitespectral modular multiplication to improve the hardware performance of spectral modularmultiplication for polynomials. Finally, we introduce Karatsuba combined bipartite methodfor polynomials and its spectral version