Exponenciación modular

La exponenciación modular es un tipo de exponenciación realizada sobre un módulo. Es particularmente útil en ciencias de la computación, especialmente en el campo de la criptografía.

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. En notación matemática, dada la base b, el exponente e, y el módulo m, la exponenciación modular c se escribe:

Por ejemplo, dado b = 5, e = 3, y m = 13, la solución, c = 8, es el resto de dividir por 13.

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. Esto es:

donde y

Problemas de exponenciación modular similares al descrito arriba son considerados fáciles de resolver, incluso cuando los números que se manejan son enormes.
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.

Método directo

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, dadosb = 4, e = 13 y m = 497, para abordar la operación de :, se puede calcular en primer lugar de be' y luego su módulo m.
Se puede apelar a la calculadora para obtener 67 108 864 como resultado de 413:
y luego el módulo 497 de este valor para determinar que c es 445.

En este caso, con un valor de apenas un dígito para b y solo dos para e, son 8 los de be - es decir, para 413-.
En aplicaciones habituales de la criptografía, b puede presentar al menos 256 dígitos binarios (y 77 decimales). Consideremos b = 5×1076 y e = 17,, valores todos perfectamente razonables. En este caso, con b de 77 dígitos y e de 2, son 1304 los de be.
Dada la capacidad de cómputo actual este recorrido es viable pero ralentiza tanto la operatoria que lo conveniente es apelar una modalidad que ofrezca mejores condiciones de seguridad para llegar al valor de be aunque aumenten los b y e (el cálculo de la exponenciación como serie de multiplicaciones requiere un tiempo acorde a O(e)).