Testo di riferimento:
Concrete abstract algebra
Niels Lauritzen
Cambridge University Press

Indico con s.d. i risultati enunciati senza dimostrazione.

1. 22.09.09 (ore 2).
   Introduzione al corso: presentazione docenti, informazioni pratiche, prerequisiti, programma, motivazioni, corsi collegati, testi di riferimento.
   Introduzione al sistema criptografico RSA--sistema di crittografia a chiave pubblica--per la trasmissione di dati. Essenzialmente le chiavi pubbliche sono su un numero naturale N (prodotto di due numeri primi molto grandi) e un numero naturale e scelto opportunamente; la una chiave privata e' un altro numero d, segreto, che si utilizza per la decrittazione. Per iniziare a curiosare: algoritmo RSA e anche elliptic curve cryptography.
   Definizioni di gruppo, gruppo abeliano, anello, anello commutativo, campo. L'insieme dei numeri interi e' un gruppo abeliano rispetto alla somma, e' un anello commutativo con le operarazioni di somma e prodotto. L'insieme dei numeri razionali, con le operazioni di somma e prodotto, e' un campo. Lo stesso vale per i numeri reali e per i numeri complessi.
   Divisione con resto (teorema s.d.). Definizione di divisore.
   
2. 23.09.09 (ore 2).
   Congruenze: congruenza modulo un intero positivo d, definizione e prime proprieta'. La congruenza conserva somma e prodotto.
   L'importante identita' [xy]_d=[[x]_d[y]_d]_d con x,y numeri interi. Su questa si basa l'algoritmo dei quadrati ripetuti per calcolare il resto con dividendi molto grandi. Esempio svolto: calcolo del resto della divisione di 12¹¹ per 21.
   Massimo comun divisore: esistenza e unicita'.
3. 24.09.09 (ore 2).
   Algoritmo Euclideo per determinare il massimo comun divisore, gcd(m,n), tra due interi m e n. Algoritmo Euclideo esteso per determinare interi x e y tali che xm+yn=gcd(m,n). Definizione: m e n sono primi tra loro se gcd(m,n)=1. Proposizioni: Se a divide bc e a e b sono primi tra loro, allora a divide c; Se gcd(a,b)=1, a divide c e b divide c, allora ab divide c; Se gcd(a,b)=1 e gcd(a,c)=1 allora gcd(a,bc)=1.
   Introduzione al teorema cinese dei resti. Esempi. La congruenza e' una relazione di equivalenza.
   Definizione della applicazione resto r da Z/n a Z/n₁x...Z/n_r, con n=n₁...n_r.
   Assegnato il primo foglio di esercizi: tra gli altri algoritmo binario per il calcolo del massimo comun divisore.
   Per curiosare Dictionary of Algorithms and Data Structures.
4. 29.09.09 (ore 2).
   Teorema cinese dei resti (se i fattori n_i sono primi tra loro l'applicazione r e' definita da
   (Z/N) a (Z/n₁)x...x (Z/n_k) e' biunivoca; calcolo esplicito di r^-1 utilizzando l'algoritmo Euclideo esteso).
   Definizione della funzione &phi di Eulero sui naturali. Proposizione: Se n e m sono primi tra loro, allora &phi(mn)=&phi(m)&phi(n).
   Teorema di Eulero: siano a,n interi primi tra loro, n naturale. Allora a^&phi(n)&equiv 1(mod n). Calcolo di &phi(p) e &phi(p^m) con p numero primo.
