Exponenciación modular a mano ( $a^b\bmod c$ )

Question

¿Cómo puedo calcular eficientemente $a^b\bmod c$ :

• En $b$ es enorme, por ejemplo $5^{844325}\bmod 21$ ?
• En $b$ es inferior a $c$ pero aún así sería mucho trabajo multiplicar $a$ por sí mismo $b$ veces, por ejemplo $5^{69}\bmod 101$ ?
• En $(a,c)\ne1$ por ejemplo $6^{103}\bmod 14$ ?

¿Existen otros trucos para evaluar exponentes en aritmética modular?

---

Esto se pide en un esfuerzo por reducir los duplicados, véase aquí y aquí .

Answer 1

Wikipágina sobre aritmética modular no está mal.

• En $b$ es enorme, y $a$ y $c$ son coprimos, Teorema de Euler se aplica: $$a^b \equiv a^{b \, \bmod \, \phi(c)} \, \bmod c$$ Para el ejemplo que nos ocupa, $\phi(21) = \phi(3) \times \phi(7) = 2 \times 6 = 12$ . $$\Rightarrow 844325 \bmod 12 = 5,\ \text{so}\ 5^5 = 5 \times 25^2 \equiv 5 \times 4^2 = 80 \equiv 17 \mod 21$$ .

• En $a$ y $c$ son coprimos, pero $0<b<\phi(c)$ La cuadratura repetida (o el uso de otras composiciones de potencias) es la forma más rápida de hacerlo (manualmente): $$\begin{eqnarray} 5^4 \equiv 5 \times 5^3 \equiv 5 \times 24 \equiv 19 &\pmod{101}\\ 19^4 \equiv (19^2)^2 \equiv 58^2 \equiv (-43)^2 \equiv 1849 \equiv 31 &\pmod{101} \\ 31^4 \equiv (31^2)^2 \equiv (961)^2 \equiv 52^2 \equiv 2704 \equiv 78 &\pmod{101} \\ 5^{69} \equiv 5 \times 5^4 \times ((5^4)^4)^4 \equiv 5 \times 19 \times 78 \equiv 5 \times 19 \times (-23)\\ \equiv 19 \times (-14) \equiv -266 \equiv 37 & \pmod{101} \end{eqnarray}$$

• En $a$ y $c$ no son coprimos, sea $g = \gcd(a,c)$ . Sea $a = g \times d$ y $c = g \times f$ entonces, suponiendo $b > 1$ : $$a^b \bmod c = g^b \times d^b \bmod (g \times f) = ( g \times (g^{b-1} d^b \bmod f) ) \bmod c$$ En el ejemplo dado, $\gcd(6,14) = 2$ . Así que $2^{102} \times 3^{103} \mod 7$ utilizando el teorema de Euler, con $\phi(7) = 6$ y $102 \equiv 0 \mod 6$ , $2^{102} \times 3^{103} \equiv 3 \mod 7$ Así que $6^{103} \equiv (2 \times 3) \equiv 6 \mod 14$ .

Answer 2

Probemos $5^{844325} \bmod 21$ : $$\begin{align} 5^0 & & & \equiv 1 \\ 5^1 & & &\equiv 5 \\ 5^2 & \equiv 25 & & \equiv 4 \\ 5^3 & \equiv 4\cdot 5 & & \equiv 20 \\ 5^4 & \equiv 20\cdot 5 & & \equiv 16 \\ 5^5 & \equiv 16\cdot 5 & & \equiv 17 \\ 5^6 & \equiv 17\cdot 5 & & \equiv 1 \end{align}$$ Así que multiplicando por $5$ seis veces es lo mismo que multiplicar por $1$ . Queremos multiplicar por $5$ un gran número de veces: $844325$ . ¿Cuántas veces multiplicamos por $5$ ¿Seis veces? El número de veces $6$ entra en $844325$ es $140720$ con un remanente de $5$ . Ese resto es lo que importa. Multiplica por $5^6$ exactamente $140720$ veces y eso es lo mismo que multiplicar por $1$ tantas veces. Luego multiplique por $5$ sólo $5$ más veces, y obtener $17$ .

