Calculadora de Aritmética Modular
Calcule a mod n, adição modular, multiplicação e potência (aᵇ mod n) — aritmética de relógio na hora.
1.253 visualizações
Como Funciona a Aritmética Modular
a mod n faz uma pergunta simples: qual é o resto que sobra ao dividir a por n? Formalmente, a mod n = a − n × piso(a ÷ n), e por convenção matemática o resultado está sempre entre 0 e n−1. A forma mais intuitiva de visualizar isso é um mostrador de relógio: as horas não contam para sempre, elas dão a volta em 12 (ou 24). Digamos que sejam 15h00 e você precise saber que horas serão 10 horas depois — você não obtém "25h00", você calcula (15 + 10) mod 24 = 1, ou seja, 01h00 do dia seguinte. Todo valor volta a percorrer o mesmo conjunto de "posições", e é exatamente essa volta que n representa em a mod n.
Esta calculadora estende a mesma ideia a três operações relacionadas: adição modular (a + b) mod n, multiplicação modular (a × b) mod n, e exponenciação modular aᵇ mod n. Esta última parece inofensiva, mas é a operação mais importante da criptografia moderna. Calculá-la da forma ingênua — primeiro elevar a à potência b, depois tirar o resto — produziria números com milhões de dígitos para tamanhos de chave reais, muito antes mesmo de a etapa de módulo ser executada. Em vez disso, a ferramenta usa o algoritmo de elevação ao quadrado e multiplicação (square-and-multiply): eleva repetidamente a base ao quadrado e reduz módulo n a cada passo, de modo que os números intermediários nunca crescem além do tamanho do próprio n, por maior que seja b. É isso que torna possíveis resultados exatos mesmo para expoentes com centenas de dígitos.
O Que Você Deve Saber
- Criptografia: a troca de chaves RSA e Diffie-Hellman funcionam com exponenciação modular usando primos muito grandes — criptografar uma mensagem é, no fundo, calcular aᵇ mod n, em que a, b e n têm cada um centenas de dígitos.
- Funções hash: a maioria dos esquemas de hash reduz uma entrada de tamanho arbitrário a um "compartimento" de tamanho fixo usando uma operação de módulo, e é por isso que o mod aparece em tabelas hash, somas de verificação e lógica de balanceamento de carga.
- Calendários e relógios: cálculos de dia da semana, conversões entre 12/24 horas e ciclos de calendário são todos aritmética modular disfarçada — o apelido "aritmética de relógio" vem diretamente daí.
- As convenções de sinal diferem: a matemática sempre define a mod n como não negativo, mas muitas linguagens de programação (C, JavaScript, Java) retornam em vez disso um resto com o mesmo sinal de a, o que pode atrapalhar traduções diretas de fórmulas para código.
Perguntas Frequentes
Quanto é −7 mod 3?
Esta ferramenta segue a convenção matemática segundo a qual o resultado é sempre não negativo: −7 mod 3 = 2 (já que −7 = −3×3 + 2). Algumas linguagens de programação retornam −1 em vez disso, porque definem o resto para carregar o mesmo sinal do dividendo em vez de ser sempre positivo.
Onde aᵇ mod n é usado na vida real?
É a operação central da troca de chaves RSA e Diffie-Hellman: criptografar uma mensagem ou combinar um segredo compartilhado significa essencialmente calcular uma enorme potência modular, geralmente com números de 2048 bits ou mais.
Por que o exemplo do relógio usa mod 24 e não mod 12?
Os dois funcionam — um relógio de 12 horas dá a volta em mod 12, um relógio de 24 horas em mod 24. O módulo n é simplesmente o tamanho do ciclo que interessa a você; escolha a convenção de relógio que corresponda à forma como está contando o tempo.
a mod n é o mesmo que divisão inteira?
São duas metades da mesma divisão. a ÷ n (divisão inteira) dá o quociente — quantas vezes n cabe inteiramente em a — enquanto a mod n dá o que sobra. Juntos, quociente × n + resto sempre reconstrói a.
Por que elevação ao quadrado e multiplicação é mais rápido do que calcular aᵇ diretamente?
A exponenciação direta multiplica a por si mesmo b−1 vezes, e o valor intermediário explode em tamanho muito antes que você consiga reduzi-lo módulo n. A elevação ao quadrado e multiplicação, em vez disso, reduz após cada etapa de elevação ao quadrado, de modo que os números envolvidos nunca crescem além do tamanho aproximado de n — transformando uma operação que levaria mais tempo que a idade do universo para tamanhos de chave criptográficos em uma que termina em milissegundos.
Ferramentas Semelhantes
Reportar um Problema
Calculadora de Aritmética Modular
Comentários
Ainda não há comentários — seja o primeiro a escrever um!