Calcular un exponente muy grande

[eferion]

Si tu quieres calcular r = a^b mod c tienes que operar de la siguiente forma:

1. a1 = a mod c
2. inicializa r=1
3. itera i=1 hasta b
   1. r = r * a1
   2. r = r mod c

Al final del proceso obtendrás en r el resultado de la operación:

3^10 mod 7 = 4
a1 = 3, pues 3 = 3 mod 7

1. 1 * 3 = 3 mod 7
2. 3 * 3 = 2 mod 7
3. 2 * 3 = 6 mod 7
4. 6 * 3 = 4 mod 7
5. 4 * 3 = 5 mod 7
6. 5 * 3 = 1 mod 7
7. 1 * 3 = 3 mod 7
8. 3 * 3 = 2 mod 7
9. 2 * 3 = 6 mod 7
10. 6 * 3 = 4 mod 7

como ves, tras 10 iteraciones el resultado es el correcto, 4.

Hay formas más óptimas de llegar al mismo resultado pero el algoritmo es más complejo, este creo que es sencillo e ilustrativo.

Por si a alguien le pica la curiosidad, un algoritmo optimizado:

1. a1 = a mod m
2. r = 1
3. mientras b>0
   1. si b es impar
      1. r *= a1
      2. r = r mod c
   2. b /= 2
   3. a1 = (a1 * a1) mod c

Es decir:

1. b=10, luego
   • b=10/2=5
   • a1=(3*3) mod 7 = 2
2. b=5, luego
   • r=(1*2) mod 7 = 2
   • b=5/2=2
   • a1=(2*2) mod 7 = 4
3. b=2, luego
   • b=2/2=1
   • a1=(4*4) mod 7 = 2
4. b=1, luego
   • r=(2*2) mod 7 = 4
   • b=1/2=0
   • a1=(2*2) mod 7 = 4

Finalmente, r=4

Un saludo