Así que $5^{844325} \equiv 17 \bmod 21$ .

Answer 3

He aquí dos ejemplos elevar al cuadrado y multiplicar método para $5^{69} \bmod 101$ :

$$\begin{matrix} 5^{69} &\equiv& 5 &\cdot &(5^{34})^2 &\equiv & 37 \\ 5^{34} &\equiv& &&(5^{17})^2 &\equiv& 88 &(\equiv -13) \\ 5^{17} &\equiv& 5 &\cdot &(5^8)^2 &\equiv& 54 \\ 5^{8} &\equiv& &&(5^4)^2 &\equiv& 58 \\ 5^{4} &\equiv& &&(5^2)^2 &\equiv& 19 \\ 5^{2} &\equiv& &&(5^1)^2 &\equiv& 25 \\ 5^{1} &\equiv& 5 &\cdot &(1)^2 &\equiv& 5 \end{matrix}$$

El cálculo comienza con $5^{69}$ y luego trabajar hacia abajo para crear las dos primeras columnas, y luego calcular los resultados de abajo hacia arriba. (normalmente se omitiría la última línea; la he puesto ahí para aclarar el párrafo siguiente).

Como método abreviado, la representación binaria de $69$ es $1000101_2$ la lectura de los dígitos binarios de izquierda a derecha nos indica las operaciones a realizar a partir del valor $1$ : $0$ dice "cuadrado" y $1$ dice "elevar al cuadrado y multiplicar por $5$ ".

---

La otra forma es calcular una lista de cuadrados repetidos:

$$\begin{matrix} 5^1 &\equiv& 5 \\ 5^2 &\equiv& 25 \\ 5^4 &\equiv& 19 \\ 5^8 &\equiv& 58 \\ 5^{16} &\equiv& 31 \\ 5^{32} &\equiv& 52 \\ 5^{64} &\equiv& 78 \end{matrix}$$

A continuación, calcula qué términos tienes que multiplicar:

$$5^{69} \equiv 5^{64 + 4 + 1} \equiv 78 \cdot 19 \cdot 5 \equiv 37$$

Answer 4

Algunos trucos útiles para la exponenciación modular

La intención de este post es recopilar varios trucos que a veces pueden simplificar los cálculos de este tipo. (Especialmente cuando se hacen a mano y no con ordenador o calculadora.) Este post es comunidad-wiki, así que siéntete libre de editarlo si tienes alguna idea para mejorarlo.

Usar complemento: $(c-a) \equiv (-a) \pmod c$

Si el número dado se aproxima a $c$ (pero menor que $c$ ), sustituyéndolo por $c-a$ mi ayuda - trabajaremos con números más pequeños. Algunos ejemplos:

• Si queremos calcular $7^{777} \bmod 50$ es útil observar que $7^2=49 \equiv (-1) \pmod{50}$ por lo que podemos sustituir $7^2$ por $-1$ y obtener $7^{777} \equiv 7^{388} \cdot 7 \equiv (-1)^{388} \cdot 7 \equiv 7 \pmod{50}$ . (Esto formaba parte de Encuentre $3^{333} + 7^{777}\pmod{50}$ .)
• Queremos calcular $50^{50} \bmod 13$ . Desde $4\cdot 13 = 52$ tenemos $50 \equiv -2 \pmod{13}$ . Así que podemos trabajar con $-2$ en lugar de $50$ que será más fácil, ya que es un número más pequeño. Cómo utilizar el pequeño teorema de Fermat para hallar $50^{50}\pmod{13}$ ?

Si puedes encontrar una potencia cercana al módulo, intenta utilizarla.

Algunos ejemplos:

