Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2016-2017
Primo semestre.
Diario delle lezioni di Teoria Elementare dei Numeri
Prima settimana (4 e 7 ottobre):
Illustrazione del programma del corso. Richiami sul calcolo in Zn. Complessita' polinomiale e complessita' esponenziale di un algoritmo. Complessita' delle operazioni aritmetiche sugli interi: somma, sottrazione, prodotto, divisione con resto.
Complessita' delle operazioni aritmetiche su Zn: somma e prodotto. Caratterizzazione degli elementi di Zn che ammettono inverso moltiplicativo. Stima della complessita' dell'algoritmo di Euclide e del calcolo dell'inverso moltiplicativo di una classe resto in Zn.
Seconda settimana (11 e 14 ottobre):
La funzione φ di Eulero. La complessita' dell'elevamento a potenza in Z e in Zn col metodo delle quadrature successive. Il Piccolo Teorema di Fermat.
Il criptosistema RSA. Un esempio con PARI/GP.
Terza settimana (18 e 21 ottobre):
Piccolo Teorema di Fermat e numeri di Carmichael. Il Teorema di Miller-Rabin. Il test di primalita' di Miller-Rabin. La complessita' di un ciclo del test di Miller-Rabin. Il teorema dei Numeri Primi. Applicazioni ed esempi: individuazione di grossi primi. Complessita' probabilistica dell'individuazione di un primo di ordine di grandezza prefissata.
Quarta settimana (25 e 28 ottobre):
Cenni alla dimostrazione del teorema dei numeri primi di Chebyshev. L'algoritmo di fattorizzazione per divisioni successive e la sua complessita'. Il paradosso del compleanno. Il metodo di fattorizzazione ρ di Pollard.
Il Lemma di Floyd.
La complessita' probabilistica del metodo ρ di Pollard. Esempi con PARI/GP.
Quinta settimana (4 novembre):
Dimostrazione del Lemma di Floyd. Ulteriori esempi con PARI/GP. Gruppi: definizione e proprieta'. Gruppi abeliani finiti. Esempi: (Zn,+) e (Z*p,*); Prodotto di gruppi. Il Teorema di Lagrange. Ordine di un elemento in un gruppo.
Sesta settimana (8 e 11 novembre):
L'ordine di un elemento divide l'ordine del gruppo. Gruppi ciclici e generatori. Esempi di gruppi ciclici finiti: il gruppo additivo Zn, gruppi finiti di ordine primo,
il prodotto ZnxZm, con gcd(m,n)=1.
Isomorfismi di gruppi. Struttura dei gruppi abeliani finiti. Due lemmi preliminari alla dimostrazione del Teorema della Radice Primitiva: formula di Gauss e ordine della potenza di un elemento di
ordine a. Il Teorema della Radice Primitiva.
Settima settimana (15 e 18 novembre):
Radici di un polinomio a coefficienti in Zp, con p primo.
Ulteriori osservazioni sui gruppi abeliani finiti.
Interi B-smooth, funzione di Dickman.
L'algoritmo p-1 di Pollard e la sua complessita' probabilistica. Esempi con PARI/GP.
Ottava settimana (22 e 25 novembre):
Introduzione alle curve ellittiche: equazione di Weierstrass di una curva ellittica su un campo K diverso da Z 2 e Z 3.
Curve ellittiche su R: implicazioni della condizione "discriminante non nullo"; costruzione geometrica della somma di due punti e del doppio di un punto.
Curve ellittiche su Z p, con p>>0 primo: l'intervallo di Hasse;
la struttura del gruppo E(Z p) (cenni).
Nona settimana (29 novembre e 2 dicembre):
Introduzione al metodo di fattorizzazione con le curve ellittiche ECM di Lenstra: descrizione della fase 1 di un ciclo dell'algoritmo. Esempi con PARI/GP.
La complessita' di un ciclo della fase 1. La fase due.
Decima settimana (6 dicembre):
Complessita' probabilistica dell'algoritmo ECM. Esempi con PARI/GP. Esercizi assortiti.
Undicesima settimana (13 e 16 dicembre):
Il logaritmo discreto: definizione e proprieta' del logaritmo discreto su un gruppo ciclico.
Criterio della radice primitiva in Z*p. Index Calculus in
Z*p. Complessita' probabilistica dell'I.C. (-continua)
Dodicesima settimana (20 e 23 dicembre):
Complessita' probabilistica dell'I.C.: parametri asintotici ideali. Il logaritmo discreto su un gruppo ciclico
arbitrario. L'algoritmo Baby-Step-Giant-Step. Complessita' dell'algoritmo BS-GS. Diffie-Hellman-Merkle key exchange. Il criptosistema a chiave pubblica El Gamal. Esempi.
Tredicesima settimana (10 e 13 gennaio):
Introduzione all'algoritmo di Schoof per contare in punti di una curva ellittica su Z p.
Introduzione al crivello quadratico: dalle relazioni alle congruenze fra quadrati modulo n (continua).
Quattordicesima settimana (17 e 20 gennaio):
Quindicesima settimana (24 e 27 gennaio):
Certificati di primalita': il criterio di Pocklington. Il test di Pocklington-Lehmer.
Elliptic Curve Primality Proving (ECPP): il test di Goldwasser-Kilian. Cenni all'algoritmo di Atkin-Morain.
