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

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

1. 20.09.12 (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. 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.
2. 24.09.12 (ore 2).
   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. 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.
3. 27.09.12 (ore 3).
   Massimo comun divisore: esistenza e unicita'. 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. Proposizione: Se a divide bc e a e b sono primi tra loro, allora a divide c.
4. 01.10.12 (ore 2).
   Proposizioni: 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: 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 (è infatti un isomorfismo di anelli (dimostrata solo la biunivocita').
   Dimostrazione del teorema cinese del resto mediante algoritmo esplicito per determinare una soluzione, basato sull'algoritmo euclideo esteso. Esempio di applicazione del teorema cinese del resto: Shamir secret sharing.
   Per iniziare a curiosare: Secret sharing.
   Definizione della funzione φ di Eulero (1707-1783) sui naturali.
5. 04.10.2012 (ore 3).
   Proposizione: Se n e m sono primi tra loro, allora φ(mn)=φ(m)φ(n).
   (Z/nZ)^* \egrave un gruppo, il gruppo degli invertibili dell'anello Z/nZ.. Z/nZ e' un campo se e solo se n \egrave e' primo. Teorema di Eulero: siano a,n interi primi tra loro, n naturale. Allora a^φ(n)≡ 1(mod n).
   
6. 08.10.2012 (ore 2).
   Ogni naturale positivo è prodotto di primi (SD) 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 (SD).
   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.

   Per iniziare a curiosare: The largest known primes; Great internet Mersenne (1588-1648) prime search; Prime numbers and Prime factorization; 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. 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..

   L'anello dei polinomi, A[x], nell'indeterminata x a coefficienti in un anello A. Grado di un polinomio. 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.
   Sia K un campo. Siano f,g sono in K[x], allora deg(fg)=def(f)+deg(g). Gli elementi invertibili di K[x] sono tutti e soli i polinomi costanti non nulli.
   Definizione di radice di un polinomio. Denotiamo con V(p) l'insieme delle radici del polinomio p. Un elemento a in K è 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. Si ha V(fg)=V(f)UV(g). Teorema: Sia F in K[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).
   

7. 11.10.2012 (3 ore)
   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.
   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.
   Dimostrazione di (a)
8. 15.10.2012 (2 ore)
   Dimostrazione di (b).
   Dato un campo K, esiste un un'unico omomorfismo di anelli k:Z--->K. Il nucleo di k, Ker(k)=dZ, con d=0 oppure d numero primo. Il numero d si dice caratteristica del campo K.
   La proprietà (b) dei polinomi ciclotomici implica che, 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.
9. 18.10.2012 (3 ore)
   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. Inoltre se g^n=e (elemento neutro), allora ord(g) divide n.
   Definizione di gruppo ciclico.finito del gruppo moltiplicativo di K. Allora G è ciclico.
   Esempi: i gruppi moltiplicativi di Z/pZ.
   Sia K un campo. Definizione di polinomio irriducibile in k[x]. 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.
   Esempio di 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]: K=F₂=Z/2Z e f(x)=x^2+x+1.
   
10. 22.10.2012 (2 ore)
    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]. Notare che l'elemento α=[x] è radice del polinomio f in L. Esempio accennato K=R f(x)=x^2+1, si ottiene L=C campo dei complessi. Esempio con K=F₃, f=x^2+x+2. Elementi di L=F₃/ < x^2+x+2 >, numero degli elementi, tabella moltiplicativa utilizzando la relazione α²=2α+1. Caso generale di F_p (p è numero primo) e f polinomio irriducibile in F_p[x] di grado n, allora il quoziente L=F_p[x]/< f > è un campo con pⁿ elementi.
    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.
    Teorema di esistenza e unicita'. Enunciato:
    1)Esistenza: dati p numero primo e n intero positivo, esiste un campo F con pⁿ elementi.
    2) Unicita': siano F e F' campi finiti con lo stesso numero di elementi. Allora F e F' sono isomorfi.
    
11. 22.10.2012 (3 ore)
    Dimostriamo che (1b) dati p numero primo, n un intero positivo e f un fattore irriducibile di Φ_pⁿ-1, allora f ha grado n.
    Questo implica che dati p numero primo e n intero positivo, esiste un polinomio f irriducibile in F_p[x] di grado n, ossia la parte di esistenza del teorema.
    Dimostriamo inoltre l'unicita'.
12. 29.10.2012 (2 ore)
    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 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). Esempio di applicazione dell'algoritmo.
13. 05.11.2012 (2 ore)
    Esempio di applicazione dell'algoritmo di Berlekamp.
    Seconda parte della dimostrazione: Ker(F)=0 e Ker(F-I)=F_p implica f irriducibile.
    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.
14. 08.11.2012 (3 ore)
    Il problema del logaritmo discreto. Il sistema crittografico a chiave pubblica (Elgamal (cfr. ad esempio, oltre al libro di testo, Capitolo 8 di Handbook of applied cryptography).
    Esercizi di riepilogo su polinomi e costruzione di campi finiti.
    
15. 10.12.2012 (2 ore)
    Codici ciclici: definizione e teorema di classificazione: i codici lineari ciclici in F_qⁿ sono in corrispondenza biunivoca con i divisori monici del polinomio xⁿ-1 in F_q[x].
16. 13.12.2012 (2 ore)
    Sia g di grado n-k in F_q[x] il polinomio generatore del codice ciclico C in F_qⁿ, allora la dimensione di C e' k. La matrice generatrice di un codice ciclico a partire dal polinomio generatore. Esempi di codici ciclici. Esercizio per determinare la matrice di controllo di parita' a partire dal polinomio generatore (assegnato). Decodifica dei codici ciclici. Esempio di decodifica.