Kalkulator Eksponensial Modular

Tentang Kalkulator Eksponensial Modular

Kalkulator Eksponensial Modular menghitung \(a^b \bmod n\) — menaikkan basis \(a\) ke eksponen \(b\) dan mengambil sisa pembagian saat dibagi oleh modulus \(n\). Alat ini menggunakan algoritma eksponensiasi biner (juga disebut daya cepat atau eksponensiasi dengan pengkuadratan), yang mereduksi operasi dari \(O(b)\) perkalian menjadi hanya \(O(\log b)\). Ini adalah algoritma yang sama yang digunakan dalam implementasi kriptografi dunia nyata seperti RSA, Diffie-Hellman, dan ElGamal.

Aplikasi Eksponensial Modular

Cara Kerja Algoritma Eksponensiasi Biner

Wawasan utamanya adalah kita dapat mendekomposisi eksponen apa pun menjadi jumlah pangkat 2 menggunakan representasi binernya. Misalnya, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), sehingga \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

Algoritma memproses digit biner dari eksponen dari kiri ke kanan:

Pseudocode

function modpow(base, exp, mod):

    result = 1

    base = base mod mod

    while exp > 0:

        if exp is odd:        // bit adalah 1

            result = (result × base) mod mod

        exp = exp >> 1        // geser kanan (bagi 2)

        base = (base × base) mod mod

    return result

Formula Utama

Cara Menggunakan Kalkulator Eksponensial Modular

1. Masukkan basis (a): Ini adalah angka yang ingin Anda pangkatkan. Bisa positif atau negatif. Misalnya, masukkan 7 untuk menghitung 7^256 mod 13.
2. Masukkan eksponen (b): Ini harus berupa bilangan bulat non-negatif. Ini mewakili pangkat. Untuk aplikasi kriptografi, ini bisa sangat besar (kalkulator mendukung hingga 10^18).
3. Masukkan modulus (n): Ini harus berupa bilangan bulat positif. Ini adalah angka pembagi untuk mendapatkan sisa. Dalam RSA, ini biasanya merupakan produk dari dua bilangan prima besar.
4. Klik Hitung: Kalkulator menghitung a^b mod n menggunakan eksponensiasi biner dan menunjukkan hasilnya secara instan.
5. Tonton animasi: Tekan Putar untuk melihat algoritma eksponensiasi biner dieksekusi langkah demi langkah. Setiap bit eksponen diproses secara berurutan, menunjukkan apakah algoritma menguadratkan, atau menguadratkan dan mengalikan.
6. Tinjau jejak: Tabel langkah demi langkah menunjukkan setiap komputasi perantara, dan perbandingan efisiensi menunjukkan seberapa jauh lebih cepat eksponensiasi biner dibandingkan perkalian berulang yang naif.

Mengapa Eksponensiasi Biner Cepat

Pertimbangkan menghitung \(2^{1000} \bmod 13\). Pendekatan naif membutuhkan 999 perkalian. Eksponensiasi biner mengubah 1000 ke biner (1111101000), yang memiliki 10 bit. Ia hanya membutuhkan maksimal 9 pengkuadratan ditambah beberapa perkalian untuk setiap bit '1' — totalnya sekitar 15 operasi. Itu berarti sekitar 98,5% lebih sedikit operasi. Untuk eksponen skala kriptografi dengan ratusan digit, perbedaannya sangat besar: metode biner membutuhkan ribuan operasi di mana metode naif akan membutuhkan lebih banyak operasi daripada jumlah atom di alam semesta.

FAQ