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 rápida
¿Cómo podemos calcular A^B mod C rápidamente si B es una potencia de 2?
Usando las reglas de la multiplicación modular:
es decir, A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
Podemos usar esto para calcular 7^256 mod 13 rápidamente:
7^1 mod 13 = 7
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
Podemos sustituir nuestro resultado anterior por 7^1 mod 13 en esta ecuación.
7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10
7^2 mod 13 = 10
7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13
Podemos sustituir nuestro resultado anterior por 7^2 mod 13 en esta ecuación.
7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9
7^4 mod 13 = 9
7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13
Podemos sustituir nuestro resultado anterior por 7^4 mod 13 en esta ecuación.
7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3
7^8 mod 13 = 3
Continuamos de esta manera, sustituyendo resultados anteriores en nuestras ecuaciones.
... después de 5 iteraciones llegamos a:
7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
Esto nos da un método para calcular A^B mod C rápidamente siempre y cuando B sea una potencia de 2.
Sin embargo, también necesitamos un método para una exponenciación modular rápida cuando B no sea una potencia de 2.
¿Cómo podemos calcular A^B mod C rápidamente para cualquier B?
Paso 1: divide B en potencias de 2 al escribirlo en binario:
Comienza con el dígito de la extrema derecha, haz k=0 y para cada dígito:
- Si el dígito es 1, necesitamos una parte para 2^k, de lo contrario no es necesario.
- Súmale 1 a k y muévete al siguiente dígito a la izquierda.
Paso 2: calcula el mod C de las potencias de dos ≤ B
5^1 mod 19 = 5
5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
Paso 3: usa las propiedades de multiplicación modular para combinar los valores calculados de mod C
5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
Notas:
Existen más técnicas de optimización, pero están fuera del alcance de este artículo. Debe tenerse en cuenta que cuando realizamos exponenciación modular en criptografía, no es raro utilizar exponentes para B > 1000 bits.
¿Quieres unirte a la conversación?
Sin publicaciones aún.