3º Boletín Aritmética Modular (Resuelto) PDF

Preview

Summary

Download 3º Boletín Aritmética Modular (Resuelto) PDF

Description

Ingeniería Informática I NTRODUCCIÓN A L A 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). E JERCICIO 2 [0] Halla todas las soluciones de la ecuación 91x ≡ 419 (mod 440). E JERCICIO 3 [0] Halla la solución general de la ecuación 54x ≡ 342 (mod 23400). E JERCICIO 4 [0] Resuelve las siguientes ecuaciones: 1. 225x ≡ 18 (mod 31315). 2. 1235x ≡ 65 (mod 25948). 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) 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. E JERCICIO 7 [0] 1. Prueba que si a m ≡ 1 (mod n) con m ∈ 2. Si a no es una unidad en

26

y m ≥ 2, entonces mcd (a,n) = 1.

y a 10 ≡ 10 (mod 26), entonces ¿cuánto vale mcd(a,26)?

E JERCICIO 8 [0] Resuelve los siguientes sistemas de ecuaciones en congruencias:

a)

 x ≡ 1 (mod 4)  x ≡ 2 (mod 3)   x ≡ 3 (mod 5)

d)

 x ≡ 13 (mod 40)   x ≡ 5 (mod 44)   x ≡ 38 (mod 275)

b)

 x ≡ 2 (mod 7)   x ≡ 7 (mod 9)   x ≡ 3 (mod 4)

e)

 2x ≡ 2 (mod 12)   x ≡ 5 (mod 14)   x ≡ 4 (mod 21)

1

c)

f)

 3x ≡ 6 (mod 12)   2x ≡ 5 (mod 7)   3x ≡ 1 (mod 5) 5x ≡ 5 (mod 6)

3x ≡ 2 (mod 14)

x ≡ −2 (mod 21)

    

E JERCICIO 9 [1] Dado el sistema

x ≡4

x ≡α

x ≡ −1

 (mod 8)   (mod 6)   (mod 15)

1. Determina todos los posibles valores de α ∈ para los que el sistema tiene solución. 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. 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? 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). 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? E JERCICIO 13 [1] Laura trabaja cuatro días seguidos y descansa al quinto. María trabaja dos y descansa al tercero. 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? 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 1 2 3

accede por primera vez al recurso 10:00 horas 10:02 horas c minutos después de las 10 horas

2

accede cada 5 minutos 12 minutos 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≡

x≡

x≡

 0 ( mod 5)   2 ( mod 12)   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?

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? 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. E JERCICIO 18 [0] Utiliza el teorema de Fermat para calcular los restos de dividir: 1. 528574 entre 17. 2. 35346 entre 41. 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. E JERCICIO 20 [0] Demuestra que si p, p + 2, p + 4 son primos, entonces p = 3. 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

n.

E JERCICIO 22 [1] 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

3

n = n 1 n 2 · . . . · n k , entonces el sistema

 x ≡ b1 (mod n 1 )     x ≡ b (mod n )  2

2

...

tiene como solución en

     x ≡ bk (mod n k )

n:

x = a1 (n /n 1 )φ(n1 ) + . . . + ak (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

n

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 ). 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 T

1 R

2 W

3 A

4 G

5 M

6 Y

7 F

8 P

9 D

10 X

12 N

13 J

14 Z

15 S

16 Q

17 V

18 H

19 L

20 C

21 K

22 E

11 B

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: 2835051 − 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. E JERCICIO 29 [0] Queremos cifrar mensajes mediante RSA usando el alfabeto

O 00

A 01

B 02

C 03

D 04

E 05

4

I 06

Ñ 07

O 08

S 09

T 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. 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 . E JERCICIO 31 [0] Sabiendo que n = p · q, producto de dos primos y que φ(n) = 24, halla los posibles valores de n . 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

14

15

16

17

18

19

20

21

22

23

24

25

Y 26

Z 27

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

14

15

16

17

18

19

20

21

22

23

24

25

Y 26

Z 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? 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. E JERCICIO 35 [0] 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. E JERCICIO 36 [0] Maripuri y dos amigos suyos, Roberto y Pedrín, grandes defensores del uso correcto del idioma, usan habitualmente en sus mensajes el criptosistema RSA, cifrando carácter a carácter y utilizando el alfabeto 5

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

14

15

16

17

18

19

20

21

22

23

24

25

Y 26

Z 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) no son claves del todo correctas, porque los factores primos del módulo no son primos con todos los mensajes, pero no haremos caso de esto, para permitir números pequeños y operaciones fáciles. Un día, Maripuri recibe el siguiente mensaje, que sospecha que es de uno de sus dos amigos y que contiene una palabra cifrada:

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

14

15

16

17

18

19

20

21

22

23

24

25

Z 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. 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 ¿Cuál sería el descifrado de 207, 233,129, 185,103, 87,129, 233? E JERCICIO 39 [1] El profesor Otto Rino, experto jefe de seguridad de la República Democrática de Tirania, recomienda al presidente 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 exponente privado de descifrado. 6

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. 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. 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. E JERCICIO 42 [0] Demuestra que 55552222 + 22225555 es múltiplo de 7. 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. E JERCICIO 44 [1] En este ejercicio se estudia una sucesión de enteros a1 , a2 , . . . tal que para todo n, a12+a22+·· ·+a 2n es un cuadrado perfecto. Para ello consideramos dos sucesiones paralelas: a1 s1

= =

3 2

3

a2

=

s2

=

1 (s − 1) 2 1 s1 + a 22

.. .

an+1

=

.. .

sn+1

=

1 (s − 1) 2 n 2 sn + an+1

.. . .. .

1. Demuestra que para todo n, sn ≡ 1 (mod 4). Deduce de aquí que las sucesiones de enteros ai y si están bien definidas y que todos los si son impares. 2. Demuestra que para todo n, sn = a12+ a22 + · ·· + a 2n es cuadrado perfecto. 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.

2. Ejercicios avanzados E JERCICIO 46 [2] Demuestra las afirmaciones siguientes: ¡ p ¢ ¡ ¢ ¡p ¢ 1. Si n = p es primo entonces todos los números 1p , 2 ,. . . , p−1 son múltiplos de p . ¡¢ 2. Si n tiene un factor primo p < n, entonces pn 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

p

se verifica que (x + y)p = x p + y p . 7

E JERCICIO 47 [2] 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? 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 = {z1 ,. . . , zr } a los conjuntos de unidades en a , b y ab , respectivamente. Usando el Teorema Chino de los Restos demuestra 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 . 1p Demuestra que para todo entero n > 2, se verifica 2 n < φ(n) < n. E JERCICIO 50 [2] 1. Demuestra que si k ≥ 1 entonces k − 21 ≥ k2 . 1

2. Demuestra que si p ≥ 3 entonces p − 1 > p2 . 3. Demue...