punto 3 de este teorema, lo demostraremos aquí y dejaremos las demostraciones de las partes restantes del teorema a los ejercicios del 9 al 11 al f...

punto 3 de este teorema, lo demostraremos aquí y dejaremos las demostraciones de las partes restantes del teorema a los ejercicios del 9 al 11 al final de la sección. 8.4 Aritmética modular con aplicaciones a la criptografía 483 Demostración del inciso 3: Suponga que a, b, c, d y n son enteros con n 1 y suponga que a b (mod n) y c d (mod n). Por el teorema 8.4.1, existen enteros s y t tales que a c sn y b d tn. Entonces ab = (c + sn)(d + tn) = cd + ctn + snd + sntn = cd + n(ct + sd + stn) por sustitución por álgebra. Sea k ct sd stn. Entonces k es un entero y ab cd nk. Así por el teorema 8.4.1, ab cd (mod n). Ejemplo 8.4.2 Iniciando con la aritmética modular El uso más práctico de la aritmética modular es reducir los cálculos que implican grandes enteros a cálculos que implican pequeños. Por ejemplo, observe que 55 3 (mod 4) ya que 55 ฀ 3 52, es divisible por 4 y 26 2 (mod 4) ya que 26 ฀ 2 24, que es también divisible por 4. Compruebe los siguientes enunciados. a. 55 26 (3 2) (mod 4) b. 55 ฀ 26 (3 ฀ 2) (mod 4) c. 55 26 (3 2) (mod 4) d. 552 32 (mod 4) Solución a. Calcule 55 26 81 y 3 2 5. Por definición de congruencia módulo n, para demostrar que 81 5 (mod 4), necesita demostrar que 4 (81 ฀ 5). Pero esto es ver- dadero ya que 81 ฀ 5 76 y 4 76 puesto que 76 4 19. b. Calcule 55 ฀ 26 29 y 3 ฀ 2 1. Por definición de congruencia módulo n, para demostrar que 29 1 (mod 4), necesita demostrar que 4 (29 ฀ 1). Pero esto es ver- dadero ya que 29 ฀ 1 28 y 4 28 puesto que 28 4 7. c. Calcule 55 26 1 430 y 3 2 6. Por definición de congruencia módulo n, para demostrar que 1 430 6 (mod 4), necesita demostrar que 4 (1 430 ฀ 6). Pero esto es verdadero ya que 1 430 ฀ 6 1 424 y 4 1 424 puesto que 1 424 4 356. d. Calcule 552 3 025 y 32 9. Por definición de congruencia módulo n, para demostrar que 3 025 9 (mod 4), necesita demostrar que 4 (3 025 ฀ 9). Pero esto es verdadero ya que 3 025 ฀ 9 3 016 y 4 3 016 puesto que 3 016 4 754. Para facilitar los cálculos que se realizan en esta sección, es conveniente expresar el inciso 3 del teorema 8.4.3 en una forma ligeramente diferente. Corolario 8.4.4 Sean a, b y n enteros con n 1. Entonces ab [(a mod n)(b mod n)] (mod n), o, equivalentemente, ab mod n [(a mod n)(b mod n)] mod n. En particular, si m es un entero positivo, entonces a m [(a mod n)m] (mod n). 484 Capítulo 8 Relaciones Ejemplo 8.4.3 Cálculo de un producto módulo n Como en el ejemplo 8.4.2, observe que 55 3 (mod 4) y 26 2 (mod 4). Ya que ambos 3 y 2 son menores que 4, cada uno de estos números es un residuo no negativo mínimo módulo 4. Por tanto, 55 mod 4 3 y 26 mod 4 2. Use la notación del corolario 8.4.4 para encontrar el residuo de 55 26 módulo 4. Solución Recuerde que al utilizar una calculadora para cuantificar residuos, puede utilizar la fórmula n mod d n ฀ d n d . Si se utiliza una calculadora de mano con una caracte- rística de “parte entera” y tantos n como d son positivos, entonces n d es la parte entera de la división de n entre d. Cuando se divide un entero positivo n entre un entero positivo d con una calculadora más básica, se puede ver n d en la presentación de la calculadora simplemente haciendo caso omiso de los dígitos que siguen al punto decimal. Por el corolario 8.4.4, 55 26 mod 4 55 mod 4 26 mod 4 mod 4 3 2 mod 4 ya que 55 mod 4 3 y 26 mod 4 2 6 mod 4 2 ya que 4 6฀ 2 y 2 4. Cuando se realiza aritmética modular con un gran número, como es el caso de la cripto- grafía RSA, los cálculos se facilitan utilizando dos propiedades de exponentes. La primera es X 2a (xa)2 para todos los números reales x y a con x 0. 8.4.1 Así, por ejemplo, si x es cualquier número real positivo, entonces x4 mod n = (x2)2 mod n = (x2 mod n)2 mod n ya que (x 2)2 x 4 por el corolario 8.4.4. Por tanto puede reducir x4 módulo n reduciendo x2 módulo n y después reduciendo el cua- drado del módulo n resultante. Ya que todos los residuos son menores que n, este proceso limita el tamaño de los cálculos a números que son menores que n2, lo que hace más fácil trabajar con ellos, tanto para los seres humanos (cuando los números son relativamente pequeños) y para computadoras (cuando los números son muy grandes). Una segunda propiedad útil de los exponentes es x a b x a x b para todos los números reales x, a y b con x 0. 8.4.2 Por ejemplo, ya que 7 4 2 1, x 7 x4 x2 x1 Así, por el corolario 8.4.4, x 7 mod n {(x4 mod n)(x2 mod n)(x1 mod n)} mod n. Primero damos un ejemplo que muestra la aplicación de la fórmula (8.4.1) y después un ejemplo que utiliza tanto a la (8.4.1) como a la (8.4.2). 8.4 Aritmética modular con aplicaciones a la criptografía 485 Ejemplo 8.4.4 Cálculo de a k mod n cuando k es una potencia de 2 Determine 1444 mod 713. Solución Use la propiedad (8.4.1) para escribir 1444 (1442)2. Entonces 1444 mod 713 1442 2 mod 713 1442 mod 713 2 mod 713 20 736 mod 713 2 mod 713 592 mod 713 3 481 mod 713 629 ya que 1442 20 736 ya que 20 736 mod 713 59 ya que 592 3 481 ya que 3 481 mod 713 629. Ejemplo 8.4.5 Cálculo de a k mod n cuando k no es una potencia de 2 Determine 1243 mod 713. Solución Primero escriba al exponente como una suma de potencias de 2: 43 25 23 2 1 32 8 2 1. Ahora calcule 122k para k 1, 2, 3, 4, 5. 12 mod 713 = 12 122 mod 713 = 144 124 mod 713 = 1442 mod 713 = 59 128 mod 713 = 592 mod 713 = 629 1216 mod 713 = 6292 mod 713 = 639 1232 mod 713 = 6392 mod 713 = 485 por ejemplo 8.4.4 por ejemplo 8.4.4 por el método del ejemplo 8.4.4 por el método del ejemplo 8.4.4 Por la propiedad (8.4.2), 1243 = 1232+8+2+1 = 1232 ·128 ·122 ·121. Así, por el corolario 8.4.4, 1243 mod 713 = {(1232 mod 713) ·(128 mod 713) ·(122 mod 713) ·(12 mod 713)} mod 713. Por sustitución, 1243 mod 713 = (485 ·629 ·144 ·12) mod 713 = 527152320 mod 713 = 48. ■ Es importante entender cómo hacer los cálculos a mano del ejemplo 8.4.5 utilizando sólo una simple calculadora electrónica, pero si está calculando muchos residuos, especialmente los relacionados con números grandes, puede que desee escribir un programa de calculadora de computadora pequeña para hacer los cálculos personales. Extensión del algoritmo de Euclides Una versión extendida del algoritmo de Euclides puede utilizarse