Pendekatan alternatif operasi multi-perpangkatan dengan metode modifikasi Straus's

PRIYANTO, Heri, Dr. Volker Mueller, Dipl.Inf

2003 | Tesis | S2 Teknik Elektro

Laporan ini menyajikan pembahasan dan hasil-hasil implementasi tiga algoritma multi-perpangkatan yaitu Algoritma Straus’s, Algoritma Modifikasi Straus’s (dua algoritma dengan tahap pra-komputasi dan tahap evaluasi) dan Algoritma de Rooij (algoritma tanpa tahap pra-komputasi). Dalam penelitian ini, penulis mengajukan trik baru untuk tahap pra-komputasi pada Algoritma Straus’s yang diimplementasi pada Algoritma Modifikasi Straus’s. Algoritma-algoritma tersebut dibandingkan unjuk kerjanya dengan menerapkan ide dari Müller [Mül00] yaitu penggunaan bilangaan basis berjumlah banyak (yaitu, 8, 9 dan 10 basis). Pada akhir laporan ini disajikan fakta-fakta perilaku ketiga algoritma multi-perpangkatan dan ditunjukkan juga hasil-hasil praktis dari semua algoritma.

This thesis presents implementation results for three multi-exponentiation algorithms. The three algorithms are Straus's Algorithm, a modification of Straus's Algorithm (both algorithms use a pre-computation stage), and de Rooij's Algorithm (a multiexponentiation algorithm without pre-computation stage). We propose a new trick for the pre-computation stage of Straus's Algorithm in the new modified Straus's Algorithm. To compare the performance of these algorithms, we generalize Müller's idea which uses a large number of bases g (i.e., 8, 9 or 10 bases) as input for the algorithms. Finally, we present facts on the characteristics of these multi-exponentiation algorithm and show practical results for all the algorithms.

Kata Kunci : Komputer,Multi Perpangkatan,Modifikasi Strauss, Multi-exponentiation, Straus's Algorithm, Modification of Straus's Algorithm, de Rooij Algorithm.