Sección4.3El método de los cuadrados repetidos
¶Calcular potencias grandes puede tomar mucho tiempo. Así como cualquiera puede calcular \(2^2\) o \(2^8\text{,}\) cualquiera sabe como calcular
\begin{equation*}
2^{2^{1000000} }.
\end{equation*}
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.
