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

Aquí utilizamos un algoritmo de 'trabajo en el lugar / manera perezosa / a mano' para el problema

$\quad$ Resuelva $5^{69}\,\bmod 101$ .

$\; 5^{69} = \big((4 + 1) 5^2\big)^{23} \equiv 24^{23}= 24 \big((4 + 20) {24}\big)^{11} \equiv 24\, (71^{11}) \equiv -24\, (30^{11}) =$
$\quad (-24)(30) \big((15 + 15) 30\big)^{5} \equiv (-24)(30)\, ({-9}^{5}) \equiv 24 \times 30 \times (-20) \times (-20) \times 9 \equiv$ $\quad 24 \times 30 \times (-4) \times 9 \equiv 24 \times (-19) \times 9 \equiv 24 \times (-70) \equiv 24 \times 31 \equiv$
$\quad (24 \times 4) \times 8 - 24 \equiv -64 \equiv 37 \,\bmod 101$

---

Nota: Como se utilizó cierta discreción, en realidad no especificamos un algoritmo. Pero el trabajo podría hacerse para que un ordenador utilice tablas de búsqueda simples y produzca salidas similares sin utilizar ningún registro matemático.

Answer 2

No es difícil demostrar que la secuencia

$$x_n=a^n\mod{c}$$

es periódica, con período $p$ (que es como máximo $c$ ). Evalúe los primeros términos para obtener el período $\{x_0,x_1,\dots,x_{p-1}\}$ . Entonces usted puede evaluar para cualquier poder enorme $n$ como

$$x_n=x_{n\mod{p}}$$