Calculadora de exponenciação modular

A exponenciação modular calcula o resto de uma base inteira elevada a um expoente inteiro não negativo e dividida por um módulo positivo. A expressão a^b mod m busca o único resto de 0 a m - 1 que é congruente a a^b. O cálculo direto pode se tornar inviável muito rapidamente, pois as potências atingem tamanhos enormes, mesmo quando o resto final é pequeno. Esta calculadora evita construir esse inteiro intermediário gigantesco. O método eficiente é chamado de exponenciação binária, quadrados sucessivos ou quadrados e multiplicações. O expoente é escrito em binário e seus bits são processados. Primeiro, a base é reduzida módulo m. Em cada etapa, o fator atual é elevado ao quadrado módulo m. Quando o bit correspondente do expoente é um, esse fator é multiplicado pelo resultado, com nova redução imediata módulo m. Como todos os valores intermediários são reduzidos, eles permanecem menores que o quadrado do módulo. Esse algoritmo exige apenas um número de etapas proporcional ao logaritmo do expoente. Portanto, calcular uma potência de expoente um bilhão requer cerca de trinta etapas de quadrados, em vez de um bilhão de multiplicações repetidas. A contagem exibida separa as elevações ao quadrado das multiplicações selecionadas associadas aos bits de valor um do expoente. Um expoente zero retorna corretamente 1 mod m. A aritmética modular trata números com o mesmo resto como equivalentes. Por exemplo, 17 e 5 são congruentes módulo 12 porque ambos deixam resto 5. Uma base negativa também é aceita: ela é normalizada primeiro para um resíduo não negativo. Nesta calculadora, o expoente deve ser não negativo. Expoentes modulares negativos exigem um inverso multiplicativo modular, que só existe quando a base e o módulo são coprimos. Potências modulares são fundamentais na teoria dos números e na criptografia moderna. A criptografia e as assinaturas RSA elevam mensagens a grandes potências módulo um número composto. A troca de chaves Diffie-Hellman e muitos sistemas de logaritmo discreto usam potências módulo um primo. A mesma operação também é usada em testes de primalidade, geradores pseudoaleatórios, somas de verificação, padrões cíclicos e problemas de programação competitiva. Os três campos são processados como inteiros exatos de tamanho arbitrário, e não como números de ponto flutuante. Assim, valores além do limite usual de inteiros seguros do JavaScript mantêm todos os dígitos. O módulo deve ser maior que um e não se devem inserir vírgulas nem pontos decimais. Para conferir manualmente, reduza primeiro a base e verifique expoentes pequenos por multiplicações sucessivas, tomando o resto a cada etapa.