Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 2
Lección 5: Aritmética modular- ¿Qué es la aritmética modular?
- Operador módulo
- Desafío de módulo
- Congruencia módulo
- Relación de congruencia
- Relaciones de equivalencia
- El teorema del cociente y del residuo
- Suma y resta modular
- Suma modular
- Desafío de módulo (suma y resta)
- Multiplicación modular
- Multiplicación modular
- Exponenciación modular
- Exponenciación modular rápida
- Exponenciación modular rápida
- Inversos modulares
- El algoritmo de Euclides
© 2023 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
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.
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.
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
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
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?
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)
Donde esta la mejor manera? Esta incompleta la información(1 voto)