If you're seeing this message, it means we're having trouble loading external resources on our website.

Si estás detrás de un filtro de páginas web, por favor asegúrate de que los dominios *.kastatic.org y *.kasandbox.org estén desbloqueados.

Contenido principal

Exponenciación modular

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.

Por exjemplo:

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 al usar 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....

¿Quieres unirte a la conversación?

  • Avatar male robot hal style para el usuario diego bustillo
    un truco con los mod's es el siguiente=
    por ejemplo 14mod2=0
    pero 15mod2=1 porque son diferentes?
    porque 14/2=7 y 15/2=7.5
    si el 7 es un entero en la respuesta del mod se pone lo que sobra o sea 0
    en cambio si divides 15 entre dos (sin decimal) sale 7 y 8
    por lo cual si los haces parejo(7y7) sobra 1.
    si esto te ayuda dale un voto a favor
    (2 votos)
    Avatar Default Khan Academy avatar para el usuario
  • Avatar blobby green style para el usuario Tapia Alvarez
    Donde esta la mejor manera? Esta incompleta la información
    (1 voto)
    Avatar Default Khan Academy avatar para el usuario
¿Sabes inglés? Haz clic aquí para ver más discusiones en el sitio en inglés de Khan Academy.