Perpustakaan Digital ITB

Banyak penelitian dikembangkan untuk mengurangi operasi perkalian untuk pengali polinom di GF(2n). Hal ini penting karena hubungannya dengan efisiensi dalam perangkat terbatas, seperti dalam kriptografi kurva eliptik. Dua penelitian mengenai hal ini adalah penelitian yang dilakukan oleh Paar untuk n=4 dan Montgomery untuk n=5,6,7. Penelitian mereka lebih baik dari penelitian sebelumnya, tetapi mereka tidak menjelaskan metode yang mereka lakukan, bagaimana mereka dapat menemukan pengali-pengali tersebut. Ini adalah kesenjangan pengetahuan yang ditemui, dan dalam penelitian ini telah ditemukan metode yang lebih baik dari apa yang telah mereka lakukan dalam mencari pengali tersebut. Langkah pertama adalah pengembangan formula yang lebih baik dari formula atau metode Generalizations of The Karatsuba Algorithm, setelah itu pengembangan algoritma pencarian yang lengkap untuk semua kemungkinan elemen pengali yang ada. Selanjutnya, penggabungan formula dan algoritma tersebut, yang disebut sebagai algoritma NAYK. Algoritma ini dapat mengurangi perkalian secara signifikan, yaitu dengan mengidentifikasi beberapa elemen perkalian yang termasuk dalam solusi dan beberapa elemen perkalian yang tidak termasuk dalam solusi, sehingga sisa elemen perkalian berkurang secara signifikan. Kemudian dengan menggunakan elemen-elemen perkalian yang telah diidentifikasi yang termasuk dalam solusi, dan dengan mengacu pada batas atas dari fungsi O(n) pada pengali dari Montgomery, maka kekurangan elemennya ditambahkan dari kombinasi elemen sisa yang ada. Algoritma ini menghasilkan ruang pencarian yang lebih kecil secara signifikan dibandingkan dengan algoritma Montgomery. Algoritma ini cocok dan mempunyai dampak signifikan jika diterapkan di composite field.