Calcular un exponente muy grande

[dmorill]

Hola amigos ahora os traigo una pregunta que que no he podido aún responder.

Como puedo calcular 3^520 y luego sacar un modulo. El problema está en que en que ninguna variable de ningún tipo puede almacenar un valor tan grande para realizar la operación. He buscado algo de información al respecto pero lo único que he encontrado es intentar dividir la operación el pequeñas operaciones pero cuando voy a unir el número el problema resurge pues no puedo almacenarlo.

Saludos,

[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

[dmorill]

Hola eferion muchas gracias, tu siempre atento y presto a compartir tus conocimientos. Lo implementaré y te comentaré como va, muchas gracias.