Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2009-2010
Primo semestre (emisemestre 2).
Diario delle lezioni di di Teoria Elementare dei Numeri / Crittografia (parte 1)

Prima settimana:
Il criptosistema RSA (vedi articolo di Schoof su Didattica della Matematica). Fattorizzazione e primalita'.
Complessita' delle operazioni aritmetiche sugli interi, dell'algoritmo di Euclide, delle operazioni aritmetiche sugli interi modulo n (vedi soluzioni Esercizi 1).
Richiami sull'anello Z_n. Il test di primalita' di Miller-Rabin (vedi nota2, Appendice). Esempi con PARI/GP.

Seconda settimana:
Il Teorema dei Numeri Primi (vedi Crandall-Pomerance, Thm.1.1.4; soluzioni Esercizi 2).
Complessita' dell'algoritmo di Miller-Rabin e del metodo di fattorizzazione per tentativi (vedi soluzioni Esercizi 1).
Il paradosso del compleanno. L'algoritmo di fattorizzazione di Pollard &rho. Il Lemma di Floyd (vedi Crandall-Pomerance, sect. 5.2.1; Nota su Pollard &rho). Esempi con PARI/GP.

Terza settimana:
Complessita' probabilistica dell'algoritmo di fattorizzazione &rho di Pollard (vedi nota su Pollard &rho). Esempi con PARI/GP.
Gruppi abeliani: esempi. Gruppi abeliani finiti: Z_n e Z^*_n (vedi nota2). La funzione &phi di Eulero (vedi nota sulla funzione &phi di Eulero).
Prodotto diretto di gruppi. Gruppi ciclici finiti. Generatori di un gruppo ciclico finito. Teorema di Lagrange. Piccolo Teorema di Fermat. Calcolo di grosse potenze modulo n. Ordine di un elemento in un gruppo abeliano finito (vedi nota2).

Quarta 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 &phi(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).
Numeri B-smooth: la funzione di Dickman (vedi Crandall-Pomerance, Sect.1.4.5, e soluzioni Esercizi 2).

Quinta settimana:
L'algoritmo p-1 di Pollard (vedi Crandall-Pomerance, Sez.5.4 e Nota su "Pollard p-1;")
Curve ellittiche. Equazione di Weierstass. 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. Esempi ed esercizi. (vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 89-91;
Crandall-Pomerance, Cap.7, Sez.1,2,3; soluzioni Esercizi 5).

Sesta settimana:
- Il metodo delle curve ellittiche di Lenstra: descrizione dell'algoritmo;
- stima della complessita';
- la seconda fase.
(vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 179-184; Crandall-Pomerance, Cap.7, Sez.4; Nota sul metodo delle curve ellittiche).

Settima settimana:
Il logaritmo discreto in Z_p^*. Il calcolo dell'indice in Z_p^*. Il calcolo dell'indice: stima della complessita' (vedi Crandall-Pomerance, Cap.6, Sez.6.4.1;).
L'algoritmo Baby-step-Giant-step (vedi Crandall-Pomerance, Cap.5, Sez.5.3;).
Il logaritmo discreto su curve ellittiche (cenni).
Applicazioni alla crittografia: Diffie-Hellmann-Merkle key exchange, ElGamal encription. Esempi ed esercizi.
(vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 133-137).

Ottava settimana: Il crivello quadratico per la fattorizzazione di numeri interi. Stima della complessita' (vedi Crandall-Pomerance, Cap.6, Sez.6.1;).
Esperimenti con PARI/GP.