Buscar

Prova-3-2009-1-Numeros-Inteiros-e-Criptografia-Severino-Collier-Coutinho (1)

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.

Outros materiais

Materiais relacionados

Perguntas relacionadas

Perguntas Recentes