Exponenciación modular

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 símbolos, esto es, dada la base b, el exponente e, y el módulo m, la exponenciación modular c es: c \equiv b^e \pmod{m}

Por ejemplo, dado b = 5, e = 3, y m = 13, la solución, c = 8, es el resto de dividir 5^3 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 modulo m usando el algoritmo extendido de Euclides. Esto es:

c \equiv b^{e} \equiv d^{\left|e\right|} \pmod{m} donde e < 0 y b \cdot d \equiv 1 \pmod{m}

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 — se cree que es difícil. Este comportamiento de función unidireccional hace a la exponenciación modular un candidato para su uso en algoritmos criptográficos.

Referencias[editar]

Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd edición). Wiley. ISBN 978-0-471-11709-4. 

Enlaces externos[editar]