Comparing Partial and Full Return Spectral Methods

Abstract

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ı

Öz

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.

References

1. ANSI, 2001. X9.62-2001. Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography, Draft Version.
2. Baktir, S. 2008. Frequency Domain Finite Field Arithmetic for Elliptic Curve Cryptography, Ph.D. Thesis, Electrical and Computer Engineering Department, Worcester Polytechnic Institute, Worcester, MA, USA, April.
3. Baktir, S., Kumar, S., Paar, C. and Sunar, B. 2007. A State-of-the-Art Elliptic Curve Cryptographic Processor Operating in the Frequency Domain. Mobile Networks and Applications (MONET). 12 (4), 259–270.
4. Blahut, R. E. 1985. Fast Algorithms for Digital Signal Processing, Addison-Wesley Publishing Company.
5. Bunimov, V. and Schimmler, M. 2003. Area and Time Efficient Modular Multiplication of Large Integers. ASAP’03.
6. IEEE, 1999. P1363: Standard Specifications for Public-Key Cryptography, November 12, Draft Version.
7. Koblitz, N. 1987. Elliptic Curve Cryptosystems. Mathematics of Computation. (48), 201–209.
8. Miller, V. 1986. Use of Elliptic Curves Cryptography. Advances in Cryptology; Proc. Crypto’85, LNCS 218, Springer-Verlag. 417–426.

9. Montgomery, P. L. 1985. Modular Multiplication without Trial Division. Mathematics of Computation. 44 (170), 519–521.
10. NIST, 2009. Fips Pub. 186-3: Digital Signature Standard (DSS), June.
11. Nussbaumer, H. J. 1982. Fast Fourier Transform and Convolution Algorithms, Springer, Berlin, Germany.
12. Pollard, J. M. 1976. Implementation of Number Theoretic Transform. Electronics Letters. 12 (15), 378–379.
13. Rivest, R. L., Shamir, A. and Adleman, L. 1978. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM. 21 (2), 120–126.
14. Saldamlı, G. 2005. Spectral Modular Arithmetic, Ph.D. Thesis. Department of Electrical and Computer Engineering, Oregon State University.
15. Saldamli, G. and Koc¸ C. K. 2007. Spectral Modular Exponentiation. ARITH’07: Proceedings of the 18th IEEE Symposium on Computer Arithmetic. 123–132.
16. Schönhage, A. and Strassen, V. 1971. Schnelle Multiplikation Grosser Zahlen. Computing. (7), 281–292.
17. Tenca A. F. and Koc, C. K. 1999. A wordBased Algorithm and Scalable Architecture for Montgomery Multiplication. Lecture Notes in Computer Science, Springer-Verlag. (1717), 94–108.
18. Todorov, G., Tenca A. F. and Koc, C. K. 2001. High-Radix Design of a Scalable Modular Multiplier. Lecture Notes in Computer Science, Springer-Verlag. (1717), 189–206.