Criptografia

2ª Avaliação à Distância de Criptografia-2-2012
1) (2,0pts) Sejam p um número primo positivo e r e k ∈ N ∗ (conjunto dos números naturais sem o zero). Mostre que mdc (r, pk ) = 1 se e só se p não divide r.
2) (2,5pts)Considere o conjunto (Z/mZ)*, definido por:
(Z/mZ)* = {k ∈ Z  0 ≤ k < m e mdc (k, m) = 1}
Seja a função φ : N → N é definida por

φ (m) = # (Z/mZ)* = # {k ∈ Z  0 ≤ k < m e mdc (k, m) = 1},
# (Z/mZ)* significar o número de elementos do conjunto (Z/mZ)*.
a) (1,5pts) Use o exercício anterior para mostrar que se p é um primo positivo e k ∈ N ∗ então φ (pk) = pk – pk–1 = pk (1–1/p).
b) (1,0pt) Calcule φ (3125).
3) (1,0pt)Use os conceitos aprendidos sobre os conjuntos Z n e construa uma tabela para a operação potência quadrada (m² = m.m) em Z11 .
4) (1,0pt) Considerando a raiz quadrada de um número em Z n como sendo a operação inversa a potência quadrada. Determine em Z11 a(s) raiz(es) quadrada(s) de 3.
5) (2,0pts) Um método criptográfico conhecido é o Método de Rabin, devido a Michael
Rabin. Neste método, se n é um inteiro muito grande, a função codificadora C é definida por: C ( M ) = M 2 mod n
Isto equivale a dizer que C(M) = x, 0 ≤ x < n e M 2 ≡ x (mod n)

A função decodificadora E inversa de C, é tal que E[C(M)] = M.
a) (1,0pt) Calcule C(28) e C(31) para n = 59,
b) (1,0pt) Responda justificando: No Método criptográfico de Rabin a escolha do n pode ser aleatória? Isto é, a escolha de n não influencia o funcionamento do método? 6) (1,5pts) Use a Segunda versão do Teorema de Fermat para calcular o resto da divisão de 3200 por 13.