5. 30.09.09 (ore 2).
   Esistono infiniti numeri primi (s.d.). Ogni intero positivo si fattorizza in modo unico come prodotto di numeri primi (s.d.).
   Calcolo della funzione di Eulero nota la fattorizzazione: se n=p₁^r₁...p_h^r_h allora &phi(n)=n(1-1/p₁)...(1-1/p_h).
   Il sistema RSA in dettaglio, preso N=pq, come scegliere la chiave pubblica e e determinare la chiave privata d, sfruttando i risultati dimostrati fin'ora.
   Definizione, sull'insieme delle classi di resto modulo n, che indichiamo con Z/nZ, le operazioni di somma e di prodotto, con queste operazioni Z/nZ e' un anello commutativo. Gli elementi in Z/nZ primi con n formano un gruppo di ordine &phi(n) (sono gli elementi invertibili di Z/nZ), in particolare Z/nZ e' un campo se e solo se n e' primo (da riprendere e concludere nella prossima lezione).
   Per curiosare: Randomness and pseudorandomnes, di Avi Wigderson, scarica il file Summer 2009 da qui Random numbers; per una bella introduzione ai generatori congruenziali (in italiano) guardare la sezione 5.9 del Trattatello di probabilita' di E. Marinai e G. Parisi.
6. 06.10.09 (ore 2).
   Esempi: tabella moltiplicativa di (Z/4Z)_*,(Z/5Z)_*.
   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: dati due polinomi f e d, con d non zero, esistono unici polinomi q ed r, con r=0 o deg(r)< deg(d), tali che f=qd+r.
   Algoritmo della divisione (in sintesi). Esempi.
   Radice di un polinomio. Un elemento a in K e' radice del polinomio f se e solo se f e' divisibile per x-a.
   Molteplicita' di una radice
   Teorema: Sia f un polinomio a coefficienti in un campo K, con radici a₁,...,a_r. Allora f=q(x-a₁)^&nu₁... (x-a_r)^&nu_r, dove q e' un polinomio a coefficienti nel campo K, senza radici in K. La dimostrazione si tralascia, conseguenza di quanto gia' svolto.
   
7. 07.10.09 (ore 2)
   Come esempio di applicazione si dimostra che per ogni p primo si ha (p-1)!&equiv-1(mod p).
   Derivata Df di un polinomio f e sue proprieta'.
   Lemma: Siano f,g due polinomi a coefficienti in un campo K. Se f² divide g, allora f divide Dg; l'elemento a in k e' una radice del polinomio f con molteplicita' maggiore di 1 se e solo se e' una radice di f e di Df.
   Nel campo dei numeri complessi consideriamo le redici n-esime di 1.
   Lemma: &xi_k=e^{2&pi i k/n}, con 1&le k&le n e' una radice primitiva n-esima di 1 se e solo se k e' primo con n. Inoltre se &xi e' n-esima primitiva e &xi^m=1, allora n divide m.
   Definizione per ogni n naturale &ge 1, del polinomio ciclotomico &Phi_n.
   Teorema: Il prodotto dei polinomi ciclotomici &Phi_d(X), con d che divide n, e' uguale a Xⁿ-1.
