##
Por último, exploremos la propiedad de la potenciación:

A^B mod C = ( (A mod C)^B ) mod C

A menudo queremos calcular A^B mod C para valores grandes de B.
Desafortunadamente, A^B se vuelve muy grande incluso para valores modestos de B.

For Example:

2^90 = 1.237.940.039.290.000.000.000.000.000
7^256 = 2.213.595.400.050.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 83.794.038.078.300.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000 721.264.246.243.000.000.000.000.000
Estos valores tan grandes causan que nuestras calculadoras y computadoras den un mensaje de error (overflow).
Incluso aunque no lo hicieran, tomaría mucho tiempo encontrar el módulo de estos números tan largos de manera directa.

¿Qué podemos hacer para reducir el tamaño de los términos involucrados y hacer nuestro cálculo más rápido?

Supongamos que queremos calcular 2^90 mod 13, pero tenemos una calculadora que no puede trabajar con números más grandes que 2^50.
Aquí esta una estrategia sencilla de divide y vencerás:
partes más pequeñas
las reglas de los exponentes:
2^90 = 2^50 * 2^40
módulo C
cada parte:
2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3
propiedades de la multiplicación
combinar las partes:
2^90 mod 13 = (2^50 * 2^40) mod 13
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12

¿Cómo podemos calcular A^B mod C rápidamente si B es una potencia de 2?

¿Cómo podríamos calcular 7^256 mod 13 usando una calculadora que no pueda trabajar con números más grandes que 7^10 ?
Podríamos dividir 7^256 en 25 partes de 7^10 y 1 parte de 7^6, pero esto no sería muy eficiente.
Hay una mejor manera....