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

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

1. 07.03.11 (ore 3).
   Introduzione al corso: presentazione docenti, informazioni pratiche, prerequisiti, programma, motivazioni, corsi collegati, 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.
   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. 10.03.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.
   
3. 14.03.2011 (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. 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.
   
4. 21.03.2011 (ore 3)
   Dimostrazione dei corollari enunciati la lezione scorsa.
   Teorema cinese dei resti, ovvero 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. Si descrive inoltre una procedura esplicita, basata sull'algoritmo Euclideo esteso, per determinarla.
   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). Calcolo di φ(p) e φ(p^m) con p numero primo.
5. 24.03.2011 (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).
   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 non ha divisori dello zero 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..
   

6. 28.03.2011 (ore 2)
   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.
   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. 31.03.2011 (ore 3)
   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.
   Definizione di: omomorfismo di gruppi, omomorfismo di anelli, ideale di un anello, nucleo di un omomorfismo di anelli, il nucleo di un omomorfismo di anelli è un ideale.
   Dato un campo K, esiste un un'unico omomorfismo di anelli f:Z--->K.
   Z è un anello a ideali principali.
   Sia K un campo. K ha caratteristica 0 se f è iniettivo. Altrimenti f 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.
   Enunciato del 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: 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).
8. 04.04.2011 (ore 2)
   L'ordine di un sottogruppo di un gruppo finito divide l'ordine del gruppo.
   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.
   Dimostrazione del teorema di Gauss (1777-1855).
   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.
9. 07.04.2011 (ore 2)
   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. Parallelo con il caso particolare Z/3Z e con il caso generale A/I, con A anello e I ideale. Elementi di L=F₃/ < x^2+x+2 >, numero degli elementi, tabella moltiplicativa. 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.
   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.
10. 14 aprile 2011 (3 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 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: 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].
    
11. 18.04.2011 (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, 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.