8. 08.10.09 (ore 2)
   Teorema: I polinomi ciclotomici hanno coefficienti interi.
   Sia K un campo. Esiste un unico omomorfismo di anelli dall'anello Z al campo K. (definizione di omomorfismo f da un anello A a un anello B: un omomorfismo f:A-->B e' un'applicazione da A a B tale che per ogni x,y in A si ha f(x+y)=f(x)+f(y),f(xy)=f(x)f(y) e f(1)=1). Esiste d naturale tale che dZ=ker(k). Se d e' positivo (cioe' non zero) allora e' primo. d si dice caratteristica del campo k.
   I polinomi ciclotomici in un campo K. Definizione di radice n-esima primitiva di 1 in K.
   Lemma: Se &alpha e' una radice di &Phi_n e non e' una radice multipla di Xⁿ-1, allora &alpha e' una radice n-esima primitiva di 1.
   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.
   In particolare F^*_p e' ciclico per ogni p. Esempio: 2 genera F^*₁₃. I sistemi di crittografia a chiave pubblica ElGamal, proposti da Taher Elgamal nel 1984, sono basati sui gruppi ciclici (cfr. ad esempio, oltre al libro di testo, Capitolo 8 di Handbook of applied cryptography).
9. 13.10.2009 (ore 2)
   Definizione di anello quoziente A/I, con A anello e I ideale. 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. Ripetiamo la definizione di caratteristica di un campo.
   Esempi di campi costruiti come quozienti: R[X]/&lang X²+1&rang, costruzione in dettaglio e identificazione con il campo C dei numeri complessi; F₂/&lang X²+X+1&rang, costruzione in dettaglio; si ottiene un campo di ordine 2².
   Proposizione: Se f e' irriducibile in K[X], deg(f)>1, allora f non ha radici. Viceversa, se deg(f)=2,3 e f non ha radici, allora e' irriducibile.
   In generale F_p/&lang f&rang, con f irriducibile in F_p di grado n, e' un campo con pⁿ elementi.
   Lemma: Sia F un campo finito. Allora F ha pⁿ elementi, dove p e' primo e n&ge 1, inoltre esiste f in F_p[X] irriducibile di grado n tale che F e' isomorfo a F_p/&lang f &rang.
   Definizione di isomorfismo.
   
10. 14.10.09 (ore 2).
    Teorema: siano p primo e n&ge 1, esiste un unico campo con pⁿ elementi (a meno di isomorfismi).
    Piu' precisamente dimostriamo: 1) esiste un polinomio irriducibile in F_p[X] di grado n
    2) se F e F' sono campi finiti con pⁿ elementi allora F e F' sono isomorfi.
    Prima di iniziare la dimostrazione occorre il seguente Lemma: siano &tau, d, n naturali con &tau&ge 1. Allora &tau^d divide &tauⁿ se e solo se d divide n. (s.d.)
    Deduciamo 1) dal seguente risultato: se f e' un fattore irriducibile che divide &Phi_pⁿ-1 in F_p[X], allora f ha grado n.
    Dimostrazione. Ossrvazione: ne consegue che n divide &phi(pⁿ-1).
    Lemma: A/I e' un campo, con A anello e I ideale, se e solo se I e' massimale. Dimostrazione di 2).
    Per curiosare: applicazioni alla teoria dei codici sul libro Codes and Curves, J. Walker AMS.
11. 20.10.09 (ore 2).
    Teorema: Il polinomio X^pn-1-X in F_p e' il prodotto DEI polinomi monici irriducibili di F_p di grado d, con 0&le d &le n e d che divide n.
    Corollario: Sia N_d il numero dei polinomi monici irriducibili di grado d in F_p, allora pⁿ=&sum_{d | n}d N_d.
    Da cui la formula N_n=1&frasl n&sum_{d | n}&mu(n&frasl d)p^d.
    Caso particolare della formula nel caso in cui n sia primo.
    Definizione della mappa di Froebenius dall'anello F_p[x]&lang f &rang in se. F_p[x]&lang f &rang e' uno spazio vettoriale su F_p di dimensione uguale al grado di f. La mappa di Froebenius e' un omomorfismo di anelli ed e' una applicazione lineare. Teorema: Un polinomio f e' irriducibile se e solo se Ker(F)=0 e Ker(F-I)-F_p.
    Esempio di calcolo della matrice di F e F-I con F₂[x]&lang X⁵+X+1 &rang. Il polinomio X⁵+X+1 e' riducibile in F₂[x].
    
12. 21.10.09 (ore 2).
    Prima parte della dimostrazione: f irriducibile implica Ker(F)=0 e Ker(F-I)-F_p. La dimostrazione da' un'algoritmo per la fattorizzazione di polinomi (algoritmo di Berlekamp). Seconda parte della dimostrazione: se Ker(F)=0 e Ker(F-I)=F_p allora f e' irriducibile.
    Esempi: seconda parte dell'esercizio sulla fattorizzazione in F₂ di X⁵+X+1.
    Introduzione agli insiemi parzialmente ordinati (poset). Definzione.
