MathPemulaFase 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.
Example use case
Kriptografi RSA: menghitung pangkat modular bilangan raksasa secara efisien untuk enkripsi.
Syllabus
Menghitung pangkat dengan mengkuadratkan basis dan membagi dua eksponen, jadi jauh lebih sedikit perkalian.
Objectives
- ·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
How It Works
- ·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
Prerequisites
- ·Perpangkatan
- ·Representasi biner
Real-World Uses
- ·Kriptografi RSA yang mengamankan chat dan transaksi online
- ·Menghitung pangkat besar cepat di kalkulator atau game
Complexity O(log n)