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

Yıl 2017, Cilt: 3 Sayı: 2, 22 - 32, 31.12.2017

SEDAT Akleylek NURŞAH Kaya

https://doi.org/10.18640/ubgmd.373313

Öz

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

Kaynakça

• [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)