[skip-to-content]
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\gcd}{\operatorname{mcd}} \renewcommand{\lcm}{\operatorname{mcm}} \renewcommand{\deg}{\operatorname{gr}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

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. 1 Los resultados de esta sección solo serán necesarios en el Capítulo 7

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.