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

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

1. 19.01.09 (ore 2).
   Esempio di algoritmo RSA--sistema di crittografia a chiave pubblica--per la trasmissione di dati, l'algoritmo RSA e' basato su funzioni cosidette "a senso unico", costruite a partire da un numero naturale N prodotto di due numeri primi, con una chiave pubblica di criptazione dei messaggi, e, e una chiave privata, d, per la decriptazione. Alcuni esempi di sfide di fattorizzazione fatte dagli RSA laboratories possono essere trovate sul sito RSA.
   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.
   Divisione con resto.
   Congruenze: congruenza modulo un intero positivo d, 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.
2. 26.01.09 (ore 2).
   Massimo comun divisore: esistenza e unicita'. 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.
3. 28.01.09 (ore 2).
   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.
   Teorema cinese dei resti (se i fattori n_i sono primi tra loro l'applicazione r 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).
4. 02.02.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.
5. 09.02.09 (ore 2).
   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.
   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. 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
   
6. 16.02.09 (ore 2).
   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 svolto nella lezione precedente.
   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.
   
7. 18.02.09 (ore 2).
   Teorema: I polinomi ciclotomici hanno coefficienti interi.
   Sia K un campo. Omomorfismo k dell'anello degli interi Z in K (definizione di omomorfismo tra anelli, gruppi,...). Caratteristica d di un campo. Se d e' positivo (cioe' non zero) allora e' primo.
   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 criptografia 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).
   Sia K un campo e f un polinomio irriducibile in K[X]. Definiamo l'insieme delle classi di resto modulo f, K[X]/&lang f&rang, analogamente a quanto fatto in Z. Si ottiene un anello.
   Possiamo identificare K[X]/&lang f&rang con {[a₀+a₁X+...+ a_n-1X^n-1] | a_j &isin K}.
8. 23.02.09 (ore 2).
   Poiche' f e' irriducibile K[X]/&lang f&rang e' un campo (con dimostrazione)
   Brevemente: definizione di ideale , &lang f&rang e' un ideale di K[X]; definizione di ideale principale , &lang f&rang e' un ideale principale, Z e K[X] sono anelli a ideali principali (con dimostrazione).
   Esempi di campi ottenuti con la costruzione quoziente k[X]/&lang f&rang: 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.
   
9. 25.02.09 (ore 2).
   Siano p primo e n&ge 1, esiste un unico campo con pⁿ elementi. Piu' precisamente
   Teorema: 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.
   Enunciato esistenza: esiste un polinomio irriducibile di F_p[X] di grado n&ge 1. Piu' precisamente se f e' un fattore irriducibile che divide &Phi_pⁿ-1 in F_p[X], allora f ha grado n.
   Dimostrazione. Ne consegue che n divide &phi(pⁿ-1).
   Unicita'.
   Preliminare: se F_p/&lang f &rang e' un campo allora &lang f &rang e' massimale in F_p.
   Dimostrazione
10. 04.03.09 (ore 2).
    Definizione della mappa di Froebenius da 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. Richiamo della definizione di matrice di una applicazione lineare rispetto a una base. Esempio di calcolo della matrice di F e F-I con F₂[x]&lang X⁵+X+1 &rang.
    Teorema: Un polinomio f e' irriducibile se e solo se Ker(F)=0 e Ker(F-I)-F_p.
    Inoltre la dimostrazione da' un'algoritmo per la fattorizzazione di polinomi (algoritmo di Berlekamp). Prima parte della dimostrazione: se Ker(F)=0 allora f e' riducibile (prima parte dell'algoritmo di Berlekamp).
11. 09.03.09 (ore 2).
    Compilazione schede di valutazione del corso.
    Seconda parte della dimostrazione: se Ker(F-I) contiene strettamente F_p allora f e' riducibile (seconda parte dell'algoritmo di Berlekamp); 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. Assegnazione di un altro esercizio di fattorizzazione di un polinomio mediante l'algoritmo di fattorizzazione di Berlekamp.
    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.(s.d.)
    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.
    Assegnazione di esercizi sulla fattorizzazione di polinomi.
12. 11.03.09 (ore 2). Dimostrazione del teorema enunciato nella lezione precedente. Osservazioni sulla formula per il calcolo del numero dei polinomi irriducibili in F__p. Un algoritmo per calcolare i fattori di grado d di un polinomio g in F_p[X] attraverso il calcolo dei gcd(g,X^pj-X). Svolgimento di un esercizio sull'algoritmo di Berlekamp. Assegnazione e parziale svolgimento di un esercizio il cio risultato finale e' il seguente: &Phi_n e' irriducibile in F_p[X] se e solo se [p] genera (Z/nZ)^*.
13. 16.03.09 (ore 2). Definizione di least upper bound e greatest lower bound di un sottoinsieme X di un insieme P parzialmente ordinato (gli insiemi parzialmente ordinati sono stati trattati nel modulo parallelo). Definizione di reticolo. Definizione di reticolo completo. L'esempio dell'insieme delle parti. Il teorema del punto fisso di Tarski: Sia L un reticolo completo e sia f una applicazione da L in L che conserva l'ordine. Allora l'insieme P dei punti fissi di f e' un reticolo completo, inoltre il massimo di P e' il least upper bound dell'insieme degli x in L tali che x&ge f(x) e il minimo di P e' il greatest lower bound dell'insieme degli x in L tali che f(x)&ge x. In particolare P e' non vuoto. Dimostrazione. Esempi di applicazioni: siano A e B due insieme, siano g da A in B e f da B in A due applicazioni iniettive, allora esiste una applicazione i da A in B biunivoca. La dimostrazione si basa sul teorema di Tarski.