Baixe o app para aproveitar ainda mais
Prévia do material em texto
DCC-UFRJ–Números inteiros e criptografia–Terceira Prova–2009/1 Nome: Justifique cuidadosamente as suas respostas. 1. Seja p > 2100 um número primo tal que 2p+1 também é primo. Use o teorema de Fermat para calcular a ordem de 9 módulo 2p+ 1. Sugestão: aplique Fermat à base 3. 2. Seja p > 2100 um número primo tal que 2p + 1 também é primo. Prove que 3p(2p+ 1) não pode ser um número de Carmichael. 3. Seja n = 13981 = 11 · 31 · 41. 4. Seja n = 13981 = 11 · 31 · 41. Calcule o resto da divisão de 23495 por n pelo algoritmo chinês do resto e use isto para determinar se n é pseudoprimo forte e/ou fraco para a base 2. Resolução 1. Pelo teorema de Fermat, 32p ≡ 1 (mod 2p+ 1), pois 2p+ 1 é um primo maior que 3. Mas, 32p ≡ 9p (mod 2p+ 1). Portanto, 9p ≡ 1 (mod 2p+ 1), Disto e do Lema Chave, temos que a ordem de 9 módulo 2p + 1 tem que dividir p. Como p é primo, 9 tem que ter ordem 1 ou p módulo 2p + 1. Contudo, se a ordem fosse um teríamos 9 ≡ 1 (mod 2p+ 1), de modo que 2p + 1 teria que dividir 8, o que é obviamente falso. 9 tem ordem p módulo 2p+ 1. 2. Se 3p(2p+ 1) fosse Carmichael, teríamos que 3p(2p+ 1) ≡ 9 (mod p− 1) pois p ≡ 1 (mod p− 1). Como p > 2100 não é possível que isto ocorra. Portanto, 3p(2p+ 1) não pode ser um número de Carmichael. 3(a). Pelo teorema de Fermat 210 ≡ (mod 11) 230 ≡ (mod 31) 240 ≡ (mod 41) Como n = 13981 = 11 · 31 · 41, e 3495 ≡ 5 (mod 10) 3495 ≡ 15 (mod 30) 3495 ≡ 15 (mod 40). Portanto, 23495 ≡ 25 ≡ −1 ≡ 10 (mod 11) 23495 ≡ 215 ≡ (25)3 ≡ 1 (mod 31) 23495 ≡ 215 ≡ (25)3 ≡ (−9)3 ≡ 9 (mod 41). Logo, se r for o resto de 23495 por n teremos que r ≡ 10 (mod 11) r ≡ 1 (mod 31) r ≡ 9 (mod 41). Resolvendo pelo algoritmo chinês do resto, tiramos o valor de r da última congruência, r = 9 + 41t, e substituímos na segunda, 9 + 41t ≡ 1 (mod 31), donde 10t ≡ −8 (mod 31). Multiplicando por 3: 30t ≡ −24 (mod 31); donde −t ≡ −24 (mod 31); que equivale a t ≡ 24 (mod 31). Assim, t = 24 + 31y. Substituindo em r, r = 993 + 31 · 41y. Levando isto à primeira congruência, obtemos 993 + 31 · 41y ≡ 10 (mod 11); isto é, 3− 5y ≡ 10 (mod 11). Assim, 6y ≡ 7 (mod 11). Multiplicando tudo por 2; y ≡ 3 (mod 11). Logo, y = 3 + 11z, donde, r = 4806 + nz. Para aplicar o teste de composição forte, escrevemos n− 1 = 22 · 3495. Como 23495 ≡ 4806 6≡ 1, n− 1 (mod n), e como 22·3495 ≡ (4806)2 ≡ 1024 6≡ n− 1 (mod n), concluímos que n não é pseudoprimo forte para a base 2. Por outro lado, 2n−1 ≡ 24·3495 ≡ (1204)2 ≡ 1 6≡ n− 1 (mod n), de modo que n é um pseudoprimo para a base 2.
Compartilhar