Ingeniería Informática
I NTRODUCCIÓN A LA M ATEMÁTICA D ISCRETA
53 ejercicios sobre Aritmética modular
1. Ejercicios básicos
E JERCICIO 1 [0]
Halla la solución general de la ecuación 12x ≡ 9 (mod 15).
Respuestas: x = 2 + 5k con k ∈ Z.
E JERCICIO 2 [0]
Halla todas las soluciones de la ecuación 91x ≡ 419 (mod 440).
Respuestas: x = 169 + 440k
E JERCICIO 3 [0]
Halla la solución general de la ecuación 54x ≡ 342 (mod 23400).
Respuestas: x = 873 + k · 1300, con 0 ≤ k ≤ 17
E JERCICIO 4 [0]
Resuelve las siguientes ecuaciones:
1. 225x ≡ 18 (mod 31315).
2. 1235x ≡ 65 (mod 25948).
Respuestas:
1. Sin solución.
2. x = 1896 + 1996k
E JERCICIO 5 [0]
Para cada una de las siguientes ecuaciones, decide cuáles tiene solución y resuelve las que la tengan.
1. 3x ≡ 5 (mod 7)
2. 12x ≡ 15 (mod 22)
3. 19x ≡ 42 (mod 50)
4. 18x ≡ 42 (mod 50)
Respuestas:
1. x = 4 + 7k
2. Sin solución.
1
3. x = 18 + 50k
4. x = 19 + 25k
E JERCICIO 6 [0]
¿Existe algún múltiplo de 91 terminado en 15? En caso afirmativo encuentra cuántos hay comprendidos entre
10000 y 30000.
Respuestas: Exactamente 2.
E JERCICIO 7 [0]
1. Prueba que si a m ≡ 1 (mod n) con m ∈ Z y m ≥ 2, entonces mcd (a, n) = 1.
2. Si a no es una unidad en Z26 y a 10 ≡ 10 (mod 26), entonces ¿cuánto vale mcd(a, 26)?
Respuestas:
2. 13
E JERCICIO 8 [0]
Resuelve los siguientes sistemas de ecuaciones en congruencias:
x ≡ 1 (mod 4)
x ≡ 2 (mod 7)
3x ≡ 6 (mod 12)
a) x ≡ 2 (mod 3) b) x ≡ 7 (mod 9) c) 2x ≡ 5 (mod 7)
x ≡ 3 (mod 5) x ≡ 3 (mod 4) 3x ≡ 1 (mod 5)
x ≡ 13 (mod 40) 2x ≡ 2 (mod 12) 5x ≡ 5 (mod 6)
d) x ≡ 5 (mod 44) e) x ≡ 5 (mod 14) f) 3x ≡ 2 (mod 14)
x ≡ 38 (mod 275) x ≡ 4 (mod 21) x ≡ −2 (mod 21)
Respuestas:
1. x = 53 + 60 · λ con λ ∈ Z.
2. x = 79 + 252 · λ con λ ∈ Z.
3. x = 62 + 140 · λ con λ ∈ Z.
4. x = 1413 + 2200 · λ con λ ∈ Z.
5. Sin solución.
6. Sin solución.
E JERCICIO 9 [1]
Dado el sistema
x ≡4 (mod 8)
x ≡α (mod 6)
x ≡ −1 (mod 15)
1. Determina todos los posibles valores de α ∈ Z para los que el sistema tiene solución.
2
2. Demuestra que la solución del sistema es independiente del valor de α.
3. Resuelve el sistema en los casos en que tiene solución.
Respuestas:
1. α = 2 + 6k con k ∈ Z.
2. La solución no depende de α.
3. x = 44 + 120 · λ con λ ∈ Z.
E JERCICIO 10 [1]
Siete ladrones tratan de repartir, entre ellos y a partes iguales, un botín de lingotes de oro. Desafortunadamente,
sobran seis lingotes y en la pelea que se desata muere uno de ellos. Como al hacer de nuevo el reparto sobran
dos lingotes, vuelven a pelear y muere otro. En el siguiente reparto vuelve a sobrar una barra y sólo después de
que muera otro es posible repartirlas por igual. ¿Cuál es el mínimo número de barras para que esto ocurra?
Respuestas: La solución general es x = 356 + 420 · λ con λ ∈ Z, y el menor valor positivo se obtiene para k = 0,
que es 356.
E JERCICIO 11 [1]
Una banda de 20 piratas trata de repartirse un botín de entre 5000 y 10000 monedas de oro. Al intentar hacer un
reparto equitativo les sobran 15 monedas que se disputan entre ellos y como consecuencia de la pelea muere
uno de los piratas. Deciden hacer de nuevo un reparto equitativo pero les vuelven a sobrar 15 monedas. En una
nueva disputa vuelve a morir otro de los piratas y al volver a efectuar el reparto les sobran 3 monedas.
1. Calcula el número de monedas del botín.
2. Si la historia continúa, es decir, siempre que sobren monedas se organiza una reyerta y muere uno de los
piratas, ¿cuántos quedarán vivos cuando en el reparto no sobre ninguna moneda? (la respuesta deberá
obtenerse sin probar a eliminar sucesivamente piratas hasta dar con la solución).
Respuestas:
1. 7995.
2. 15 supervivientes.
E JERCICIO 12 [1]
Se dispone de un número par de monedas, N . Si formamos montones de 17 monedas cada uno nos sobran
8 monedas, mientras que si, con la mitad de las monedas iniciales, se forman montones de 7 nos sobran 3.
Calcular la cantidad de monedas de que se disponía sabiendo que su número era inferior a 600. En caso de
existir más de una solución, ¿existe alguna de ellas para la que 7N mod 31 = p siendo p un número primo? ¿Es
ahora única la solución?
Respuestas: La solución general es x = 38 + 119 · λ con λ ∈ Z.
N = 36 y N = 314.
E JERCICIO 13 [1]
Laura trabaja cuatro días seguidos y descansa al quinto. María trabaja dos y descansa al tercero.
3
1. Si sólo se ven cuando ambas descansan y hay luna llena (la luna tiene un periodo de 28 días) ¿cuándo
volverán a verse si María descansó ayer, Laura lo hará pasado mañana y hace diez días que hubo luna
llena?
2. Hasta esa fecha, ¿cuántos días habrán descansado ambas pero no se habrán visto por falta de luna llena?
Respuestas:
1. Se verán en 242 días.
2. 15 veces.
E JERCICIO 14 [1]
En un ordenador se han lanzado tres procesos que periódicamente acceden a un recurso compartido. Si dos
de ellos acceden de forma simultánea no hay problemas, pero si lo hacen los tres se producirá un bloqueo.
Considerando los datos de la siguiente tabla, se pide:
Proceso accede por primera vez al recurso accede cada
1 10:00 horas 5 minutos
2 10:02 horas 12 minutos
3 c minutos después de las 10 horas 4 minutos
1. Llamando x al número de minutos transcurridos desde las 10:00 horas hasta la ocurrencia de un bloqueo,
razona que x debe verificar el sistema de congruencias
x ≡ 0 ( mod 5)
x ≡ 2 ( mod 12)
x ≡ c ( mod 4)
2. Demuestra que se producirá un bloqueo si y sólo si, c ≡ 2 (mod 4).
3. Si c = 6, encuentra la hora del primer bloqueo que se producirá entre las 10:00 y las 11:00 horas. ¿Y para
c = 10?
Respuestas:
1. x ≡ c (mod 4)
2. c ≡ 2 (mod 4) y la solución es independiente de c.
E JERCICIO 15 [1]
En un almacén hay tres lámparas A, B y C controladas por temporizadores que se activan cada cierto tiempo,
solo a las horas en punto, y se apagan a los 60 minutos. La lámpara A se enciende cada 6 horas, la B cada 10
horas y la C cada 15 horas. La lámpara A se programó para ponerse en funcionamiento por primera vez a las
8:00 y la B a las 12:00.
1. ¿Cuál es la primera hora a la que se debe empezar a encender la tercera para que no coincida nunca con
ninguna de las dos primeras?
2. Si se quiere que en algún momento coincidan las tres lámparas encendidas, ¿cuál es la primera hora a la
que se debe empezar a encender la tercera?
Respuestas:
4
1. C debe encenderse por primera vez a las 04:00.
2. El primer valor posible es h = 2: a las 2:00.
E JERCICIO 16 [0]
Deduce criterios de divisibilidad de un entero por 2, 3, 4 y 2r basados en su expresión binaria.
E JERCICIO 17 [0]
Halla todos los enteros n para los que φ(n) es impar.
Respuestas: n = 2
E JERCICIO 18 [0]
Utiliza el teorema de Fermat para calcular los restos de dividir:
1. 528574 entre 17.
2. 35346 entre 41.
Respuestas:
1. 15.
2. 2.
E JERCICIO 19 [0]
Utiliza el teorema de Fermat para calcular los restos de dividir:
1. 3302 mod 5, 3302 mod 7, 3302 mod 11.
2. Utiliza los resultados anteriores y el Teorema Chino de los Restos para calcular 3302 mod 385.
Respuestas:
1. 4.
2.
9.
2. 9.
E JERCICIO 20 [0]
Demuestra que si p, p + 2, p + 4 son primos, entonces p = 3.
Respuestas: Trabaja en Z3
E JERCICIO 21 [1]
Demuestra que si a es primo con n entonces hay una potencia de a, r = a k tal que r 2 = 1 en Zn .
E JERCICIO 22 [1]
5
Demuestra que n es primo con m si y solo si n mod m es primo con m.
E JERCICIO 23 [1]
Demuestra que si n 1 , n 2 , . . . , n k son enteros mayores que 1, tales que mcd(n i , n j ) = 1 para todo par i 6= j , y
n = n 1 n 2 · . . . · n k , entonces el sistema
x ≡ b 1 (mod n 1 )
x ≡ b (mod n )
2 2
...
x ≡ b k (mod n k )
tiene como solución en Zn :
x = a 1 (n/n 1 )φ(n1 ) + . . . + a k (n/n k )φ(nk )
E JERCICIO 24 [0]
Demuestra que si mcd(n, m) = 1, entonces m φ(n) + n φ(m) = 1 (mod nm)
E JERCICIO 25 [0]
Demuestra que para todo par de enteros a, n con n positivo se verifica que las expresiones decimales de a y
a 4n+1 tienen la misma cifra de las unidades.
E JERCICIO 26 [1]
Sea n = p · q, producto de dos primos impares distintos y
x = (p · (p −1 mod q) − q · (q −1 mod p)) mod n
1. Demuestra que x 2 = 1 en Zn y que x 6= ±1.
2. Demuestra que mcd(x − 1, n) es uno de los dos, p o q..
E JERCICIO 27 [1]
Sea p > 3 un primo y α, β enteros positivos. Si n = 2α 3α p β y φ(n) = 216, se pide:
1. Determina los posibles valores de n.
2. Si n 1 < n 2 son dos soluciones del apartado anterior, calcula φ(n 2 − n 1 ).
Respuestas:
1. 654 y 684
2. 8
E JERCICIO 28 [1]
El número del DNI consiste en 8 dígitos decimales más una letra de control que se obtiene calculando el valor
del número 23 y buscando el resultado en la tabla siguiente:
0 1 2 3 4 5 6 7 8 9 10 11
T R W A G M Y F P D X B
12 13 14 15 16 17 18 19 20 21 22
N J Z S Q V H L C K E
6
Estudia las siguientes afirmaciones:
1. Si recibimos un DNI donde exactamente un dígito es ilegible, es posible recuperar su valor a partir de la
letra.
2. Intenta recuperar el siguiente DNI: 2835051 − V.
3. La letra de control puede detectar un DNI con un dígito equivocado y corregirlo.
4. La letra de control es una especie de resumen que sirve para detectar errores y corregirlos.
Respuestas:
2 28335051 − V
3 Falso.
4 Algunas veces.
E JERCICIO 29 [0]
Queremos cifrar mensajes mediante RSA usando el alfabeto
O A B C D E I Ñ O S T
00 01 02 03 04 05 06 07 08 09 10
1. Si queremos dividir el mensaje en bloques de 2 caracteres, ¿sería válida la clave (n = 1046429, e = 860081)?
2. Descifra el mensaje
254997, 159427, 655945, 253529, 694904, 228091
cifrado con la clave anterior.
Respuestas:
1. La clave es correcta.
2. AÑO BISIESTO
E JERCICIO 30 [0]
Halla el valor de la función de Euler φ(n) para n = 59437. Usa este valor para calcular 550905 mod n. 5.
Respuestas: φ(n) = 50904, 5.
E JERCICIO 31 [0]
Sabiendo que n = p · q, producto de dos primos y que φ(n) = 24, halla los posibles valores de n.
Respuestas: 39 y 35.
E JERCICIO 32 [1]
En este ejercicio se utiliza el alfabeto siguiente:
O A B C D E F G H I J K L M
00 01 02 03 04 05 06 07 08 09 10 11 12 13
N Ñ O P Q R S T U V W X Y Z
14 15 16 17 18 19 20 21 22 23 24 25 26 27
7
1. Se quiere cifrar texto mediante RSA agrupando los caracteres de 1 en 1. Si deseamos que el módulo n =
p · q sea tal que p y q sean cada uno de ellos mayores que el mayor bloque posible, halla cuál es la clave
(n, e) con n y e de lo más pequeños posible.
2. Halla la clave privada d para esa clave pública.
3. Se ha recibido el mensaje cifrado 380, 605, 858, 1. Halla el mensaje en claro.
Respuestas:
1. e = 1
2. d = 661
3. HOLA
E JERCICIO 33 [1]
En este ejercicio se utiliza el alfabeto siguiente:
O A B C D E F G H I J K L M
00 01 02 03 04 05 06 07 08 09 10 11 12 13
N Ñ O P Q R S T U V W X Y Z
14 15 16 17 18 19 20 21 22 23 24 25 26 27
Usando la clave pública RSA (n = 7 · 13, e = 17) se quiere cifrar texto agrupando los caracteres de 2 en 2.
1. Cifra el mensaje BECA.
2. Descifra el mensaje cifrado obtenido anteriormente. ¿Qué es lo que falla?
3. ¿Qué pasaría si el mensaje fuera TAXI?
Respuestas:
1. BECA se cifra en 4,84
2. 4,84 no se descifra en BECA.
3. Con TAXI es todavía peor.
E JERCICIO 34 [1]
Olvido es muy prudente y como tiene mala memoria lleva apuntada su clave RSA en un papelito; el problema
es que un dia de lluvia se le ha mojado y algunos dígitos se han vuelto ilegibles:
n = p · q, p = 1, q = 1
e = 503, d = 4761
Demuestra que Olvido, usando solo los datos anteriores puede encontrar d = 476167, pero no determinar p y
q, excepto buscando n por otros medios (es público) y factorizándolo.
Respuestas: d = 476167, Para p, q hay varias posibilidades, por ejemplo (p = 701, q = 911, λ = 376) o (p =
131, q = 16451, λ = 112)
E JERCICIO 35 [0]
8
Supongamos que se define un criptosistema como RSA pero tomando como módulo un primo n = p muy
grande, en lugar de un producto de dos primos. Indica si este sistema es seguro.
Respuestas: NO
E JERCICIO 36 [0]
Maripuri y dos amigos suyos, Roberto y Pedrín, grandes defensores del uso correcto del idioma, usan habitual-
mente en sus mensajes el criptosistema RSA, cifrando carácter a carácter y utilizando el alfabeto
O A B C D E F G H I J K L M
00 01 02 03 04 05 06 07 08 09 10 11 12 13
N Ñ O P Q R S T U V W X Y Z
14 15 16 17 18 19 20 21 22 23 24 25 26 27
Las claves públicas de Roberto y Pedrín son respectivamente (n R = 55, e R = 49) y (n P = 77, e P = 11).
Un día, Maripuri recibe el siguiente mensaje, que sospecha que es de uno de sus dos amigos y que contiene
una palabra cifrada con la clave pública del remitente:
Hla Maripuri. Ok q ls palbrs d ls novlas d Gbrl Gcia Mrkz t
convkn a 1 mnifa n kontra dl lnguaj rduc!nista d ls sms l sabdo
a ls 4 nfrnt d l sd d l Real Akdmia. Eso es tdo. Sldos. Psalo al
rsto. 23-49-23-1
Deduce de quién procede el mensaje.
Respuestas: Roberto. Mensaje=VIVA
E JERCICIO 37 [0]
Alicia y Benito cifran con RSA usando el alfabeto
A B C D E F G H I J K L M N
00 01 02 03 04 05 06 07 08 09 10 11 12 13
Ñ O P Q R S T U V W X Y Z
14 15 16 17 18 19 20 21 22 23 24 25 26
y acuerdan cifrar agrupando los caracteres de dos en dos y concatenando sus valores numéricos en base 10,
con dos cifras cada uno. Por ejemplo, HOLA se representa como (0715, 1100) = (715, 1100).
La clave pública de Alicia es (n = 391 = 17 · 23, e = 47) y su clave privada es d = 15.
Usando la clave púbica de Alicia, Benito cifra HOLA y le envía su cifrado
HOLA ∼ (715, 1100) se cifra como (71547 mod 391 = 307, 110047 mod 391 = 350)
pero cuando Alicia descifra obtiene
(307, 330) se descifra como (30715 mod 391 = 324, 33015 mod 391 = 318) ∼ DXDR
Si damos por correctas las operaciones aritméticas que han hecho Benito para cifrar y Alicia para descifrar,
indica la explicación más probable para la causa de este mal funcionamiento.
Respuestas: No va bien porque el módulo de la clave es pequeño para esos mensajes.
E JERCICIO 38 [0]
En un criptosistema RSA se cifra carácter a carácter. El mensaje FUMANDOOESPERO se ha cifrado como
185, 187, 229, 12, 108, 102, 129, 223, 103, 87, 207, 103, 233, 129
9
¿Cuál sería el descifrado de 207, 233, 129, 185, 103, 87, 129, 233?
Respuestas: PROFESOR
E JERCICIO 39 [1]
El profesor Otto Rino, experto jefe de seguridad de la República Democrática de Tirania, recomienda al presi-
dente Bruteztrausen que para sus comunicaciones secretas use RSA con las siguientes carácterísticas:
Un módulo n de 2048 bits, producto de dos primos fuertes de 1024 bits cada uno y cuya diferencia sea
mayor que 2512 .
Exponente de cifrado e = 3, para agilizar el cifrado.
Los mensajes son representados como una lista de números, cada uno correspondiente a 64 bits del
mensaje a cifrar.
El experto argumenta que entonces:
1. Es muy difícil que un adversario pueda factorizar el módulo, con lo que no va a poder encontrar el expo-
nente privado de descifrado.
2. El exponente e = 3 hace que el cifrado sea muy rápido.
3. Es prácticamente imposible que un adversario que solo conoce (n, e) pueda descifrar los mensajes.
Estudia la veracidad o falsedad de las anteriores afirmaciones.
Respuestas:
1. Verdadero.
2. Verdadero.
3. Falso.
E JERCICIO 40 [1]
1. Haz una tabla con la factorización de 14n + 11 para 0 ≤ n ≤ 8.
2. A partir de la tabla anterior, haz una conjetura acerca de los divisores de 14n +11 según n sea par o impar.
3. Demuestra que si n ≥ 0, entonces 14n + 11 no puede ser primo.
Respuestas:
2 Parece que si n es par 14n + 11 es múltiplo de 3 y si n es impar, es múltiplo de 5.
3 Siempre es múltiplo de 3 o de 5.
E JERCICIO 41 [1]
1. Demuestra que si x es cuadrado perfecto, entonces x mod 4 es 0 o 1.
2. Demuestra que si p es primo, entonces 2p + 3p no es cuadrado perfecto.
Respuestas:
10
2 Usa el apartado anterior distinguiendo p = 2 y p > 2.
E JERCICIO 42 [0]
Demuestra que 55552222 + 22225555 es múltiplo de 7.
Respuestas: Trabaja en Z7 y usa MC.
E JERCICIO 43
Encuentra un número de lotería de cinco cifras con las cinco cifras distintas y que, además si numeramos los
meses del año del 1 al 12, en cualquier mes del año ocurre que al restar a nuestro número de lotería el número
del mes anterior, el resultado es divisible por el número del mes en el que estemos. Y esto sucede para cada
uno de los meses del año.
Respuestas: 83159
E JERCICIO 44 [1]
En este ejercicio se estudia una sucesión de enteros a 1 , a 2 , . . . tal que para todo n, a 12 +a 22 +· · ·+a n2 es un cuadrado
perfecto. Para ello consideramos dos sucesiones paralelas:
1 1
a1 = 3 a2 = 2 (s 1 − 1) ... a n+1 = 2 (s n − 1) ...
2
s1 = 3 s2 = s 1 + a 22 ... s n+1 = 2
s n + a n+1 ...
1. Demuestra que para todo n, s n ≡ 1 (mod 4). Deduce de aquí que las sucesiones de enteros a i y s i están
bien definidas y que todos los s i son impares.
2. Demuestra que para todo n, s n = a 12 + a 22 + · · · + a n2 es cuadrado perfecto.
Respuestas: Usa inducción.
E JERCICIO 45 [0]
Encuentra tres enteros n − 2, n, n + 2 tales que la expresión decimal de la suma de sus cuadrados consista en
cuatro dígitos iguales.
Respuestas: 41, 43 y 45.
2. Ejercicios avanzados
E JERCICIO 46 [2]
Demuestra las afirmaciones siguientes:
1. Si n = p es primo entonces todos los números p1 , p2 , . . . , p−1
¡ ¢¡ ¢ ¡ p ¢
son múltiplos de p.
2. Si n tiene un factor primo p < n, entonces np no es múltiplo de n. Deduce que la condición anterior es
¡ ¢
necesaria y suficiente para que n sea primo.
3. Si p es primo, entonces en Zp se verifica que (x + y)p = x p + y p .
E JERCICIO 47 [2]
11
1. Demuestra que si p es un primo distinto de 2 y 5, existe un entero múltiplo de p cuya expresión decimal
está formada solo por unos.
2. ¿Puedes generalizar lo anterior a cualquier base de numeración?
Respuestas: Considera la sucesión de restos 1 mod p, 11 mod p, 111 mod p, . . .
E JERCICIO 48 [2]
© ª
Sean a y b enteros positivos primos entre sí y llamamos U a = {x 1 , . . . , x m } ,Ub = y 1 , . . . , y n y U ab = {z 1 , . . . , z r } a
los conjuntos de unidades en Za , Zb y Zab , respectivamente. Usando el Teorema Chino de los Restos demues-
tra que la aplicación
f : U ab −→ U a ×Ub , f (z) = (z mod a, z mod b)
está bien definida y es biyectiva. Deduce de aquí que si a y b son enteros positivos primos entre sí, entonces
φ(ab) = φ(a)φ(b).
E JERCICIO 49 [2]
p
Demuestra que si p > 2 es primo, entonces p − 1 > p.
p
Demuestra que para todo entero n > 2, se verifica 21 n < φ(n) < n.
E JERCICIO 50 [2]
1. Demuestra que si k ≥ 1 entonces k − 12 ≥ k2 .
1
2. Demuestra que si p ≥ 3 entonces p − 1 > p 2 .
p
3. Demuestra que si p es primo impar, k ≥ 1 y n = p k entonces φ(n) > n.
p
4. Demuestra que para todo n impar, φ(n) > n.
p
5. Demuestra que para todo n par, φ(n) > 12 n.
E JERCICIO 51 [2]
Los códigos de cuenta corriente (CCC) consisten en una cadena de 20 dígitos:
b 1 b 2 b 3 b 4 s 1 s 2 s 3 s 4 d 1 d 2 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c 10
Banco Sucursal Control Nºde cuenta
Los dígitos de control son una especie de resumen de los restantes datos de la cuenta y se usan para detectar
pequeños errores (algo así como la letra del DNI) y se calculan como sigue:
d 1 = (−(4b 1 + 8b 2 + 5b 3 + 10b 4 + 9s 1 + 7s 2 + 3s 3 + 6s 4 ) mod 11) mod 9
d 2 = (−(c 1 + 2c 2 + 4c 3 + 8c 4 + 5c 5 + 10c 6 + 9c 7 + 7c 8 + 3c 9 + 6c 10 ) mod 11) mod 9
Demuestra que es fácil modificar un CCC, por ejemplo alterando solo c 7 y c 8 , sin que el cambio sea detectado
por los dígitos de control.
E JERCICIO 52 [2]
1. Tres amigos, Alicia, Bernardo y Carlos, cifran con RSA y tienen como claves (377, 3), (391, 3) y (589, 3) res-
pectivamente (el mismo exponente y distinto módulo). Alicia, la experta, justifica el exponente e = 3
porque así las operaciones de cifrado son muy rápidas. Eva, que desea perjudicarlos, se ha dado cuenta
de que los módulos son primos entre sí dos a dos y ha interceptado 330, 34, 419, que son los cifrados de
un mismo mensaje m dirigido a los tres. Indica cómo puede Eva usar el Teorema Chino de los Restos para
encontrar m.
12
2. Tras darse cuenta del problema, Alicia propone a sus amigos cambiar a módulos mayores y dice que se
puede seguir usando un mismo exponente, pero mucho más grande: sugiere tomar como e un número de
Fermat, concretamente e = 216 + 1. Alicia mantiene que entonces el ataque anterior se ha vuelto inviable
aunque la operación de cifrado sigue siendo muy eficiente. Razona si Alicia tiene razón y por qué.
E JERCICIO 53 [2]
1. Demuestra que si d 1 , d 2 , d 3 son enteros, entonces d 1 · d 2 · d 3 · (d 2 − d 1 ) · (d 3 − d 1 ) · (d 3 − d 2 ) es divisible por
3 y por 4.
2. Demuestra que si a 0 , a 1 , a 2 , a 3 son enteros, entonces el producto de todas sus diferencias dos a dos es
múltiplo de 144.
3. Si el enunciado no diera antes como pista el apartado 1, ¿cómo llegarías a que primero hay que probar
ese apartado?
13
