Teste 2
Matemática Discreta LEIC 2007/2008

50 minutos
Enunciado H
Não é permitido o uso de máquina de calcular nem de qualquer  tipo de consulta.

Grupo I (2  val)

Determine todas as soluções em Z do seguinte sistema de equações
               3 x +4(Subscript[=, 7])-2
               2x -4(Subscript[=, 9])3.

Grupo II (1,5 val)

Considere um sistema criptográfico RSA com n = p × q, p = 23 e q = 3. Determine um par de chaves a e b, chave pública e chave privada, respectivamente, tal que a≠1. Para estes valores de a e b, ilustre o funcionamento do sistema calculando a mensagem codificada correspondente à mensagem x = 2 e indicando os cálculos correspondentes à descodificação da mensagem codificada.

Grupo III (1+0,5+0,5 val)

Considere a seguinte versão (mais lenta) do algoritmo de Euclides.

euclides(0,n) = n
euclides(m,n) = euclides(m,n-m) se m < n-m
euclides(m,n) = euclides(n-m,m) caso contrário

(a) Demonstre que para x,y ∈ N com x ≤ y se tem euclides(x,y) = mdc(x,y).
(b) Usando este algoritmo, confirme que mdc(90,105) = 15.
(c) Proponha uma versão estendida do algoritmo que permita calcular c,d ∈ Z tais que cx+dy = mdc(x,y).