Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2010-2011
Primo semestre.
Diario delle lezioni di di Teoria Elementare dei Numeri

Prima settimana:
Fattorizzazione e primalita': il criptosistema RSA (vedi articolo di Schoof su Didattica della Matematica).
Complessita' delle operazioni aritmetiche sugli interi: somma, sottrazione, prodotto, divisione con resto, massimo comun divisore con l'algoritmo di Euclide, elevamento ad una potenza intera (vedi soluzioni Esercizi 1 in "Esercizi svolti").

Seconda settimana:
- Complessita' delle operazioni aritmetiche su Z_n : somma, prodotto, elevamento ad una potenza intera, inverso. (vedi soluzioni Esercizi1 in "Esercizi svolti").
Richiami sull'anello Z_n. Il Piccolo Teorema di Fermat e le sue conseguenze. I numeri di Carmichael. (vedi nota2 - Gruppi, anelli, campi e applicazioni).
- Il test di primalita' di Miller-Rabin (vedi nota2, Appendice). Esempi con PARI/GP. Complessita' del test di Miller-Rabin. Il Teorema dei Numeri Primi (vedi Crandall-Pomerance, Thm.1.1.4; soluzioni Esercizi2 in "Esercizi svolti").

Esercizi relativi al materiale svolto nelle prime 2 settimane:
Esercizi1-svolti; Esercizi2-svolti, n.1-7; Esercizi1 2009, n.1,2;
Esercizi1 2010.

Terza settimana:
- Il metodo di fattorizzazione per tentativi e la sua complessita'. Il paradosso del compleanno. Il metodo di fattorizzazione &rho di Pollard, il Lemma di Floyd, la complessita' probabilistica del metodo &rho di Pollard. (vedi Crandall-Pomerance, sect. 5.2.1; Nota su Pollard &rho). Esempi con PARI/GP.

Esercizi1 2009, n.3, 4, 5, 6, 7, 8;
Esercizi2 2010

Quarta settimana:
Gruppi: definizione, proprieta' ed esempi. Prodotto diretto di gruppi. Gruppi abeliani. Gruppi ciclici e loro generatori. Gruppi abeliani finiti: Z_n e Z^*_n (vedi nota2).
La funzione φ di Eulero (vedi nota sulla funzione φ di Eulero).
Teorema di Lagrange. Piccolo Teorema di Fermat. Ordine di un elemento in un gruppo abeliano finito (vedi nota2). Esempi. Isomorfismi di gruppi (cenni).

Esercizi3-svolti.
Esercizi4-svolti dal sito EAL2009.

Quinta settimana:
Lemma 1 (Lemma di Gauss) e Lemma 2 della nota sulla radice primitiva. Enunciato del teorema della radice primitiva e conseguenze: Z^*_p (con p primo) e' ciclico, e in Z^*_p ci sono φ(d) elementi di ordine d. Esempi ed esercizi.
Lemma 3 della nota sulla radice primitiva. Dimostrazione del teorema della radice primitiva. Caratterizzazione delle radici primitive. (vedi Nota sulle radici primitive modulo p).

Esercizi3-svolti.
Esercizi4-svolti dal sito EAL2009.

Sesta settimana:
Numeri B-smooth: la funzione di Dickman (vedi Crandall-Pomerance, Sect.1.4.5, e soluzioni Esercizi 2).
L'algoritmo p-1 di Pollard (vedi Crandall-Pomerance, Sez.5.4 e Nota su "Pollard p-1;")
Curve ellittiche su Z: equazione di Weierstrass (vedi Crandall-Pomerance Cap.7, Sez.7.1, e soluzioni Esercizi 5: n.1).

Esercizi2 2009, n.1
Esercizi3 2010.

Settima settimana:
Curve ellittiche su Z: equazione di Weierstrass (vedi Crandall-Pomerance Cap.7, Sez.7.1, e soluzioni Esercizi 5: n.1).
Costruzione geometrica della somma fra punti di una curva ellittica su R. (vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 9-19 e soluzioni Esercizi 5).
Curve ellittiche su Z_p (con p primo). Teorema di Hasse. Struttura del gruppo dei punti di una curva ellittica su Z_p. Esempi ed esercizi. (vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 89-91;
Crandall-Pomerance, Cap.7, Sez.7.1, 7.2, 7.3; soluzioni Esercizi 5).

Ottava settimana:
Esempi ed esercizi sulle curve ellittiche su Z_p (con p primo).
Il metodo di fattorizzazione con le curve ellittiche di Lenstra: descrizione dell'algoritmo.

(vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 179-184; Crandall-Pomerance, Cap.7, Sez.4;
Introduzione di: H. Lenstra: Factoring integers with elliptic curves, Annals of Math. 126, (1987) 649-673 pdf
Nota sul metodo delle curve ellittiche).

Nona settimana:
Il metodo di fattorizzazione con le curve ellittiche di Lenstra: analisi della complessita' probabilistica. La seconda fase. Esperimenti con PARI/GP.
(vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 179-184; Crandall-Pomerance, Cap.7, Sez.4;
Nota sul metodo delle curve ellittiche).

Decima settimana:
Il logaritmo discreto in Z_p^*. Definizione e proprieta'. Esempi di determinazione del logaritmo discreto col calcolo dell'indice.
(vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 179-184;
Esercizi6 (svolti)).

Undicesima settimana:
Il logaritmo discreto in Z_p^*. Il calcolo dell'indice: l'algoritmo. Complessita' probabilistica del calcolo dell'indice. Esempi con Pari/Gp.
(vedi Crandall-Pomerance, Cap.6, Sez.6.4.1;).

Dodicesima settimana:
L'algoritmo Baby-step-Giant-step (vedi Crandall-Pomerance, Cap.5, Sez.5.3;).
Il logaritmo discreto su curve ellittiche (cenni).
Applicazioni del logaritmo discreto alla crittografia: Diffie-Hellmann-Merkle key exchange, ElGamal encription.
(vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 133-137).

Tredicesima settimana:
Il crivello quadratico per la fattorizzazione di numeri interi: descrizione dell'algoritmo.
Studio di alcuni esempi.
(vedi Crandall-Pomerance, Cap.6, Sez.6.1;).

Quattordicesima settimana:
Il crivello quadratico per la fattorizzazione di numeri interi: analisi della complessita'.
Esercizi3 2009
Esercizi4 2010

Quindicesima settimana:
Certificati di primalita': criterio di Pocklington.
(vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 184-187
Esercizi5 2010).

Sedicesima settimana:
Certificati di primalita': algoritmo di Goldwasser-Kilian.
(vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 184-187;
Crandall-Pomerance, sezione 7.6, 7.6.1)