Spectral modular multiplication

Akın, İhsan Haluk
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.
Citation Formats
İ. H. Akın, “Spectral modular multiplication,” Ph.D. - Doctoral Program, Middle East Technical University, 2009.