ALGEBRA E LOGICA (Pareschi e Schoof) 1^{o} appello Roma 2 maggio 2002, 14:00–15:45.

COGNOME . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NOME . . . . . . . . . . . . . . . . . . . . . . . .

Inserire le risposte negli spazi predisposti, accompagnandole con spiegazioni chiare ed essenziali. NON SI ACCETTANO RISPOSTE SCRITTE SU ALTRI FOGLI. Ogni esercizio vale 5 punti.

1. Sia n = 77 il modulo di un sistema crittografico RSA. Sia D = 13 l’esponente segreto. Determinare un esponente E ∈ Z tale che (x^{D})^{E} ≡ x (mod n) per il messaggio x = 4.

Abbiamo che n = p · q con p = 7 e q = 11. Siccome (p − 1)(q − 1) = 60, ogni esponente E > 0 che soddisfa DE = 13E ≡ 1 (mod 60) va bene. Tale esponente si trova calcolando il mcd di 13 e 60. Si trova che 37 · 13 ≡ 1 (mod 60) e possiamo prendere E = 37.

2. Trovare tutte le soluzioni x ∈ Z del sistema di congruenze \{ \begin{matrix}x ≡ 2 (mod 5); \\ x ≡ 3 (mod 4); \\ x ≡ 4 (mod 11). \end{matrix}

Applicando il Teorema Cinese del Resto, si trova che x ≡ 147 (mod 220).

3. Determinare quanti sono i numeri 0 ≤ n < 2000 le cui cifre hanno somma uguale a 8.

Ogni numero con questa proprietà ha tre cifre o ha la prima cifra uguale a 1. Ci sono \binom{8+3−1}{8} = \binom{10}{2} numeri del primo tipo e \binom{7+3−1}{7} = \binom{9}{2} del secondo. Ci sono quindi \binom{10}{2} + \binom{9}{2} = 81 numeri con la proprietà richiesta.

4. Sia A = {a, b, c, d, e}. Determinare la chiusura transitiva della relazione R che consiste nelle coppie (a, b), (a, e), (b, c), (c, d), (d, b).

La matrice A associata alla relazione e le sue “potenze” A^{[2]} e A^{[3]} sono

A = ( \begin{matrix}0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) ,  A^{[2]} = ( \begin{matrix}0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) ,  A^{[3]} = ( \begin{matrix}0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) .

Siccome le matrici A^{[4]} e A^{[5]} contengono solo ripetizioni, la chiusura transitiva di R è l’unione di R e l’insieme {(a, c), (b, d), (c, b), (d, c), (a, d), (b, b), (c, c), (d, d)}.

5. Siano x, y variabili booleane. L’operatore NAND è definito da x NAND y = \overline{(xy)}. Usando solo porte NAND costruire un circuito con input x e y e output \overline{x} e x + y.

Abbiamo che \overline{x} = x NAND x e xy = \overline{\overline{(xy)}} = \overline{(xy)} NAND \overline{(xy)} = (x NAND y) NAND (x NAND y).

6. I grafi.

Il grafo “cubo” Q_{3} è bipartito. Nelle altre versioni del compito, i due grafi sono sempre isomorfi, eccetto nel caso dei due grafi “ottagonali”. Essi non sono isomorfi perché un grafo contiene un vertice di grado 2 con due vertici vicini di grado 3, ma l’altro no.