Teste 2
Matemática Discreta LEIC 2007/2008

50 minutos
Enunciado A
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
               5 x -5(Subscript[=, 11])3
               4x +3(Subscript[=, 5])6.

5 x -5(Subscript[=, 11])3  ⇔  5x (Subscript[=, 11])8  ⇔  45x (Subscript[=, 11])72  ⇔  x (Subscript[=, 11])6  
               4x +3(Subscript[=, 5])6         4x(Subscript[=, 5])3            16x(Subscript[=, 5])12         x (Subscript[=, 5])2   
               
               o que, sendo mdc(5,11)=1, tem pelo teorema chinês dos restos as soluções x+k.55 com k inteiro e 
               
               x = (6×5×((5^(-1)) mod 11)+2×11×((11^(-1)) mod 5)) mod 55= (30×9+22×1) mod 55 = 292 mod 55 = 17
               
               pois tem-se

(5^(-1))=-2=9mod 11      já que (-2)×5+1×11=1
(4^(-1))=-1=4mod 5      já que (-1)×4+1×5=1
(11^(-1))=1mod 5      já que (-2)×5+1×11=1

Grupo II (1,5 val)

Considere um sistema criptográfico RSA com n = p × q, p = 3 e q = 29. 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.

Precisamos que a*b = 1 mod (p - 1) (q - 1) i.e. a*b = 1 mod 56
Escolhendo por exemplo a = 5 (já que mdc(5,56)=1) vamos ter b = 45 pois 1×56+(-11)×5=1 e portanto b=(a^(-1))mod 56=-11=45.

Dessa forma tem-se u(2)=(2^5)mod 87=32.
Decifrando, tem-se v(32)=(32^45)mod 87=32*((((32^2)))^22)mod 87=32*(67^22)mod 87=32*((((67^2)))^11)mod 87=32*(52^11)mod 87=32*52*((((52^2)))^5)mod 87=11*(7^5)mod 87=11*7*(49^2) mod 87=77*52 mod 87=4004 mod 87=2 mod 87.

Cálculos auxiliares:
32*32=1024=67 mod 87
67*67=4489=52 mod 87
32*52=1664=11 mod 87
52*52=2704=7 mod 87
49*49=2401=52 mod 87

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(n-m,m) se n-m < m
euclides(m,n) = euclides(m,n-m) caso contrário

(a) Demonstre que para x,y ∈ N com x<y se tem euclides(x,y) = mdc(x,y).

Claramente, mdc(0,y)=y.
Se 0<x<y e y-x<x então basta verificar que d|x e d|y se e só se d|y-x e d|x.

Da esquerda para a direita, x=kd e y=jd pelo que y-x=jd-kd=(j-k)d.
Da direita para a esquerda, y-x=kd e x=jd pelo que y=y-x+x=kd+jd=(k+j)d.

O último caso é análogo.

Resta notar que a definição é tal que a primeira projecção do par de valores com o qual se invoca o algoritmo diminui em cada iteração, mantendo-se sempre não-negativa, pelo que se chegará necessariamente a uma expressão do tipo euclides(0,n).

(b) Usando este algoritmo, confirme que mdc(30,84) = 6.

Tem-se euclides(30,84)=euclides(30,54)=euclides(24,30)=euclides(6,24)=euclides(6,18)=euclides(6,12)=euclides(6,6)=euclides(0,6)=6.

(c) Proponha uma versão estendida do algoritmo que permita calcular c,d ∈ Z tais que cx+dy = mdc(x,y).
                       
estendido(0,n)=(0,1)

estendido(m,n)=(d-c,c) se estendido(n-m,m)=(c,d) e n-m<m 
	(pois c(n-m)+dm=cn-cm+dm=(d-c)m+cn)

estendido(m,n)=(c-d,d) se estendido(m,n-m)=(c,d) e n-m≥m 
	(pois cm+d(n-m)=cm+dn-dm=(c-d)m+dn)