MatematikaPemulaFase C–FE1E5

Fast Exponentiation

Fast Exponentiation menghitung pangkat dengan mengkuadratkan basis dan membagi dua eksponen, memakai bit biner eksponen. Jadi O(log n) perkalian, bukan O(n). Fondasi kriptografi (mis. RSA) yang memakai pangkat bilangan sangat besar.

Contoh kasus

Kriptografi RSA: menghitung pangkat modular bilangan raksasa secara efisien untuk enkripsi.

Silabus

Menghitung pangkat dengan mengkuadratkan basis dan membagi dua eksponen, jadi jauh lebih sedikit perkalian.

Tujuan Belajar

·Memahami cara memecah pangkat memakai bit biner eksponen
·Menjelaskan mengapa jumlah perkalian turun jadi O(log n)
·Menerapkan teknik ini untuk pangkat modular yang besar

Cara Kerja

·Lihat eksponen dalam bentuk biner
·Kuadratkan basis di tiap langkah
·Bagi dua eksponen tiap langkah
·Kalikan hasil hanya saat bit eksponen bernilai 1
·Selesai setelah semua bit eksponen habis diproses

Prasyarat

·Perpangkatan
·Representasi biner

Contoh Nyata

·Kriptografi RSA yang mengamankan chat dan transaksi online
·Menghitung pangkat besar cepat di kalkulator atau game

Kompleksitas O(log n)