·

Sistemas de Informação ·

Matemática Discreta

· 2023/1

Send your question to AI and receive an answer instantly

Ask Question

Preview text

10 exercícios da apostila ‘Criptografia de S.C.Coutinho’ Exercício 38. Na encenação de uma batalha, duas tropas se enfrentam, posicionando-se, atirando com festim, e recarregando seus mosquetes, cada uma a sua vez. Cada lado começa com o mesmo número de cartuchos. Uma tropa tem 100 mosquetes e, depois de atirar tantos tiros de festim quanto possíveis, lhe sobram 13 cartuchos. A outra tropa tem 67 mosquetes, e ao fim da exibição, sobram-lhe 32 cartuchos. Supondo que a cada salva de tiros todos os soldados de cada lado atiraram exatamente uma vez, determine o número mínimo de cartuchos com que cada tropa iniciou a exibição. Exercício 42. Calcule o resto da divisão por 31 das potências 2⁶⁵⁵⁶⁴²³ e 2⁷⁹⁸⁷⁶⁶⁸. Exercício 43. Calcule o resto da divisão por 31 das potências 2¹⁵⁴⁹⁸⁷⁶⁶⁵⁴³³³⁵²³¹ e 6⁴³⁹⁸⁷⁶. Exercício 50. Calcule o resto da divisão de 3⁹⁸⁷⁴⁵ por 43 usando o Teorema de Fermat. Exercício 52. Calcule o resto da divisão de 31! por 307. Exercício 53. Calcule o resto da divisão de 1ᵖ⁻¹ + 2ᵖ⁻¹ + ⋯ + (p - 1)ᵖ⁻¹ por p, sabendo-se apenas que p > 2 é primo. Exercício 54. Calcule o resto da divisão de (a) 2⁴⁹⁵ por 15841; Exercício 57. Decodifique os demais blocos da mensagem 34 - 129 - 228 - 37 - 105 - 44 - 386 - 125, usando o procedimento acima. Lista de Exercícios Cálculo 3 Problema 1 Resposta Vamos observar quem é (n − 1)2 módulo n. Primeiro note que (n − 1)2 = n2 − 2n + 1 ≡ n2 + 1 mod n Claramente 2n ≡ 0 mod n, portanto temos a simplificação acima. Por outro lado, temos que n2 + 1 ≡ 1 mod n, pois n2 ≡ 0 mod n e assim fica claro que n − 1 é seu próprio inverso módulo n. Problema 2 Resposta 1. O inverso de 2 é 3k + 1, pois 2 · (3k + 1) = 6k + 2 ≡ (6k + 1) + 1 ≡ 1 mod 6k + 1 2. O inverso de 3 é 4k + 1, pois 3 · (4k + 1) = 12k + 3 ≡ 2(6k + 1) + 1 ≡ 1 mod 6k + 1 3. O inverso de 6 é 5k + 1, pois 6 · (5k + 1) = 5(6k + 1) + 1 ≡ 1 mod 6k + 1 Problema 3 Resposta Problema 4 Resposta Aqui vamos usar o teorema de Fermat: sendo p primo e p ∤ a, temos que a30 ≡ 1 mod 31. Assim: 26556426 = 230·218547+16 ≡ (230)218547 · 216 mod 31 Assim 216 ≡ (25)3 · 2 mod 31 ⇒ 216 ≡ (32)3 · 2 mod 31 ⇒ 216 ≡ 2 mod 31 Usando as mesmas propriedades 27987668 = (230)266255 · 218 ≡ 218 mod 31 1 27987668 ≡ 218 ≡ (25)3 · 23 mod 31 Assim temos 27987668 ≡ 8 mod 31. Problema 5 Resposta 1. Observe a aplicação de Fermat a relação 21445231 ≡ 230·q+20 ≡ (25)4 ≡ 1 mod 31 Precisamos observar que, pelo teorema de Euler, vale 1445231 ≡ (1429)1559 · 1420 mod 30 2. Observe a aplicação de Fermat a relação 215498766543335231 ≡ 230·q+15 ≡ (2)15 ≡ 1 mod 31 Precisamos observar que, pelo teorema de Euler, vale 15498766543335231 ≡ (1529)p · 1515 ≡ (152)7 · 15 ≡ 15 mod 30 3. Primeiro note que 26 ≡ 2 mod 31. Assim sendo temos que 239876 ≡ 230q+21 ≡ (25)4 · 2 ≡ 2 mod 31 temos que (329)340 · 316 ≡ 316 ≡ (35)3 · 3 mod 31 (329)340 · 316 ≡ 33 · 3 ≡ 21 mod 30 2