Exponenciação modular

A calculadora realiza a exponenciação modular de grandes números.

Esta calculadora executa a exponenciação de um grande número inteiro sobre um módulo. Um algoritmo rápido é utilizado, descrito logo abaixo da calculadora.

PLANETCALC, Exponenciação modular

Exponenciação modular

Resultado
 

Algoritmos de exponenciação rápida

A implementação mais simples de exponenciação requer N-1 operações de multiplicação, onde N é uma base expoente. Apesar de todo o poder dos computadores modernos, esse método não é adequado para nós, uma vez que usaremos números para o expoente, ainda maiores do que os números inteiros de 64 bits padrão. Por exemplo, número Primo de Mersenne: 618970019642690137449562111 usado como valor expoente padrão possui 89 bits (veja Comprimento de bit).
Para lidar com esses expoentes com segurança, devemos usar algoritmos de exponenciação rápida.

Na calculadora de Expansão de potência polinomial, nós já utilizamos o algoritmo de exponenciação rápida baseado em uma árvore de potência. Ele permite minimizar extremamente o número de operações de multiplicação. Entretanto, não podemos usá-lo com expoentes enormes, visto que a árvore de exponenciação consome muita memória.
Esta calculadora usa a implementação da biblioteca bigInt do algoritmo de exponenciação modular rápido baseado no método binário. O mesmo artigo descreve uma versão desse algoritmo, que processa os dígitos binários do mais significativo para o menos significativo (da esquerda para a direita). Isso é inconveniente para o nosso caso, visto que usamos números inteiros grandes de comprimento variável e não conhecemos de antemão a posição de bit mais significativa.

Algoritmo de exponenciação binária (da direita para a esquerda).

Dessa forma, o algoritmo que utilizamos lida com os bits expoentes do menos significativo para o mais significativo (da direita para a esquerda).
O pseudocódigo do algoritmo:

a //base
e //expoente
m //módulo
 //exponenciação modular
r ⟵ 1      
enquanto (e!=0) {
            se (e mod 2 = 1) r ⟵ r * a mod m;
            e ⟵ e / 2;
            a = a*a mod m;
        }
resultado ⟵ r
URL copiado para a área de transferência
PLANETCALC, Exponenciação modular

Comentários