Examen de Álgebra UDL 2021 · segon parcial gener 2021

Problema 1 (3 punts). Equació diofàntica lineal

Resoleu la següent equació diofàntica:

$$195x + 42y = 12$$

a)

$\operatorname{mcd}(195, 42) =$

b)

$x_0 =$

$y_0 =$

c)

$x(k) =$

$y(k) =$

, amb $k \in \mathbb{Z}$

Problema 2 (7 punts). Criptosistema simètric i aritmètica modular

L'Anna i la Berta han dissenyat un criptosistema simètric que opera d'acord amb el procediment següent:

Acorden dos nombres secrets $n$ i $s$ de manera que $s \in \mathbb{Z}_n^*$. Aquesta parella constituirà la clau compartida que coneixen ambdues.

L'Anna tria un missatge secret $m \in \mathbb{Z}_n$, el qual és el codi d'accés a un portal web.

L'Anna transmet a la Berta el criptograma $c$, obtingut mitjançant l'operació $c \equiv m \cdot s \pmod n$.

Contesteu de manera raonada cadascuna de les qüestions:

a)

$\phi(720) =$

b)

Suposeu que escullen les claus $n = 720$ i $s = 13$. La Berta rep el criptograma $c = 216$.

$m =$

c)

Prenent ara $m = 74$ i $n = 720$, calculeu $m' \equiv m^{1999} \pmod n$.

$m' =$