PROGRAMMA DI MATEMATICA DISCRETA II (A.A. 2007/08) (Prof. Fabio Di Franco)
Insiemi dotati di operazione, semigruppi, gruppi, monoidi. Operazioni fra classi di congruenza.
Numeri di Fibonacci e complessità dell’algoritmo Euclideo. Sottogruppi di un gruppo e relativo criterio. Congruenza modulo un sottogruppo e Teorema di Lagrange. Potenze di un elemento di un gruppo e sottogruppo ciclico generato da un elemento. Teorema di Eulero-Fermat e Piccolo teorema di Fermat. Sistemi crittografici: il sistema RSA. Algoritmo dell’esponenziazione modulare. Test di primalità deterministici e probabilistici: il test di Rabin-Miller. Gruppi ciclici e generatori. Anelli, corpi, campi. Anelli di polinomi e Teorema di Ruffini. Gruppo moltiplicativo ciclico di un campo finito: il problema del logaritmo discreto. Algoritmo di Gauss. Sistema di ElGamal e scambio di chiavi di Diffie-Hellman. Algoritmo per le radici ennesime. Algoritmi di fattorizzazione: l’algoritmo di Fermat e l’algoritmo di Pollard. Teoria dei codici: codici perfetti, codici lineari, codici di Hamming, decodifica di un codice. Disegni, 2-disegni, piani proiettivi. Quadrati latini.
Libri di testo:
Appunti del corso (disponibili online)
Alberto Facchini “Algebra e Matematica Discreta” Ed. Decibel-Zanichelli
