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), b^e, 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: $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 módulo 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 — 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, dados b = 4, e = 13 y m = 497, para abordar la operación de :$c\equiv 4^{13}\ {\pmod {497}}.$, se puede calcular en primer lugar de b^e' y luego su módulo m.
Se puede apelar a la calculadora para obtener 67 108 864 como resultado de 4¹³:
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 b^e - es decir, para 4¹³-.
En aplicaciones habituales de la criptografía, b puede presentar al menos 256 dígitos binarios (y 77 decimales). Consideremos b = 5×10⁷⁶ y e = 17,, valores todos perfectamente razonables. En este caso, con b de 77 dígitos y e de 17, son 1304 los de b^e.
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 b^e 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

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:

$b^{\prime }\equiv b\ {\pmod {m}}\ {\rm {y}}\ c^{\prime }\equiv c\ {\pmod {m}}$

$b^{\prime }c\ {\pmod {m}}\equiv bc\ {\pmod {m}}$

$bc^{\prime }\ {\pmod {m}}\equiv bc\ {\pmod {m}}$

El algoritmo es el siguiente:

1. Siendo $c^{\prime }$ = 1, $e^{\prime }$ = 0.
2. Incrementar e' en 1.
3. Calcular $c^{\prime }\equiv (b\cdot c^{\prime })\ {\pmod {m}}$.
4. Si e' < e, pasar al paso 2. Si no, $c^{\prime }$ contiene la solución correcta de $c\equiv b^{e}{\pmod {m}}$.

Cabe señalar que en cada ciclo por el paso 3, la ecuación $c\equiv b^{e'}\ {\pmod {m}}$ 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

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:

$e=\sum _{i=0}^{n-1}a_{i}2^{i}.$

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

El valor b^e puede escribirse, entonces como:

$b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}.$

La solución c es, por ende:

$c\equiv \prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}\ {\pmod {m}}.$

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 $b^{2^{i}}\ {\pmod {m}}$, donde i es el número de iteraciones del bucle.

La primera línea de código efectúa simplemente la multiplicación $\prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}\ {\pmod {m}}$. Si a_i vale cero, el código no se ejecuta, lo que equivale a multiplicar el total por uno. Si, en cambio, a_i vale uno, el resultado es simplemente multiplicar por la variable base (que contiene el valor $b^{2^{i}}\ {\pmod {m}}$ 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

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

• Wikilibros alberga un libro o manual sobre Implementaciones de la exponenciación modular.
• Fast Modular Exponentiation Java Applet - University of Minnesota Math Department
• Algorithm for modular exponentiation en PlanetMath.

• Datos: Q1228841