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

Operações matemáticas avançadas:

• Calculadora de Antilog
• Calculadora de Função Beta
• Calculadora de Coeficiente Binomial
• Calculadora de distribuição binomial
• Calculadora de Lógica Binária
• Calculadora do Teorema Central do Limite
• Calculadora de Combinação Em Destaque
• Calculadora de Função de Erro Complementar
• Calculadora de Números Complexos Em Destaque
• Calculadora de Entropia
• Calculadora da função de erro
• Calculadora de decaimento exponencial
• Calculadora de Crescimento Exponencial de Alta Precisão
• Calculadora de Integral Exponencial
• Calculadora de Expoentes (Alta Precisão) Em Destaque
• Calculadora de Fatorial
• Calculadora de Função Gama
• Calculadora de Proporção Áurea
• Calculadora de Meia-Vida
• Calculadora de Taxa de Crescimento Percentual Em Destaque
• Calculadora de Permutação
• Calculadora de Distribuição de Poisson
• Calculadora de Raízes de Polinômios
• Calculadora de Probabilidade
• Calculadora de Distribuição de Probabilidade
• Calculadora de Proporção Em Destaque
• Calculadora de Fórmula Quadrática
• Calculadora Científica
• Calculadora de notação científica
• Calculadora de Algarismos Significativos Novo
• Calculadora de Soma de Cubos
• Calculadora de soma de inteiros positivos
• Calculadora de Soma dos Quadrados
• Gerador de Tabela Verdade
• Calculadora de Teoria dos Conjuntos
• Gerador de Diagrama de Venn (3 Conjuntos)
• Calculadora do Teorema Chinês do Resto
• Calculadora da Função Totiente de Euler
• Calculadora do Algoritmo Euclidiano Estendido
• Calculadora do Inverso Multiplicativo Modular
• Calculadora de Frações Contínuas
• Calculadora de Caminho Mais Curto de Dijkstra
• Calculadora de Árvore Geradora Mínima
• Validador de Sequência de Graus de Grafo
• Calculadora de Desarranjo (Subfatorial)
• Calculadora de Números de Stirling
• Calculadora do Princípio da Casa dos Pombos
• Calculadora de Estado Estacionário da Cadeia de Markov
• Calculadora de Arredondamento Novo
• Calculadora de Distribuição Binomial Negativa Novo
• Calculadora de Permutações com Repetição Novo
• Calculadora de Exponenciação Modular Novo
• Calculadora de Raiz Primitiva
• Simplificador de Álgebra Booleana Novo
• Solucionador de Mapa de Karnaugh (K-Map) Novo
• Calculadora de Coloração de Grafos Novo
• Calculadora de Ordenação Topológica Novo
• Calculadora de Matriz de Adjacência Novo
• Calculadora de Inclusão-Exclusão Novo
• Solucionador de Programação Linear Novo
• Solucionador do Caixeiro Viajante (TSP) Novo
• Verificador de Caminho Hamiltoniano Novo
• Verificador de Grafo Planar Novo
• Calculadora de Fluxo em Rede (Fluxo Máximo) Novo
• Solucionador do Problema do Casamento Estável Novo
• Calculadora de Ordem em Teoria dos Grupos Novo
• Calculadora de Anéis e Corpos Novo