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

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

1. 20.09.11 (ore 3).
   Introduzione al corso: informazioni pratiche, programma, motivazioni, testi di riferimento.
   Introduzione al sistema crittografico RSA-- sistema di crittografia a chiave pubblica--per la trasmissione di dati. Essenzialmente le chiavi pubbliche sono un numero naturale N (prodotto di due numeri primi molto grandi) e un numero naturale e scelto opportunamente; la 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; elementary theory and practice of elliptic curves cryptography, the new generation of public key systems.
   Vedere anche la sezione 4.1 qui At risk - Public key encryption.
   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. Il campo F₂={0,1}.
   Divisione con resto (teorema s.d.). Definizione di divisore.
   Congruenze: definizione di congruenza modulo un intero positivo d.
2. 22.09.11 (ore 2).
   Ogni numero e' congruo, modulo d, al suo resto quando viene diviso per d. Due numeri sono congrui tra loro modulo d se e solo se hanno lo stesso resto quando vengono divisi per d. La congruenza conserva somma e prodotto. La congruenza è una relazione di equivalenza.
   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. Definizione dell'anello delle classi di resto modulo n. Esempi e relative tabelle additive e moltiplicative. Osservazione: se in un anello A ci sono divisori dello 0, allora A non è un campo. Quindi Z/nZ, se n non e' primo, non è un campo. Massimo comun divisore: esistenza e unicita'.
   
3. 27.09.11 (ore 3).
   Algoritmo Euclideo (Euclide (300 a.C.)) 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.
   Teorema cinese del resto, unicità della soluzione ed esistenza, mediante algoritmo esplicito per determinare una soluzione, basato sull'algoritmo euclideo esteso.
4. 29.09.11 (ore 2).
   Dimostrazione alternativa--non costruttiva--del teorema cinese del resto: l'applicazione resto r da Z/NZ a Z/n₁Z x ... Z/n_rZ, con n=n₁...n_r e gcd(n_i,n_j)=1 è biunivoca.
   Definizione della funzione φ di Eulero (1707-1783) sui naturali. Proposizione: Se n e m sono primi tra loro, allora φ(mn)=φ(m)φ(n).
   Teorema di Eulero: siano a,n interi primi tra loro, n naturale. Allora a^φ(n)≡ 1(mod n).
