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

Prima settimana:
Il criptosistema RSA. Fattorizzazione e primalita' (vedi articolo di Schoof su Didattica della Matematica).
Complessita' delle operazioni aritmetiche sugli interi, dell'algoritmo di Euclide e delle operazioni aritmetiche sugli interi modulo n (vedi soluzioni Esercizi 1).
Il test di primalita' di Miller-Rabin (vedi nota2: appendice).
Complessita' del test di primalita' di Miller-Rabin (vedi soluzioni Esercizi 1).
La distribuzione dei numeri primi (vedi Crandall-Pomerance, Thm.1.1.4, pag. 9 e soluzioni Esercizi 2).

Seconda settimana:
Fattorizzazione per tentativi.
Il paradosso del compleanno e il metodo di fattorizzazione "Pollard ρ". Complessita' del metodo "Pollard ρ" (vedi Crandall-Pomerance, pag.195-197 e Nota su "Pollard ρ").
Esperimenti con PARI/GP.

Terza settimana:
Gruppi, anelli, campi. Gruppi abeliani finiti. I gruppi Z_n e Z^*_n (vedi nota2).
La funzione &phi di Eulero (vedi nota sulla funzione &phi di Eulero).
Il teorema di Lagrange, il Piccolo Teorema di Fermat. Gruppi ciclici. Ordine di un elemento. (vedi nota2).
Esistenza di una radice primitiva in Z^*_p (con p primo). Caratterizzazione di una radice primitiva. (vedi Nota sulle radici primitive modulo p).
Esempi ed esercizi.
Numeri B-smooth (vedi Crandall-Pomerance, pag. 44-45 e soluzioni Esercizi 2).
Il metodo di fattorizzazione p-1 di Pollard. (vedi Crandall-Pomerance, pag. 202-203 e Nota su "Pollard p-1;")

Quarta settimana:
Curve ellittiche su R. Equazione di Weierstass. Costruzione geometrica della somma fra punti di una curva ellittica (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).

Quinta settimana:
Il metodo delle curve ellittiche di Lenstra (vedi Larry Washington, Elliptic curves - Number theory and Criptography, pag. 179-184; Crandall-Pomerance, Cap.7, Sez.4).

Sesta settimana:
Il metodo delle curve ellittiche di Lenstra: stima della complessit\`a. La seconda fase. Esperimenti con PARI/GP. (vedi Crandall-Pomerance, Cap.7, Sez.4;).
Il logaritmo discreto in Z_p^*. 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).

Settima settimana:
Il logaritmo discreto su curve ellittiche (cenni). L'algoritmo Baby-step-Giant-step (vedi Crandall-Pomerance, Cap.5, Sez.5.3;).
Il calcolo dell'indice in Z_p^*. Il calcolo dell'indice: stima della complessita' (vedi Crandall-Pomerance, Cap.6, Sez.6.4.1;).

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