A exponenciação modular – calcular a^b mod m – parece um simples exercício aritmético, mas calculá-la de forma eficiente é o que torna prática a criptografia moderna de chave pública. Esta calculadora calcula a^b mod m usando o algoritmo de quadrado e multiplicação e mostra exatamente como funciona, bit a bit.
Por que não apenas calcular a^b e depois pegar o restante?
Para números pequenos, calcular a^b diretamente e depois reduzir mod m funciona bem. Mas as operações criptográficas usam expoentes e módulos com centenas de dígitos - o próprio a^b teria muito mais dígitos do que átomos no universo observável, muito antes de você chegar à etapa "mod m". Quadrar e multiplicar evita isso completamente, reduzindo o módulo m após cada quadratura e multiplicação, de modo que nenhum valor intermediário exceda m. Combinado com o fato de que ele precisa apenas de multiplicações log2(b) em vez de b − 1, isso é o que torna operações como a criptografia RSA com um expoente de 2.048 bits concluídas em milissegundos, em vez de serem computacionalmente impossíveis.
Lendo as guias Etapas de quadrado e multiplicação e Expoente binário
O algoritmo varre os dígitos binários do expoente do mais significativo para o menos significativo. A cada bit, ele eleva ao quadrado o resultado da execução e reduz o mod m; se esse bit for 1, ele também multiplica pela base e reduz novamente. A guia Expoente Binário mostra quais bits são 1 e quais são 0 - cada bit 1 é uma multiplicação extra além dos quadrados que cada bit exige. Um expoente de 20 bits, por maior que seja o número decimal que representa, ainda custa apenas 20 quadraturas e no máximo 20 multiplicações.
Limites e casos extremos
Esta calculadora suporta apenas expoentes não negativos. Um expoente negativo - como a^(-1) mod m - requer o cálculo do inverso modular de a, que só existe quando a e m são primos e precisa de um algoritmo diferente (o algoritmo euclidiano estendido) inteiramente; não é suportado aqui. Um módulo de 1 sempre produz 0, já que todo número inteiro é divisível por 1. E embora a base possa ser inserida como negativa, ela é normalizada no intervalo [0, m) antes da execução do algoritmo, correspondendo à convenção matemática padrão de que um mod m é sempre não negativo.