Exponenciación modular

Esta calculadora realiza la exponenciación de un número entero grande sobre un módulo. Se utiliza un algoritmo rápido, descrito justo debajo de la calculadora.

Exponenciación modular

Base

Exponente

Módulo

Calcular

Resultado

 

 Enlace  Guardar  Widget

Algoritmos de exponenciación rápida

La implementación más simple de la exponenciación requiere N-1 operaciones de multiplicación, donde N es una base de exponente. A pesar de toda la potencia de los ordenadores modernos, este método no nos conviene ya que utilizaremos números para el exponente, incluso mayores que los enteros estándar de 64 bits. Por ejemplo, el número primo de Mersenne: 618970019642690137449562111 utilizado como valor del exponente por defecto tiene 89 bits (ver longitud de bits).
Para manejar con seguridad tales exponentes, debemos utilizar algoritmos de exponenciación rápida.

En la calculadora de expansión de potencia de polinomios, ya utilizamos un algoritmo de exponenciación rápida basado en un árbol de potencias. Permite minimizar el número de operaciones de multiplicación de forma extrema. Sin embargo, no podemos utilizarlo con exponentes enormes ya que el árbol de exponenciación consume demasiada memoria.
Esta calculadora utiliza la implementación de la biblioteca bigInt del algoritmo de exponenciación modular rápida basado en el método binario. El mismo artículo describe una versión de este algoritmo, que procesa los dígitos binarios desde el más significativo al menos significativo (de izquierda a derecha). Esto es inconveniente para nuestro caso, ya que utilizamos números enteros grandes de longitud variable y no conocemos la posición del bit más significativo de antemano.

Algoritmo de exponenciación binaria (de derecha a izquierda).

Entonces el algoritmo que utilizamos maneja los bits del exponente desde el menos significativo al más significativo (de derecha a izquierda).
El pseudocódigo del algoritmo:

a //base
e //exponente
m //módulo
 //exponenciación modular 
r ⟵ 1      
while (e!=0) {
            if (e mod 2 = 1) r ⟵ r * a mod m;
            e ⟵ e / 2;
            a = a*a mod m;
        }
salida ⟵ r