Salta al contenido principal
Logo image

Sección 4.3 El 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} }\text{.} \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}\text{,} \end{equation*}
podríamos fácilmente escribir el resultado pues sería un número entre \(0\) y \(46388\text{.}\) Si queremos calcular potencias módulo \(n\) rápida y eficientemente, deberemos ser astutos. 1 
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}\text{,} \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}\text{.} \end{gather*}
Cada paso corresponde a elevar al cuadrado el resultado obtenido en el paso anterior, dividir por \(n\text{,}\) y dejar el resto.
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}\text{.} \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}\text{.} \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}\text{.} \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}\text{.} \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}\text{.} \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 potencias de enteros mód \(n\) de forma rápida.

Sage.

La implementación de los grupos cíclicos en Sage es algo débil — pero igual podemos hacer uso provechoso de Sage y quizás esta situación cambie pronto.
Los resultados de esta sección solo serán necesarios en el Capítulo 7