Calculadora de Exponenciação Modular

Calculadora de Exponenciação Modular

A Calculadora de Exponenciação Modular calcula \(a^b \bmod n\) — elevando uma base \(a\) a um expoente \(b\) e obtendo o resto da divisão pelo módulo \(n\). Ela utiliza o algoritmo de exponenciação binária (também conhecido como potência rápida ou exponenciação por quadrados), que reduz a operação de \(O(b)\) multiplicações para apenas \(O(\log b)\). Este é o mesmo algoritmo usado em implementações criptográficas do mundo real como RSA, Diffie-Hellman e ElGamal.

Aplicações da Exponenciação Modular

Como Funciona o Algoritmo de Exponenciação Binária

A ideia principal é que podemos decompor qualquer expoente em uma soma de potências de 2 usando sua representação binária. Por exemplo, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), então \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

O algoritmo processa os dígitos binários do expoente da esquerda para a direita:

Pseudocódigo

função modpow(base, exp, mod):
    resultado = 1
    base = base mod mod
    enquanto exp > 0:
        se exp é ímpar:        // bit é 1
            resultado = (resultado × base) mod mod
        exp = exp >> 1        // deslocamento à direita (divide por 2)
        base = (base × base) mod mod
    retorna resultado

Fórmulas Chave

Como Usar a Calculadora de Exponenciação Modular

1. Insira a base (a): Este é o número que você deseja elevar a uma potência. Pode ser positivo ou negativo. Por exemplo, insira 7 para calcular 7^256 mod 13.
2. Insira o expoente (b): Deve ser um número inteiro não negativo. Ele representa a potência. Para aplicações criptográficas, este valor pode ser muito grande (a calculadora suporta até 10^18).
3. Insira o módulo (n): Deve ser um número inteiro positivo. É o número pelo qual você divide para obter o resto. No RSA, este é tipicamente o produto de dois grandes números primos.
4. Clique em Calcular: A calculadora computa a^b mod n usando exponenciação binária e mostra o resultado instantaneamente.
5. Assista à animação: Pressione Reproduzir para assistir à execução do algoritmo de exponenciação binária passo a passo. Cada bit do expoente é processado em sequência, mostrando se o algoritmo eleva ao quadrado, ou eleva ao quadrado e multiplica.
6. Revise o traço: A tabela passo a passo mostra cada cálculo intermediário, e a comparação de eficiência mostra o quanto a exponenciação binária é mais rápida do que a multiplicação repetida ingênua.

Por que a Exponenciação Binária é Rápida

Considere o cálculo de \(2^{1000} \bmod 13\). A abordagem ingênua exigiria 999 multiplicações. A exponenciação binária converte 1000 para binário (1111101000), que possui 10 bits. Ela precisa de no máximo 9 quadrados mais algumas multiplicações para cada bit '1' — cerca de 15 operações no total. Isso representa cerca de 98,5% menos operações. Para expoentes em escala criptográfica com centenas de dígitos, a diferença é astronômica: o método binário leva milhares de operações onde o método ingênuo exigiria mais operações do que átomos no universo.

FAQ