13. 22.10.09 (ore 2)
    Per la parte sui poset il testo di riferimento e' quello del Professor Modica, (nuova versione novembre 2009). Nelle note vi e' un'ampia trattazione di problemi di combinatoria enumerativa. Nel libro Enumerative Combinatorics, Volume I di R. Stanley, il Cap. 3 e' interamente dedicato ai poset. Poset localmente finiti, esempi (insieme delle parti con la relazione di inclusione, insieme dei naturali con la relazione d'ordine d precede n se d divide n, relazione d'ordine su un albero con radice).
    Algebra di incidenza di un poset localmente finito: definizione delle operazioni, dimostrazione della associativita' del prodotto, esistenza dell'elemento neutro. L'inverso (destro e sinistro) per la funzione &zeta che definisce l'ordine esiste (destro e sinistro), e' unico, ed e' la funzione di Moebius del poset. Funzione di Moebius per i naturali con la relazione d'ordine n precede m se m-n>0. Prodotto cartesiano di due poset.
14. Martedi 27 ottobre (ore 2).
    La funzione di Moebius del prodotto di due poset. La funzione di Moebius dell'insieme delle successioni di naturali finite. La funzione di Moebius dei naturali con la relazione d'ordine data da n precede m se n divide m. Poset localmente finiti con ideali d'ordine finiti. Azione a destra dell'algebra di incidenza su tali poset. Formule di inversione. Esempio di applicazione: la formula pⁿ=&sum_{d | n}d N_d per ogni n, implica N_n=1&frasl n&sum_{d | n}&mu(d,n)p^d.
15. Mercoledi' 28 ottobre (ore 2).
    Versione duale delle formule di inversione, cioe': Poset localmente finiti con ideali duali d'ordine finiti; Azione a sinistra dell'algebra di incidenza su tali poset; Formule di inversione duali a quelle enunciate ieri. Diagramma di Hasse di un poset. Esempi. Definizione di reticolo. Diagramma di Hasse di un reticolo. Definizione di reticolo completo. Enunciato del teorema del punto fisso di Tarski. Esempio di applicazione: siano A e B due insiemi, con g da A a B applicazione iniettiva e h da B ad A applicazione iniettiva, allora esiste f da A a B applicazione biunivoca. Prima parte della dimostrazione del teorema di Tarski.
16. Martedi' 3 Novembre (ore 2).
    Seconda parte della dimostrazione del teorema del punto fisso.
    Esercizi di riepilogo: svolgimento di un esercizio articolati in quattro punti con il seguente risultato finale: &Phi_n e' irriducibile in F_p[X] se e solo se [p] genera (Z/nZ)^*. Parziale svolgimento di uno degli esercizi distribuiti nei fogli.
    Note su reticoli e teorema del punto fisso

Teoria dei codici. Per curiosare:
1. articolo originale di Reed e Solomon: Polynomial Codes Over Certain Finite Fields, I. S. Reed and G. Solomon Journal of the Society for Industrial and Applied Mathematics, Vol. 8, No. 2 (Jun.,1960), pp. 300-304. Stable URL
2. Decoding of Reed Solomon Codes beyond the Error-Correction Bound, Madhu Sudan , JOURNAL OF COMPLEXITY 13, 180-193 (1997) ARTICLE NO. CM970439.
   Vedi anche questo articolo di Madhu.
   Sempre di S. Madhu a questo link si trovano le note di teoria dei codici, lezione per lezione, in pdf.
   
3. Potete trovare qui un'introduzione ai codici di Goppa.
4. Questa invece e' una tesi di master sulla decodifica dei codici di Reed Solomon, essendo una tesi (non un articolo) dedica spazio alle necessarie conoscenze preliminari, a cui e' dedicata la prima parte.

Articoli che e' possibile portare all'esame
1. L'articolo originale di Reed e Solomon
   
2. Error Correcting Coding for a Non-symmetric Ternary Channel
   
3. Moderate-Density Parity-Check Codes