5. 04.10.11 (ore 3).
   Ogni naturale positivo è prodotto di primi. Teorema di Euclide: ci sono infiniti numeri primi.
   Sia p primo, se p divide ab, con a,b interi, allora o p divide a o p divide b. Analogamente, se p primo divide a₁a₂a₃...a_n, con a_j interi, allora p divide almeno uno degli interi a_j.
   Teorema: Ogni numero naturale positivo si scompone in modo unico (a meno dell'ordine dei fattori) in prodotto di numeri primi.
   Il Teorema di Eulero implica il piccolo teorema di Fermat (1601-1665): se p è primo e a è un intero tale che gcd(a,p)=1, allora a^p-1≡ 1(mod p).
   Sia n=p₁^e₁...p_k^e_k la scomposizione in primi del numero naturale n. Allora φ(n)=n(1-1/p₁)...(1-1/p_k).
   Algoritmo RSA in dettaglio.
   (Z/nZ)^* è un gruppo, il gruppo degli invertibili dell'anello Z/nZ. Z/nZ è un campo se se solo se p è primo.
   L'anello dei polinomi, A[x], nell'indeterminata x a coefficienti in un anello A. Grado di un polinomio. Se un anello A è un campo e f,g sono in A[x], allora deg(fg)=def(f)+deg(g). Sia K un campo, allora gli elementi invertibili di K[x] sono tutti e soli i polinomi costanti non nulli.

   Per curiosare: un survey interessante Numbers at work and Play, IE Shparlinski pubblicato nel volume AMS Notices, Febuary 2010 Volume 57 Issue 03 tutto dedicato alla crittografia. Poi ancora: Great internet Mersenne (1588-1648) prime search; Prime numbers and Prime factorization; The Mathematics Behind Quantum Computing: Part I Part II ; The discovery of the Pentium division flaw, from Thomas Nicely home page; 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..
   Sia d un polinomio a coefficienti in un anello A, con coefficiente del termine di grado massimo invertibile. Dato f in A[x] esistono unici q e r in A[x] tali che f=qd+r, con deg(r)< deg(d) o r=0.
   

6. 06.10.11 (ore 2).
   Definizione di radice di un polinomio. Denotiamo con V(p) l'insieme delle radici del polinomio p. Un elemento a in A è una radice del polinomio p se e solo se (x-a) divide p. Definizione di molteplicità, ν_a(p) di una radice a del polinomio p. Se A à non ha divisori dello zero, allora V(fg)=V(f)UV(g). Teorema: Sia A senza divisori dello zero e sia F in A[x]. Se V(f)={a₁,...,a_r} allora f=q(x-a₁)^ν_a1(p)...(x-a_r)^ν_ar(p), con q in A[x] e V(q) vuoto. Inoltre ν_a1+...+ν_ar≤deg(f).
   Derivata di un polinomio e sue proprietà . Lemma: Siano f,g due polinomi in A[x], A anello. Se f² divide g, allora f divide Dg; l'elemento a in A e' una radice del polinomio f con molteplicità maggiore di 1 se e solo se e' una radice di f e di Df.
   Radici n-esime di 1 nel campo dei numeri complessi.
   
7. 11.10.11 (ore 2).
   Lemma: ξ_k=e^{2π i k/n}, con 1≤ k≤ n e' una radice primitiva n-esima di 1 se e solo se k e' primo con n. Inoltre se ξ e' n-esima primitiva e ξ^m=1, allora n divide m.
   Definizione per ogni n naturale ≥ 1, del polinomio ciclotomico Φ_n.
   Teorema: (a) Il prodotto dei polinomi ciclotomici Φ_d(X), con d che divide n, e' uguale a Xⁿ-1.
   (b)I polinomi ciclotomici sono monici a coefficienti interi.
   Dato un campo K, esiste un un'unico omomorfismo di anelli k:Z--->K.
   
8. 13.10.11 (ore 2).
   Sia K un campo. K ha caratteristica 0 se k è iniettivo. Altrimenti k induce un omomorfismo iniettivo da Z/pZ in K, con p primo. In questo caso si dice che il campo K ha caratteristica positiva p. Quindi, dato un campo K, possiamo considerare Φ_n in K[x] e vale ancora l'identità (a).
   Definizione di radice n-esima primitiva di 1 in un campo K. Lemma: se a in K è tale che: Φ_n(a)=0 e a non è radice multipla di Xⁿ-1, allora a è una radice n-esima primitiva di 1.
   Teorema di Gauss: sia K un campo e G un sottogruppo finito del gruppo moltiplicativo di K. Allora G è ciclico.
   Esempi: i gruppi moltiplicativi di Z/pZ.
   Osservazione: la sicurezza dei sistemi di crittografia a chiave pubblica ElGamal, proposti da Taher Elgamal nel 1984 si fonda sulla difficoltà di determinare un generatore per opportuni gruppi ciclici (cfr. ad esempio, oltre al libro di testo, Capitolo 8 di Handbook of applied cryptography).
   Sia G un gruppo finito e sia g un elemento di G. Definizione di ordine di g: ord(g). Si ha: ord(g) divide l'ordine di G. Se g^n=e (elemento neutro), allora ord(g) divide n.
   
9. Costruzione di un campo L a partire dall'anello dei polinomi a coefficienti in un campo K e da un polinomio f irriducibile in K[x]. Esempi: K=R, f=x²+1 (campo dei complessi); K=F₂, f=x^2+x+1.
10. 25.10.2011 (ore 3)
    Costruzione di un campo L a partire dall'anello dei polinomi a coefficienti in un campo K e da un polinomio f irriducibile in K[x]. Esempio con K=F₃, f=x^2+x+2. Elementi di L=F₃/ < x^2+x+2 >, numero degli elementi, tabella moltiplicativa. Parallelo con la costruzione Z/3Z e con il caso generale A/I, con A anello e I ideale. Sia α=[x], si noti che α^2+α+2=0, ossia α=[x] è radice del polinomio f.
    In generale se p è un numero primo e f è un polinomio irriducibile in F_p[x] di grado n, allora il quoziente L=F_p[x]/< f > è un campo con pⁿ elementi. Inoltre l'elemento α=[x] è radice del polinomio f in L.
    Se f è un polinomio irriducibile in K[x], di grado >1, allora f non ha radici in K.
    Se il grado di un polinomio f in K[x] è 2 o 3 e f non ha radici in K, allora f è irriducibile.
    Lemma: Sia F un campo finito. Allora esistono un numero primo p e un polinomio irriducibile f in F_p[x] tali che F è isomorfo al quoziente F_p[x]/< f >. Corollario: Sia F un campo finito, allora il numero di elementi di F è pari alla potenza di un primo.
    
11. 27 ottobre 2011 (ore 3) Teorema di esistenza e unicità. Enunciato:
    1)Esistenza: dati p numero primo e n intero positivo, esiste un campo F con pⁿ elementi.
    2) Unicità: siano F e F' campi finiti con lo stesso numero di elementi. Allora F e F' sono isomorfi.
    (1) è equivalente al seguente enunciato:
    (1a): dati p numero primo e n intero positivo, esiste un polinomio f irriducibile in F_p[x] di grado n.
    Il seguente enunciato implica (1a):
    (1b) dati p numero primo e n intero positivo, sia f un fattore irriducibile di Φ_pⁿ-1, allora f ha grado n.
    Dimostrazione di (1b) e unicita'.
