¿Cómo calcularíamos 22 ^ 362 mod 12 usando el método de exponenciación rápida?

Answer 1

1. Separe el exponente en sus poderes de 2. Entonces:
   362 = 256 + 64 + 32 + 8 + 2 o 362 = 2 ^ 8 + 2 ^ 6 + 2 ^ 5 + 2 ^ 3 + 2 ^ 1 …
2. Ya puedes decir 22 mod 12 = 10 mod 12. Así que úsalo para un cálculo más fácil.
3. (22 ^ 2) mod 12 = (10 ^ 2) mod 12 = 100 mod 12 = 4 mod 12
4. Después de eso, multiplica el resultado del paso 3 tantas veces como sea necesario para calcular varios componentes exponenciales de potencias de 2. Como
   (22 ^ 4) mod 12 = (22 ^ 2) ^ 2 mod 12 o (22 ^ 2 * 22 ^ 2) mod 12
   Sin embargo, este es un número interesante ya que
   (4 * 4) mod 12 = 16 mod 12 = 4 mod 12
   Eso significa que todos los componentes exponenciales son todos 4 mod 12; Además, toda su multiplicación también produce 4 mod 12.
5. Para resumir (todo en el mod 12):
   22 ^ 362 = 22 ^ 256 * 22 ^ 64 * 22 ^ 32 * 22 ^ 8 * 22 ^ 2
   = 4 * 4 * 4 * 4 * 4 = 4 (mod 12)
   ¡Guau, acabamos de hacer una aritmética exponencial muy larga desde lo más alto de nuestras mentes! 😀

Answer 2

1. Copie el código de Internet: exponenciación al cuadrado – Wikipedia
2. Llame a la función desde IDE / IDLE / REPL con esos valores como argumentos.
3. Lee el resultado.