Menghitung x^n secara naif mengalikan x sebanyak n kali — kompleksitas O(n). Untuk n = 10^18 (umum di kriptografi), ini mustahil selesai. Fast exponentiation (juga disebut binary exponentiation atau exponentiation by squaring) memangkas kompleksitas menjadi O(log n) dengan trik: x^n = (x^(n/2))² bila n genap. Pada Chapter ini kita menurunkan versi rekursif dan iteratif, lalu memodifikasinya untuk komputasi modular — fondasi RSA, Fermat’s little theorem, dan matrix exponentiation.

Ide Dasar: Bagi Dua #

Aturan #

Untuk sembarang n ≥ 0:

text 
x^0 = 1
x^n = (x^(n/2))²          bila n genap
x^n = x · x^(n-1)         bila n ganjil

Setiap iterasi membagi n dengan 2 (genap) atau mengurangi 1 (ganjil, lalu genap). Total iterasi ≤ 2 · log₂(n).

Mekanisme: Mengapa Kompleksitasnya O(log n) #

Representasi biner n memiliki ⌈log₂(n+1)⌉ bit. Loop iteratif membaca tiap bit sekali: setiap bit 1 menghasilkan satu kali perkalian dengan r, setiap bit (termasuk 0) menghasilkan satu kali kuadrat x. Maka total operasi perkalian adalah O(log n).

Versi Rekursif #

Aturan #

Implementasi langsung dari formula di atas. Basis n = 0 → 1.

Mekanisme: Stack Frame per Iterasi #

Versi rekursif memanggil diri sendiri log₂(n) kali. Setiap stack frame menyimpan parameter x, n, m — total O(log n) memori stack. Untuk n ≤ 10^18 (~60 bit), maksimum ~60 frame — aman.

Versi Iteratif #

Aturan #

Manfaatkan representasi biner n. Misalkan n = b_k b_{k-1} ... b_1 b_0 dalam biner. Maka:

text 
x^n = x^{Σ b_i · 2^i} = ∏ (x^(2^i))^{b_i}

Loop scan bit dari LSB ke MSB. Pada setiap langkah:

  • Bila bit b_i = 1, kalikan r dengan x (yang bernilai x^(2^i) saat ini).
  • Update x ← x² (sehingga pada iterasi berikutnya, x bernilai x^(2^(i+1))).

Kode: Tiga Versi #

cpp 
#include <iostream>

// Versi rekursif: x^n = (x^(n/2))^2 bila n genap, x * x^(n-1) bila n ganjil
long long powerRecursive(long long x, long long n, long long m) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long half = powerRecursive(x, n / 2, m);
        return (half * half) % m;
    } else {
        return (x * powerRecursive(x, n - 1, m)) % m;
    }
}

// Versi iteratif: scan bit representasi biner n
long long powerIterative(long long x, long long n, long long m) {
    long long r = 1;
    x %= m;
    while (n > 0) {
        if (n & 1) r = (r * x) % m;   // bit aktif -> kalikan ke r
        x = (x * x) % m;               // squared x untuk bit berikutnya
        n >>= 1;
    }
    return r;
}