12. 3 novembre 2011 (ore 3)
    Definizione della mappa di Frobenius (1849-1917) dall'anello F_p[x]< f > in se. F_p[x]< f > e' uno spazio vettoriale su F_p di dimensione uguale al grado di f. La mappa di Frobenius 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.
    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 (fatta per passi successivi, di alcuni si e' tralasciata la dimostrazione): se Ker(F)=0 e Ker(F-I)=F_p allora f e' irriducibile.
    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].
    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, dove &mu \è la funzione di Moebius (vedere ad esempio in questo file l'esempio numero 3).
    Caso particolare della formula nel caso in cui n sia primo.
13. 8 novembre 2011 (ore 3)
    Introduzione alla teoria dei codici (error correcting codes). Attraverso un esempio abbiamo visto: il principio della ridondanza; la capacita' di rilevare errori, la capacita' di correggere errori in dipendenza della minima distanza (di Hamming) del codice. Prime definizioni: alfabeto, parole, codice, information rate di un codice. Modello stocastico del canale, dovuto a C. E. Shannon (1916-2001): un canale e' caratterizzato da un alfabeto di cardinalita' q e da una matrice di probabilita' P, quadrata di ordine q, cosi' definita: P_ij e' la probabilita' di ricevere il simbolo a_i quando e' trasmesso il simbolo a_j (per i nostri scopi e' sufficiente considerare canali con lo stesso alfabeto in input e output). P e' una matrice con coefficienti non negativi tale che la somma dei coefficienti di ogni colonna e' uguale a 1. Per canale senza memoria si intende un canale il cui comportamento al tempo t e' indipendente dal tempo e dai passati input/output. Canali fortemente simmetrici. Esempio: binary symmetric channel (BSC). Criterio di decodifica a massima probabilita'. Esempio.
    Definizione formale e proprieta' della distanza di Hamming.
    Per curiosare: "probably no single work in this century has more profoundly altered man's understanding of communication than Shannon's 1948 paper A mathemathical theory of communication" (David Slepian (editor) in Key papers in the Development of Information Theory, IEEE Press, NY, 1974).
