Fast Exponentiation

Metode Fast exponentiation digunakan untuk menghitung operasi modulo bilangan berpangkat besar.

Misalkan g adalah suatu bilangan bulat dan z adalah bilangan bulat positif, maka untuk menghitung g^z dapat dilakukan dengan langkah–langkah berikut :
Dibentuk ekspansi biner dari bilangan bulat positif z, yaitu z =

 Karena z ditulis dengan ekspansi biner, maka a_i elemen {0,1}. Sehingga,

Jadi, diperoleh g^z dengan dengan metode fast exponentiation.

Ilustrasi perhitungan menggunakan metode fast exponentiation diberikan pada contoh berikut.

Referensi :

Buchmann, Johannes A. (2002). Introduction to Cryptography. New York: Springer-Verlag.