• Queremos calcular $6^{1000} \bmod 23$ . Desde $6=2\cdot 3$ veamos si podemos combinar de alguna manera estos dos números para obtener algo con un resto pequeño módulo $23$ . Podemos observar que $24=2^3\cdot 3 \equiv 1\pmod{23}$ . También podemos observar que $27 \equiv 4\pmod{23}$ es decir $3^3\equiv 2^2\pmod{23}$ . Sustitución de $2^2$ con $3^3$ en la congruencia anterior obtenemos $2\cdot 3^4 \equiv 1 \pmod{23}$ . Ahora podemos combinar las dos congruencias anteriores para obtener $1\equiv (2^3\cdot 3)^3\cdot(2\cdot 3^4)^2 = 2^{11}\cdot3^{11} = 6^{11}\pmod{23}$ . Obsérvese que la congruencia $6^{11}\equiv1\pmod{23}$ también puede obtenerse por distintos medios: Encuentre $6^{1000} \mod 23$ .
• Queremos encontrar $5^{119} \bmod 59$ . Esto puede resolverse de forma muy sencilla utilizando el pequeño teorema de Fermat: Hallar el resto utilizando el pequeño teorema de Fermat cuando $5^{119}$ se divide por $59$ ? Sin embargo, olvidemos el pequeño teorema de Fermat y tratemos de encontrar algunas potencias de $5$ que dan un resto pequeño módulo $59$ . Podemos observar que $5^3$ no está muy lejos de $2\cdot59$ y obtener $5^3\equiv125\equiv7\pmod{59}$ . Del mismo modo, $7\cdot25$ parece no estar muy lejos de $3\cdot59$ así que podemos intentar $5^5=5^3\cdot5^2\equiv7\cdot25\equiv175\equiv-2\pmod{59}$ . Y ahora podemos utilizar $64$ es una potencia de dos que se aproxima a nuestro resto para obtener $5^{30} = (5^5)^6 \equiv (-2)^6 \equiv 64 \equiv 5 \pmod{59}$ . Puesto que tenemos $5^{30}\equiv5\pmod{59}$ y $\gcd(5,59)=1$ podemos cancelar $5$ en ambos lados para obtener $5^{29}\equiv1\pmod{59}$ . Y este último dato puede utilizarse en cálculos posteriores.
• La tarea consiste en encontrar $16^{74} \bmod 65$ . Se puede observar que $64$ es una potencia de dos muy próxima a $65$ . Así que tenemos $2^6 = 64 \equiv -1 \pmod{65}$ lo que significa que $16^{74}=(2^4)^{74}=2^{296} = 2^{6\cdot49}\cdot2^2 \equiv (-1)^{49}\cdot4 \equiv -1\cdot 4 \equiv -4 \pmod{65}$ . Ver también Informática $16^{74} \bmod 65$ .

Utilizando el criterio de Euler

Criterio de Euler puede decirnos sobre el valor de $a^{\frac{p-1}2}$ módulo de un primo $p$ . Sin embargo, necesitamos saber si $a$ es un residuo cuadrático módulo $p$ . Para algunos números esto se puede adivinar. A veces se puede comprobar utilizando reciprocidad cuadrática (Por supuesto, esto no es una gran mejora en comparación con el pequeño teorema de Fermat, que nos da $a^{p-1}\equiv1\pmod p$ .)

• Veamos $5^{29} \bmod 59$ (ya lo hemos calculado anteriormente mediante diferentes cálculos). Es fácil darse cuenta de que $8^2=64\equiv5\pmod{59}$ Así que $5$ es un residuo cuadrático módulo $59$ . Así que a partir del criterio de Euler obtenemos $5^{29}=5^{(59-1)/2}\equiv1\pmod{29}$ .

Answer 5

El teorema chino del resto puede reducir el cálculo necesario. Por ejemplo, podemos factorizar $21 = 3 \cdot 7$ y tienen

$$1 \cdot 7 - 2 \cdot 3 = 1$$

(en general, podemos utilizar el algoritmo euclidiano ampliado para obtener esta fórmula)

Por consiguiente, si

$$x \equiv a \pmod 3 \qquad x \equiv b \pmod 7$$

entonces

$$x \equiv a \cdot (1 \cdot 7 ) + b \cdot (-2 \cdot 3) \pmod{21}$$

Así, podemos calcular $5^{844325} \bmod 21$ utilizando nuestros medios favoritos para calcular:

$$5^{844325} \equiv 2 \pmod 3 \qquad 5^{844325} \equiv 3 \pmod 7$$

y así

$$5^{844325} \equiv 2 \cdot 7 + 3 \cdot (-6) \equiv -4 \equiv 17 \pmod{21}$$