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

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} $$

Answer 2

Para la primera pregunta: utilice $a^{\Phi(c)}=1 \mod c$ donde $\Phi(c)$ es el número de coprimos de $c$ debajo de $c$ . Para $c=21=7\cdot 3$ tenemos $\Phi(c)=(7-1)\cdot(3-1)=12$

segunda pregunta: Utilice $a^4=(a^2)^2, a^8=(a^4)^2$ etc. Descomponer el exponente en potencias de 2 y combinarlas utilizando $a^n\cdot a^m=a^{n+m}$ Por ejemplo $a^{69}=a^{64}\cdot a^4\cdot a^1$

Answer 3

Hay algunas cosas dignas de mención:

• Las reglas de los exponentes ayudan. Si b es un compuesto grande, siendo el producto de d,e,f,g,h,i,j,... entonces potenciar a b es como potenciar por d luego e luego f luego g haciendo cada uno a su vez a sus resultados, es más fácil (tal vez tan tedioso) que un gran cálculo.
• Si a y c son coprimos, entonces a elevado a cualquier potencia también será coprimo, así que o bien usas todos los restos coprimos o no pero puedes saberlo potenciando hasta que el resto sea 1, y 1 elevado a cualquier potencia es 1 permitiéndote recortar b. (básicamente detrás de Euler y Fermat)
• si a y c no son coprimos, entonces potencias de a, se sitúan en múltiplos de su gcd.
• Las reglas de los exponentes ayudan de nuevo si encuentras una suma igual a b puedes usar la regla del producto de potencias de la misma base = suma de exponentes.(la exponenciación binaria usa esto)
• si a es mayor que la mitad de c, utilice -(c-a) en su lugar (otro nombre para a)
• si a>c, toma primero a mod c.
• etc.

Answer 4

Concretamente en el caso de $\gcd(a,c)\ne1$ podemos utilizar una generalización del teorema del totiente de Euler, que nos da:

$$a^b\equiv a^{(b\bmod\varphi)+\varphi}\pmod c$$

donde $b>\varphi=\varphi(c)$ .

Utilizando el teorema chino del resto, esto se puede mejorar a $\varphi=\varphi(c')$ donde $c'$ es el mayor factor de $c$ que es coprimo a $a$ . Para un cálculo de fuerza bruta de $c'$ se puede utilizar $c'=c/\gcd(a^{\lfloor\log_2(c)\rfloor},c)$ .

Cuando tengamos $b<2\varphi$ podemos aplicar la exponenciación al cuadrado.

En tu ejemplo:

$\varphi(c')=\varphi(7)=6$ Así que $\bmod14:$

$6^{103}\\\equiv6^{(103\bmod6)+6}\\=6^7\\=6\times36^3\\\equiv6\times8^3\\=48\times64\\\equiv6\times8\\=48\\\equiv6$

Answer 5

Añadir un ejemplo para calcular el resto de una potencia iterada.

Busquemos los dos últimos dígitos de $97^{75^{63}}$ .

Equivalentemente, queremos encontrar su resto módulo $100$ .

1. En primer lugar, observamos que $\gcd(97,100)=1$ . Si aquí tuviéramos factores primos comunes, trataríamos cada potencia prima por separado utilizando el teorema chino del resto. Véase también esta respuesta (y los tres pasos siguientes). Dado que $\phi(100)=40$ podemos deducir inmediatamente que $97^{40}\equiv1\pmod{100}$ .
2. Por lo tanto, a continuación tenemos que determinar el resto del exponente $75^{63}$ modulo $40$ . Observe que $\gcd(75,40)=5$ por lo que la potencia es obviamente un múltiplo de cinco. Necesitamos determinar su clase de residuo modulo $40/5=8$ .
3. Módulo $8$ tenemos $75\equiv3$ . Por lo tanto $75^{63}\equiv3^{63}\pmod 8$ . Vemos que $3^2=9\equiv1\pmod8$ Así que $3^{63}\equiv3\pmod8$ .
4. Así que sabemos que $75^{63}$ es divisible por $5$ y deja el resto $3$ modulo $8$ . Porque $35$ tiene estos mismos residuos módulo $5$ y $8$ y $\gcd(5,8)=1$ el teorema chino del resto nos dice que $75^{63}\equiv35\pmod{40}.$
5. El gran número $97^{75^{63}}$ es por tanto congruente con $97^{35}\pmod {100}$ . Ahora podemos recurrir a exponenciación al cuadrado o utilizar otros trucos. Hagamos lo que hagamos, el resultado final es que $$97^{35}\equiv93\pmod{100},$$ por lo que podemos concluir que los dos últimos dígitos son $93$ .

---

En lugar de la función totiente de Euler $\phi(n)$ puede utilizar el Función Carmichael $\lambda(n)$ en su lugar. La carga de trabajo puede reducirse considerablemente. Sobre todo si un exponente tiene un resto pequeño módulo $\lambda(n)$ pero un resto grande módulo $\phi(n)$ .