Sección4.3El método de los cuadrados repetidos
¶Calcular potencias grandes puede tomar mucho tiempo. Así como cualquiera puede calcular 22 o 28, cualquiera sabe como calcular
221000000.
Sin embargo, tales número son tan grandes que no quisiéramos siquiera intentar hacer los cálculos; Más aún, después de cierto punto, el cálculo no sería realizable aunque tuviéramos a nuestra disposición todos los computadores del mundo. Incluso escribir la representación decimal de un número demasiado grande puede no ser práctico. Podría tener miles o incluso millones de dígitos. Sin embargo, si pudiéramos calcular algo como
\begin{equation*}
2^{37398332 } \pmod{ 46389},
\end{equation*}
podríamos fácilmente escribir el resultado pues sería un número entre 0 y 46,388. Si queremos calcular potencias módulo n rápida y eficientemente, deberemos ser astutos.
Lo primero que debemos notar es que cualquier número a se puede escribir como una suma de potencias de 2 distintas; es decir, podemos escribir
\begin{equation*}
a = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_n},
\end{equation*}
con k_1 \lt k_2 \lt \cdots \lt k_n\text{.} Esto es simplemente la representación binaria de a\text{.} Por ejemplo, la representación binaria de 57 es 111001, pues 57 = 2^0 + 2^3 + 2^4 + 2^5\text{.}
La reglas de los exponentes se cumplen en {\mathbb Z}_n\text{;} es decir, si b \equiv a^x \pmod{ n} y c \equiv a^y \pmod{ n}\text{,} entonces bc \equiv a^{x+y} \pmod{ n}\text{.} Podemos calcular a^{2^k} \pmod{ n} en k pasos calculando
\begin{gather*}
a^{2^0} \pmod{ n}\\
a^{2^1} \pmod{ n }\\
\vdots\\
a^{2^k} \pmod{ n}.
\end{gather*}
Cada paso corresponde a elevar al cuadrado el resultado obtenido en el paso anterior, dividir por n\text{,} y dejar el resto.
Ejemplo4.28
Calcularemos 271^{321} \pmod{ 481}\text{.} Note que
\begin{equation*}
321 = 2^0 +2^6 + 2^8;
\end{equation*}
luego, calcular 271^{ 321} \pmod{ 481} es lo mismo que calcular
\begin{equation*}
271^{ 2^0 +2^6 + 2^8 } \equiv 271^{ 2^0 } \cdot 271^{2^6 } \cdot 271^{ 2^8 } \pmod{ 481}.
\end{equation*}
Será suficiente con calcular 271^{ 2^i } \pmod{ 481} con i = 0, 6, 8\text{.} Es muy fácil ver que
\begin{equation*}
271^{ 2^1} = \text{73,441} \equiv 329 \pmod{ 481}.
\end{equation*}
Podemos elevar al cuadrado este resultado, obteniéndo un valor para 271^{ 2^2} \pmod{481}\text{:}
\begin{align*}
271^{ 2^2} & \equiv (271^{ 2^1})^2 \pmod{ 481}\\
& \equiv (329)^2 \pmod{ 481}\\
& \equiv \text{108,241} \pmod{ 481}\\
& \equiv 16 \pmod{ 481}.
\end{align*}
Estamos usando el hecho que (a^{2^n})^2 \equiv a^{2 \cdot 2^n} \equiv a^{ 2^{n+1} } \pmod{ n}\text{.} Continuando, podemos calcular
\begin{equation*}
271^{ 2^6 } \equiv 419 \pmod{ 481}
\end{equation*}
y
\begin{equation*}
271^{ 2^8 } \equiv 16 \pmod{ 481}.
\end{equation*}
Por lo tanto,
\begin{align*}
271^{ 321} & \equiv 271^{ 2^0 +2^6 + 2^8 } \pmod{ 481}\\
& \equiv 271^{ 2^0 } \cdot 271^{ 2^6 } \cdot 271^{ 2^8 } \pmod{ 481}\\
& \equiv 271 \cdot 419 \cdot 16 \pmod{ 481}\\
& \equiv \text{1,816,784} \pmod{ 481}\\
& \equiv 47 \pmod{ 481}.
\end{align*}
El método de los cuadrado repretido resultará ser una herramienta muy útil cuando exploremos la criptografía RSA en el Capítulo 7. Para codificar y decodificar mensaje de forma razonable, será necesario poder calcular grandes potencia de enteros mód n de forma rápida.
