Eksponensial modular — menghitung a^b mod m — terlihat seperti latihan aritmatika sederhana, namun menghitungnya secara efisien itulah yang membuat kriptografi kunci publik modern menjadi praktis. Kalkulator ini menghitung a^b mod m menggunakan algoritme kuadrat dan perkalian dan menunjukkan cara kerjanya secara tepat, sedikit demi sedikit.
Mengapa tidak menghitung a^b saja lalu mengambil sisanya?
Untuk bilangan kecil, menghitung a^b secara langsung dan kemudian mengurangi mod m berfungsi dengan baik. Namun operasi kriptografi menggunakan eksponen dan modulus yang panjangnya ratusan digit — a^b sendiri akan memiliki digit yang jauh lebih banyak daripada atom di alam semesta yang dapat diamati, jauh sebelum Anda mencapai langkah "mod m". Kuadrat dan perkalian menghindari hal ini sepenuhnya dengan mengurangi modulo m setelah setiap pengkuadratan dan perkalian, sehingga tidak ada nilai antara yang melebihi m. Dikombinasikan dengan fakta bahwa ia hanya membutuhkan perkalian log2(b) dan bukan b − 1, inilah yang membuat operasi seperti enkripsi RSA dengan eksponen 2048-bit selesai dalam milidetik dan bukannya tidak mungkin dilakukan secara komputasi.
Membaca tab Langkah Kuadrat dan Kalikan dan Eksponen Biner
Algoritme memindai digit biner eksponen dari yang paling signifikan hingga yang paling tidak signifikan. Di setiap bit, ini mengkuadratkan hasil yang berjalan dan mengurangi mod m; jika bit itu 1, bit itu juga dikalikan dengan basis dan dikurangi lagi. Tab Eksponen Biner menunjukkan bit mana yang 1 dan mana yang 0 — setiap 1-bit merupakan satu perkalian tambahan di luar kuadrat yang dibutuhkan setiap bit. Eksponen 20-bit, betapapun besarnya angka desimal yang diwakilinya, tetap hanya memerlukan 20 kuadrat dan paling banyak 20 perkalian.
Batasan dan kasus tepi
Kalkulator ini hanya mendukung eksponen non-negatif. Eksponen negatif — seperti a^(-1) mod m — memerlukan komputasi invers modular a, yang hanya ada jika a dan m koprima dan memerlukan algoritme yang berbeda (algoritme Euclidean yang diperluas) seluruhnya; itu tidak didukung di sini. Modulus 1 selalu menghasilkan 0, karena setiap bilangan bulat habis dibagi 1. Dan meskipun basisnya dapat dimasukkan sebagai negatif, basis tersebut dinormalisasi ke dalam rentang [0, m) sebelum algoritme berjalan, sesuai dengan konvensi matematika standar bahwa mod m selalu non-negatif.