AATA El método de los cuadrados repetidos

Seção 4.3 El método de los cuadrados repetidos

Calcular potencias grandes puede tomar mucho tiempo. Así como cualquiera puede calcular

2^{2}

2^{8},

cualquiera sabe como calcular

2^{2^{1000000}} .

🔗

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

2^{37398332} (\mod 46389),

🔗

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

a = 2^{k_{1}} + 2^{k_{2}} + \dots + 2^{k_{n}},

🔗

con

k_{1} < k_{2} < \dots < k_{n} .

Esto es simplemente la representación binaria de

a .

Por ejemplo, la representación binaria de 57 es 111001, pues

57 = 2^{0} + 2^{3} + 2^{4} + 2^{5} .

🔗

La reglas de los exponentes se cumplen en

Z_{n};

es decir, si

b \equiv a^{x} (\mod n)

c \equiv a^{y} (\mod n),

entonces

b c \equiv a^{x + y} (\mod n) .

Podemos calcular

a^{2^{k}} (\mod n)

k

pasos calculando

\begin{matrix} a^{2^{0}} (\mod n) \\ a^{2^{1}} (\mod n) \\ ⋮ \\ a^{2^{k}} (\mod n) . \end{matrix}

🔗

Cada paso corresponde a elevar al cuadrado el resultado obtenido en el paso anterior, dividir por

n,

y dejar el resto.

🔗

Exemplo 4.3.1.

Calcularemos $271^{321} (\mod 481) .$ Note que

321 = 2^{0} + 2^{6} + 2^{8};

luego, calcular $271^{321} (\mod 481)$ es lo mismo que calcular

271^{2^{0} + 2^{6} + 2^{8}} \equiv 271^{2^{0}} \cdot 271^{2^{6}} \cdot 271^{2^{8}} (\mod 481) .

Será suficiente con calcular $271^{2^{i}} (\mod 481)$ con $i = 0, 6, 8 .$ Es muy fácil ver que

271^{2^{1}} = 73,441 \equiv 329 (\mod 481) .

Podemos elevar al cuadrado este resultado, obteniéndo un valor para $271^{2^{2}} (\mod 481) :$

\begin{aligned} 271^{2^{2}} & \equiv (271^{2^{1}})^{2} (\mod 481) \\ \equiv (329)^{2} (\mod 481) \\ \equiv 108,241 (\mod 481) \\ \equiv 16 (\mod 481) . \end{aligned}

Estamos usando el hecho que $(a^{2^{n}})^{2} \equiv a^{2 \cdot 2^{n}} \equiv a^{2^{n + 1}} (\mod n) .$ Continuando, podemos calcular

271^{2^{6}} \equiv 419 (\mod 481)

271^{2^{8}} \equiv 16 (\mod 481) .

Por lo tanto,

\begin{aligned} 271^{321} & \equiv 271^{2^{0} + 2^{6} + 2^{8}} (\mod 481) \\ \equiv 271^{2^{0}} \cdot 271^{2^{6}} \cdot 271^{2^{8}} (\mod 481) \\ \equiv 271 \cdot 419 \cdot 16 (\mod 481) \\ \equiv 1,816,784 (\mod 481) \\ \equiv 47 (\mod 481) . \end{aligned}

🔗

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