Una «exponenciación modular» calcula el residuo cuando un número entero positivo b (la base) se eleva a la e-ésima potencia (el exponente), be, y es dividido por el entero positivo m, llamado módulo.
Por ejemplo, dado b = 5, e = 3, y m = 13, la solución, c = 8, es el resto de dividir
Si b, e, y m no son negativos, y b < m, entonces una única solución c existe con la propiedad 0 ≤ c < m. La exponenciación modular se puede realizar con exponente negativo e encontrando el inverso multiplicativo modular d de b módulo m usando el algoritmo extendido de Euclides.
Por otro lado, el cálculo del logaritmo discreto — es decir, la tarea de encontrar el exponente e si es dado un b, c, y m — es un problema de los considerados difíciles.
Este comportamiento de función unidireccional hace a la exponenciación modular un candidato para su uso en algoritmos criptográficos.
Es conveniente encontrar un método más allanado para calcular la exponenciación modular dado el peso de cómputo del directo.
Por ejemplo, para obtener c, dados b = 4, e = 13 y m = 497, para abordar la operación de :
En aplicaciones habituales de la criptografía, b puede presentar al menos 256 dígitos binarios (y 77 decimales).
Un método alternativo para calcular la exponenciación modular con menor requerimiento de memoria, resulta de apelar a un algoritmo más rápido: Tal algoritmo apela a que, dados dos enteros b y c, las relaciones preliminares implican que: El algoritmo es el siguiente: Cabe señalar que en cada ciclo por el paso 3, la ecuación
Cuando se ejecuta e veces el paso 3, c deviene la respuesta buscada.
El algoritmo cicla 13 veces por el paso 3: La respuesta final para c es, en consecuencia, 445, como en el primer método.
Como el primer método, éste requiere un tiempo de cálculo según O(e).
El valor be puede escribirse, entonces como: La solución c es, por ende: Tal algoritmo se puede implementar fácilmente en un lenguaje de programación adecuado.
En la primera entrada al bucle, la variable base equivale a b.
Si ai vale cero, el código no se ejecuta, lo que equivale a multiplicar el total por uno.
Si, en cambio, ai vale uno, el resultado es simplemente multiplicar por la variable base (que contiene el valor
Para finalizar, controlemos el ejemplo correspondiente a b = 4, e = 13 y m = 497.
En binario, e es 1101 y como su longitud es de 4 bits, el bucle se ejecuta cuatro veces: El bucle termina, entonces, cuando exp es igual a cero y el resultado445, lo que concuerda con los dos algoritmos precedentes.