ÜÇ TERİMLİ POLİNOMLAR İÇİN KARATSUBA BENZERİ ÇARPMA YÖNTEMLERİNİN ARAŞTIRILMASI

Bu çalışmada, katsayıları tamsayı olan iki polinomu aritmetik karmaşıklık açısından daha verimli çarpan yöntemlerin araştırılması hedeflenmektedir. Bu yüzden, Böl-ve-Fethet mantığını kullanan, Karatsuba-Ofman Algoritmasından yola çıkarak çarpma işlemlerini daha az maliyetli toplama/çıkarma işlemleriyle değiştiren denklemler bulan bir yazılım geliştirilmiştir. Geliştirilen uygulamada, üç terimli iki polinomun katsayılarının olası kombinasyonları kullanılarak çarpma işleminden sonra bütün çarpım katsayılarının bulunup bulmadığını test edilmektedir. Üç terimli polinomları çarpmak için 3 farklı yöntem olduğu ve bu yöntemlerin hepsinde 6 çarpma, 13 toplama/çıkarma işlemine ihtiyaç duyulduğu hesaplanmıştır. Bunlara ek olarak, daha fazla terimli polinomların çarpımı için ne tür uygulamalara ihtiyaç duyulduğu konusunda detaylara da yer verilmiştir.

Anahtar Kelimeler:

Polinom çarpımı, aritmetik karmaşıklık, sembolik hesaplama, Karatsuba-Ofman, Böl-ve-Fethet

PDF

___

[1] Von zur Gathen, J. ve J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013.
[2] Knuth, D. The Art of Computer Programming, 3rd ed., vol. 2. Seminumerical Algorithms, Addison-Wesley Longman, Amerika, 1997.
[3] Karatsuba, A. ve Y. Ofman, “Multiplication of Many-Digital Numbers by Automatic Computers”, Physics-Doklady, 1963.
[4] Cook, T. ve A. Stephen, On the Minimum Computation Time of Functions, Doktora Tezi, Harvard University, Department of Mathematics, 1966.
[5] Heideman, M., D. Johnson ve C. Burrus, “Gauss and the history of the fast fourier transform”, IEEE ASSP Dergisi, Cilt 1, 14-21, 1984.
[6] Fürer, M. “Faster Integer Multiplication”, Pennsylvania State University, Amerika, 2007.
[7] Montgomery, P. L. “Five, Six, and Seven-Term Karatsuba-Like Formulae”, IEEE Transactions On Computers Dergisi, Cilt 54, Numara:3, 2005, syf. 362-369.
[8] Paar, C. ve A. Weimerskirch, “Generalizations of the Karatsuba Algorithm for Efficient Implementations”, Ruhr-Universty Bochum, Almanya, 2006, http://eprint.iacr.org/2006/224.pdf (Son erişim tarihi: 15 Mart 2017).
[9] Jankoqski, K., P. Laurent ve A. O’Mahony, Intel Polynomial Multiplication Instruction and its Usage for Elliptic Curve Cryptography, Intel White Paper, 2012, http://www.intel.co.kr/content/dam/www/public/us/en/documents/white-papers/polynomial-multiplication-instructions-paper.pdf (Son erişim tarihi: 15 Mart 2017)