// Versi tanpa modulo (long long, berpotensi overflow)
long long powerPlain(long long x, long long n) {
    long long r = 1;
    while (n > 0) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

int main() {
    long long m = 1'000'000'007;

    // 2^10 = 1024
    std::cout << "2^10 = " << powerIterative(2, 10, m) << '\n';

    // 2^100 mod 1e9+7
    std::cout << "2^100 mod 1e9+7 = " << powerIterative(2, 100, m) << '\n';

    // Verifikasi rekursif vs iteratif
    bool ok = true;
    for (int n = 0; n <= 1000; ++n) {
        if (powerRecursive(7, n, m) != powerIterative(7, n, m)) {
            ok = false;
            std::cerr << "Mismatch at n=" << n << '\n';
        }
    }
    std::cout << "Konsistensi recursive vs iterative (n=0..1000): "
              << (ok ? "OK" : "FAIL") << '\n';

    // Fermat's little theorem: a^(p-1) ≡ 1 mod p untuk p prima, gcd(a,p)=1
    long long p = 1'000'000'007;
    long long a = 12345;
    std::cout << "Fermat: " << a << "^(p-1) mod p = "
              << powerIterative(a, p - 1, p) << " (expected 1)\n";

    // 2^62 (without mod)
    std::cout << "2^62 = " << powerPlain(2, 62) << '\n';
    std::cout << "Expected:    4611686018427387904\n";

    // Perbandingan: naive O(n) vs fast O(log n) — output sama untuk 10^18
    long long big = powerIterative(2, 62, m);
    std::cout << "2^62 mod 1e9+7 = " << big << '\n';

    return 0;
}

Output yang Dihasilkan:

text 
2^10 = 1024
2^100 mod 1e9+7 = 976371285
Konsistensi recursive vs iterative (n=0..1000): OK
Fermat: 12345^(p-1) mod p = 1 (expected 1)
2^62 = 4611686018427387904
Expected:    4611686018427387904
2^62 mod 1e9+7 = 145586002
  1. Baris if (n == 0) return 1;: base case. x^0 = 1 untuk sembarang x (termasuk 0^0 = 1 menurut konvensi kombinatorial).
  2. Baris long long half = powerRecursive(x, n / 2, m);: hitung x^(n/2) sekali, simpan di half. Rekursi tunggal — bukan powerRecursive(...) * powerRecursive(...) yang akan menggandakan kerja.
  3. Baris x %= m; (iteratif): normalisasi x ke [0, m) di awal. Mencegah overflow intermediate.
  4. Baris if (n & 1) r = (r * x) % m;: bila bit LSB n adalah 1, kalikan r dengan x (yang bernilai x^(2^i) untuk bit ke-i). Modulo setelah perkalian.
  5. Baris x = (x * x) % m;: kuadratkan x — untuk iterasi berikutnya, x bernilai x^(2^(i+1)) = (x^(2^i))².
  6. Baris n >>= 1;: geser bit n ke kanan — baca bit berikutnya (LSB baru).
  7. Hasil 2^10 = 1024: trivial, verifikasi algoritma benar untuk n kecil.
  8. Hasil 2^100 mod 1e9+7 = 976371285: perhitungan dalam ~7 iterasi (log₂(100) ≈ 6.6). Tanpa fast exponentiation, akan butuh 100 perkalian.
  9. Hasil konsistensi OK: kedua versi (rekursif + iteratif) sepakat untuk n = 0..1000. Bukti implementasi benar.
  10. Hasil Fermat 12345^(p-1) mod p = 1: konfirmasi Fermat’s little theorem — untuk prima p = 10⁹+7, a^(p-1) ≡ 1 (mod p) selama a tidak kelipatan p. Inilah yang memungkinkan modular inverse via Fermat.
  11. Hasil 2^62 = 4611686018427387904: implementasi powerPlain tanpa modulo. Hasil 19-digit muat di long long (max ~9.2 × 10¹⁸).

Modular Exponentiation #

Aturan #

Untuk menghitung x^n mod m, mod setelah setiap operasi perkalian:

text 
r = (r * x) % m     // bila bit n aktif
x = (x * x) % m     // kuadrat

Kompleksitas tetap O(log n) — hanya konstanta modulo yang ditambahkan.

Mekanisme: Mengapa Modulo Bisa Dilakukan di Setiap Langkah #

Properti modulo: (a · b) mod m = ((a mod m) · (b mod m)) mod m. Karena x^n dihitung sebagai produk berantai x · x · x · ..., kita boleh modulo setiap intermediate tanpa mengubah hasil akhir. Ini menjaga r dan x selalu < m, mencegah overflow bila m < 2^31 (untuk long long aman hingga m < 2^62).

Aplikasi #

RSA Cryptography #

Dekripsi RSA: m = c^d mod n, dengan d eksponen privat (sering 2048-bit). Tanpa fast exponentiation, operasi ini mustahil. Kompleksitas O(log d) ~ O(2048) perkalian modular — selesai dalam millisecond.

Fermat’s Little Theorem #

Untuk prima p dan a tidak habis dibagi p:

text 
a^(p-1) ≡ 1 (mod p)
a^(p-2) ≡ a^(-1) (mod p)     (modular inverse via Fermat)

Aplikasi: hitung a^(-1) mod p dengan satu kali power(a, p-2, p) — basis modular inverse. Lihat Chapter Modular Inverse .

Matrix Exponentiation #

Bila basis x adalah matriks (bukan skalar), x^n adalah perkalian matriks. Kompleksitas O(M³ log n) di mana M ukuran matriks. Aplikasi:

  • Fibonacci ke-n dalam O(log n) via matriks [[1,1],[1,0]]^n.
  • Hitung jumlah path panjang k pada graph dengan adjacency matrix A^k.
  • Hitung ekspresi rekuren linier orde-d dalam O(d³ log n).

Primality Test (Miller–Rabin) #

Miller–Rabin: tulis n - 1 = 2^s · d dengan d ganjil. Tes apakah a^d ≡ 1 (mod n) atau a^(2^r · d) ≡ -1 (mod n) untuk beberapa r < s. Probabilistik, kompleksitas O(k · log²n) untuk k ronde. Digunakan untuk primality test n hingga 2⁸⁰+.

Ringkasan #

  • Fast exponentiation: x^n dalam O(log n) via x^n = (x^(n/2))² (genap) atau x · x^(n-1) (ganjil).
  • Versi rekursif: langsung dari rumus; stack O(log n).
  • Versi iteratif: scan bit n dari LSB, kalikan r saat bit aktif, kuadratkan x setiap iterasi.
  • Modular: mod setelah setiap perkalian — aman bila m < 2^31 (atau 2^62 dengan __int128).
  • Aplikasi: RSA dekripsi, Fermat’s little theorem, modular inverse, matrix exponentiation (Fibonacci, path counting), Miller–Rabin primality test.