Exponenciación modular

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la 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 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[editar]

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)).

Método con menor requerimiento de memoria[editar]

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:

  1. Siendo c = 1, e' = 0.
  2. Incrementar e' en 1.
  3. Calcular .
  4. Si e' < e, pasar al paso 2. Si no, c contiene la solución correcta de .

Cabe señalar que en cada ciclo por el paso 3, la ecuación resulta verdadera. Cuando se ejecuta e veces el paso 3, c deviene la respuesta buscada.

Repasemos el ejemplo b = 4, e = 13, y m = 497. El algoritmo cicla 13 veces por el paso 3:

  • e' = 1. c = (4 x 1) (mod 497) = 4 (mod 497) = 4.
  • e' = 2. c = (4 x 4) (mod 497) = 16 (mod 497) = 16.
  • e' = 3. c = (4 x 16) (mod 497) = 64 (mod 497) = 64.
  • e' = 4. c = (4 x 64) (mod 497) = 256 (mod 497) = 256.
  • e' = 5. c = (4 x 256) (mod 497) = 1024 (mod 497) = 30.
  • e' = 6. c = (4 x 30) (mod 497) = 120 (mod 497) = 120.
  • e' = 7. c = (4 x 120) (mod 497) = 480 (mod 497) = 480.
  • e' = 8. c = (4 x 480) (mod 497) = 1920 (mod 497) = 429.
  • e' = 9. c = (4 x 429) (mod 497) = 1716 (mod 497) = 225.
  • e' = 10. c = (4 x 225) (mod 497) = 900 (mod 497) = 403.
  • e' = 11. c = (4 x 403) (mod 497) = 1612 (mod 497) = 121.
  • e' = 12. c = (4 x 121) (mod 497) = 484 (mod 497) = 484.
  • e' = 13. c = (4 x 484) (mod 497) = 1936 (mod 497) = 445.

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). Sin embargo, como el los números en juego en este cálculo son menores que aquellos con los que se opera en el primer algoritmo, también lo es el factor constante involucrado.

El método más eficaz[editar]

Un tercer método, combinación del precedente con un principio más general denominado exponenciación binaria (o exponenciación rápida o por cuadrados).

Ante todo, se debe convertir el exponente e a notación binaria, es decir, anotado como:

En esta notación, la longitud de e es de n bits. ai puede tomar el valor 0 o 1 para todo i tal que 0 ≤ i < n - 1. Por definición, an - 1 = 1.

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. El siguiente ejemplo se elabora en C#. La clase Bignum representa a cualquier número positivo grande. Las variables de entrada son base para la base (b), exp para el exponente (e) y m para el módulo.

Bignum modpow(Bignum base, Bignum exp, Bignum m) {

   Bignum result = 1;

   while (exp > 0) {
      if ((exp & 1) > 0) result = (result * base) % m;
      exp >>= 1;
      base = (base * base) % m;
   }

   return result;

 }

Este código, adaptación del que aparece en la página 244 de Applied Cryptography de Bruce Schneier, ISBN 0471117099, apela a un bucle simple while para ejecutar todo el trabajo de cálculo necesario para la exponenciación modular.

En la primera entrada al bucle, la variable base equivale a b. Sin embargo, la repetida elevación al cuadrado 13 veces repetida asegura que la variable base resulte , donde i es el número de iteraciones del bucle.

La primera línea de código efectúa simplemente la multiplicación . 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 de la base original).

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:

  • En la primera entrada al bucle, los valores de las variables son: base = 4, exp = 1101 (binaire) y result = 1. Como el bit más a la derecha de exp es 1, result es reemplazado por (1 × 4) % 497, es decir 4. exp deviene 110 (binario) y base elevado al cuadrado por el valor (4 × 4) % 497, es decir, 16.
  • En la segunda ejecución del bucle, el bit más a la derecha de exp es 0, result no se modifica. exp se trunca a la derecha y deviene 11 (binario) y base se eleva al cuadrado y pasa a valer (16 × 16) % 497, es decir, 256.
  • En la tercera ejecución del bucle, el bit más a la derecha de exp es 1, result es remplazado por (4 × 256) % 497, es decir, 30. exp se trunca a la derecha y deviene 1 y base es elevado al cuadrado y pasa a valer (256 × 256) % 497, es decir 429.
  • En la cuarta ejecución del bucle, el bit más a la derecha de exp es 1, result es remplazado por (30 × 429) % 497, es decir, 445. exp se trunca a la derecha y deviene 0 y base es elevado al cuadrado y pasa a valer (429 × 429) % 497, es decir 151. (Esta última multiplicación base * base es irrelevante porque el resultado buscado, aquí 445, ya es conocido.)

El bucle termina, entonces, cuando exp es igual a cero y el resultado445, lo que concuerda con los dos algoritmos precedentes.

Los tiempos de ejecución de este algoritmo resultan acorde a O(log e). Incluso cuando opera con grandes valores de e, es rápido en comparación con cada uno de los anteriores.

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]