- Concrete abstract algebra
Niels Lauritzen
Cambridge University Press
- Ling-Xing,
Coding Theory: a first course,
Cambridge Univ. Press, 2004
Obiettivi Formativi
Acquisizione delle necessarie competenze, di argomenti di algebra di base, per affrontare testi e articoli di crittografia
e teoria dei codici. Acquisizione, nell'ambito della teoria dei codici, delle competenze necessarie
per affrontare la letteratura, anche recente, sull'argomento.
Prerequisiti
Nozioni di base di algebra lineare, nel programma del corso di primo anno.
Metodi Didattici
Lezioni ed esercitazioni in aula.
Modalità di verifica apprendimento
Esame orale
Programma del corso
Definizioni di gruppo, gruppo abeliano, anello, anello commutativo, campo.
Divisione con resto (teorema s.d.).
Congruenze: congruenza modulo un intero positivo d, definizione e prime proprieta'.
Algoritmo dei quadrati ripetuti.
Massimo comun divisore: esistenza e unicita'.
Algoritmo Euclideo per determinare il massimo comun divisore tra due interi.
Algoritmo Euclideo esteso.
Proprieta' del massimo comun divisore.
Teorema cinese dei resti.
Definizione della funzione φ di Eulero sui naturali.
Teorema di Eulero.
Ogni intero positivo si fattorizza in modo unico come prodotto di numeri primi (s.d.).
Calcolo della funzione di Eulero nota la fattorizzazione
Sistema criptografico RSA--sistema di crittografia a chiave pubblica--per la trasmissione di dati.
Anello delle classi di resto modulo n.
Z/nZ e' un campo se e solo se n e' primo.
Polinomi: anello dei polinomi a coefficienti in un anello, in un campo. Grado. In K[x], con K campo, deg(fg)=deg(f)+deg(g). Gli elementi invertibili di k[x] sono le costanti.
Divisione tra polinomi f e d.
Radice di un polinomio.
Molteplicita' di una radice. Fattorizzazione di un polinomio quando sono note le sue radici.
Derivata Df di un polinomio f e sue proprieta'.
Radici n-esime di 1 nel campo complesso. Radici primitive e loro proprieta'.
Definizione per ogni n naturale ≥ 1, del polinomio ciclotomico Φ_n.
Proprieta' fondamentali dei polinomi ciclotomici.
Caratteristica di un campo k.
I polinomi ciclotomici in un campo K. Definizione di radice n-esima primitiva di 1 in K e sue proprieta'.
Sia G un gruppo. Ordine di un elemento g in G. Sia G un gruppo finito con N elementi, allora l'ordine di ogni elemento g di G divide N. Definizione di gruppo ciclico.
Teorema di Gauss: Sia K un campo e sia G un sottogruppo finito del gruppo moltiplicativo K*, allora G e' ciclico.
Definizione di anello quoziente A/I, con A anello e I ideale.
A/I e' un campo, con A anello e I ideale, se e solo se I e' massimale.
Gli anelli Z e K[x] (K campo) sono anelli a ideali principali. Definizione di omorfismo di anelli. Se f da A a B e' un omorfismo di anelli allora la mappa indotta da A/ker(f) a B e' un omorfismo di anelli iniettivo.
Esempi di campi costruiti come quozienti.
Teorema: ogni campo finito di caratteristica p e' isomorfo a un quoziente dell'anello dei polinomi
a coefficienti in F_p per l'ideale generato da un polinomio irriducibile di grado n.
Teorema di esistenza e unicita' per campi finiti.
Teorema: Il polinomio X^(p^n-1)-X in F_p e' il prodotto DEI polinomi monici irriducibili di F_p di grado d, con 0≤ d ≤ n e d che divide n.
Corollario: formula per il numero dei polinomi monici irriducibili di grado d in F_p.
Definizione della mappa di Froebenius dall'anello F_p[x]/〈 f 〉 in se.
Algoritmo di Berlekamp per la fattorizzazione di polinomi.
Introduzione alla Teoria dei Codici:
Problema generale della codifica&decodifica.
Codici. Distanza di Hamming. Decodifica a minima distanza.
Bounds per codici (Hamming, sphere packing, Gilbert-Varshamov).
Codici lineari. Matrici generatrice e di controllo di parità.
Decodifica lineare (a sindrome).
Operazioni sui codici. Equivalenza di codici.
Codici di Reed-Solomon, codici di Hamming.
Codici ciclici. Teorema di classificazione.
Oltre la decodifica a minima distanza: correzione di errori localizzati (burst errors).