14. 10 novembre 2011 (ore 2)
    In un canale senza memoria fortemente simmetrico la decodifica a massima probabilita' e la decodifica a minima distanza (con la distanza di Hamming) coincidono. Definizione di distanza di Hamming di una parola x dal codice C: d(x,C); distanza di Hamming del codice C: d(C). Definizione di sfera aperta e chiusa di centro x e raggio s, denotate (in questo registro) rispettivamente con B_s(x) e B_s(x).
    Definizione (a): un codice C ⊂ Aⁿ_q rileva al piu' s errori con la decodifica a minima distanza (con distanza di Hamming) se per ogni c in C si ha B_s(x)∩C={x}.
    Definizione (b) un codice C ⊂ Aⁿ_q corregge al piu' s errori con la decodifica a minima distanza (con distanza di Hamming) se per ogni x tale che d(x,C)≤s esiste un unica parola c in C tale che x appartiene a B_s(c).
    Osserviamo che un codice C che soddisfa la definizione (b) decodifica esattamente la parola trasmessa se in trasmissione sono stati fatti al piu' s errori, infatti, supponiamo che c' sia la parola inviata e w la parola ricevuta, si avra' quindi d(c',w)≤s. Quindi d(w,C)≤s. Sia c la parola che realizza la minima distanza d(w,C)=d(w,c)≤s. Per la definzione (b) esiste un'unica parola c in C tale che w appartiene a B_s(c). Poiche' w appartiene a B_s(c') e w appartiene a B_s(c) si ha c'=c. Per quanto detto la decodifica di w a minima distanza e' esattamente c'.
    Lemma: Sia C un codice in Aⁿ_q. Allora d(C)≥2s+1 se e solo se B_s(c)∩B_s(c')=∅ per ogni c e c' in C, c diverso da c'.
    Dimostrazione: prima implicazione, ossia d(C)≥2s+1 implica B_s(c)∩B_s(c')=∅ per ogni c e c' in C, c diverso da c'. Supponiamo per assurdo che esistano c,c' in C e x in Aⁿ_q tali che x appartiene a B_s(c)∩B_s(c')=∅. Si ha d(c,c')≤d(c,x)+d(x,c')≤s+s=2s, che contraddice l'ipotesi. Per l'implicazione inversa supponiamo per assurdo che d(c,c')=d<2s+1. Esistono quindi c e c' in C tali che d(c,c')=d<2s+1. Si ha:
    c=c₁...c_sc_s+1...c_2sc_2s+1...c_n
    e c'=c'₁...c'_sc'_s+1...c'_2sc_2s+1...c_n.
    Costruiamo x=c'₁...c'_sc_s+1...c_2sc_2s+1...c_n
    (per semplificare la notazione supponiamo che c e c' differiscano per i primi d simboli). Si ha quindi d(x,c)≤s e d(x,c')≤s, quindi x appartiene a B_s(c)∩B_s(c')=∅, in contraddizione con l'ipotesi.
    Proposizione:(i) un codice C rileva al piu' s errori se e solo se d(C)≥s+1; (ii) un codice C corregge al piu' s errori se e solo se d(C)≥2s+1
    Dimostrazione (i). Riporto la dimostrazione di (ii).
    Dimostriamo che la def. (b) e' equivalente a d(C)≥2s+1.
    Nell'ipotesi d(C)≥2s+1 sia x in Aⁿ tale che d(x,C)≤s, quindi esiste c in C tale che d(x,c)≤s. Vogliamo dimostrare che c e' unica. Supponiamo che esista un'altra parola c' del codice tale che d(x,c')≤s. Si ha d(c,c')≤d(c,x)+d(x,c')≤s+s=2s, in contraddizione con l'ipotesi. Viceversa, supponiamo che il codice verifichi la definizione (b) e supponiamo per assurdo che d(C)<2s+1. Allora per il Lemma sopra dimostrato, esistono c e c' in C tali che B_s(c)∩B_s(c') non e' vuoto. Sia x in B_s(c)∩B_s(c'), x contraddice la definzione (b).
15. 15 novembre 2011 (ore 3)
    Un codice C si dice di tipo (n,M,d)_q se C e' contenuto in Aⁿ, la cardinalita' di A, |A|, e' q, la cardinalita' di C, |C|, e' M e d=d(C). La capacita' di rilevare/correggere errori con la decodifica a minima distanza dipende dal parametro d, precisamente:un codice (n,M,d)_q rileva al piu' d-1 errori e corregge al piu' [(d-1)/2] errori (il numero [(d-1)/2] indica la parte intera di (d-1)/2). Denotiamo con e=[(d-1)/2]. Teorema di Hamming. Lemma per la dimostrazione del teorema di Hamming: si conta il numero di parole di Aⁿ contenute in una palla chiusa di raggio r. Definizione di codice perfetto.
    Codici lineari: definizione. Esempi. Ortogonale di un codice lineare, somma di due codici lineari. Definizione di matrice generatrice e matrice di controllo di parita' di un codice lineare.
16. 17 novembre 2011 (ore 2)
    Caratterizzazione di un codice e del suo ortogonale a partire rispettivamente dalla matrice di controllo di parita' e dalla matrice generatrice. Altre proprieta' della matrice generatrice e di controllo di parita'. Peso di Hamming di un codice lineare. Il peso di Hamming e' uguale alla distanza del codice.
    Sia C un codice lineare e H una matrice di controllo di parita' di C. Allora
    1) d(C)≥k se e solo se comunque prese k-1 colonne di H queste sono linearmente indipendenti.
    2) d(C)≤k se e solo se esistono k colonne di H linearmente dipendenti.
    3) d(C)=k se e solo se comunque prese k-1 colonne di H queste sono linearmente indipendenti ed esistono k colonne di H linearmente dipendenti.