Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2018-2019
Primo semestre.
Diario delle lezioni di Teoria Elementare dei Numeri
Prima settimana (25 e 28 settembre 2018):
Complessita' polinomiale, esponenziale e subesponenziale di un algritmo (con input di interi).
Complessita' delle operazioni aritmetiche sugli interi: somma, sottrazione, prodotto, divisione con resto.
Richiami sul calcolo in Zn. Complessita' delle operazioni aritmetiche su Zn: somma e prodotto.
Complessita' dell'elevamento a potenza in Z ed in in Zn. Stima della complessita' dell'algoritmo di Euclide.
Seconda settimana (2 e 5 ottobre 2018):
Stima della complessita' del calcolo dell'inverso moltiplicativo di una classe resto in Zn mediante l'agoritmo di Euclide esteso.
La funzione φ di Eulero. Il criptosistema RSA. Un esempio con PARI/GP.
Terza settimana (9 e 12 ottobre 2018):
Il criptosistema RSA: i moduli N=pq di clienti distinti devono essere diversi e non devono avere fattori in comune. Il Teorema dei Numeri Primi: significato e conseguenze. Complessita' probabilistica dell'individuazione di un primo di grandezza prefissata.
Il Piccolo Teorema di Fermat. Il teorema di Miller-Rabin. Il test di primalita' di MiIler-Rabin. I numeri di Carmichael. La complessita' di un ciclo del test di Miller-Rabin. Complessita' probabilistica della costruzione di uno pseudoprimo di grandezza prefissata.
Quarta settimana (16 e 19 ottobre 2018):
L'agoritmo 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 (23 ottobre 2018):
Interi B-smooth: definizione, stima della loro distribuzione asintotica mediante il teorema di Dickman.
Sesta settimana (30 ottobre 2018):
L'algoritmo di fattorizzazione p-1 di Pollard.
Settima settimana (6 e 9 novembre 2018):
Il terorema di Lagrange per gruppi abeliani finiti. Ordine di un elemento. L'ordine di un elemento divide l'ordine del gruppo.
L'algoritmo p-1 di Pollard: complessita' probablistica. Esempi con PARI/GP.
Ripasso di algebra: gruppi abeliani finiti. Gruppi ciclici. Isomorfismi di gruppi. Esempi.
Teorema della radice primitiva: Il gruppo Zp*, con p primo, e' ciclico. Enunciato e significato.
Ottava settimana (13 e 16 novembre 2018):
Dimostrazione del Teorema della radice primitiva.
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.
Nona settimana (20 e 23 novembre 2018):
Formule algebriche per somma e duplicazione su una curva ellittica. Curve ellittiche su Z p, con p>>0 primo: l'intervallo di Hasse;
la struttura del gruppo E(Z p) (cenni).
Il metodo di fattorizzazione con le curve ellittiche di Lenstra: fase uno e fase due.
Decima settimana (27 e 30 novembre 2018):
La complessita' di un ciclo della fase 1. La fase due.
Complessita' probabilistica dell'algoritmo ECM. Esempi con PARI/GP.
Il logaritmo discreto: definizione e proprieta' del logaritmo discreto su un gruppo ciclico.
Criterio della radice primitiva in Z*p.
Undicesima settimana (4 e 7 dicembre 2018):
Criterio della radice primitiva in Z*p. Index Calculus in Z*p: l'algoritmo. Esempi. La complessita' probabilistica dell'Index Calculus.
L'algoritmo naif per risolvere il logaritmo discreto e la sua complessita'.
L'algoritmo BabyStep-GiantStep. Esempi.
Dodicesima settimana (11 dicembre 2018):
Stima della complessita' dell'algoritmo BabyStep-GiantStep. Diffie-Hellman-Merkle key exchange. Il criptosistema a chiave pubblica El Gamal. Esempi.
Tredicesima settimana (18 e 21 dicembre 2018):
Introduzione al crivello quadratico. L'algoritmo (modello base). Un esempio.
Quattordicesima settimana (8 e 11 gennaio 2019):
Stima della complessita' del crivello quadratico. Il criterio di primalita' di Pocklington. Esempi di applicazione del test di primalita' di Pocklington. Il criterio di primalita' di Goldwasser-Kilian. Cenni alla variante di Atkin-Morain (cntinua).
Quindicesima settimana (8 e 11 gennaio 2019):
Stima della complessita' del crivello quadratico. Il criterio di primalita' di Pocklington. Esempi di applicazione del test di primalita' di Pocklington. Il criterio di primalita' di Goldwasser-Kilian. ECPP basato sul criterio di Goldwasser-Kilian. Cenni alla variante di Atkin-Morain (continua).
Sedicesima settimana (15 e 18 gennaio 2019):
ECPP basato sul criterio di Goldwasser-Kilian e la variante di Atkin-Morain: ulteriori dettagli. L'algoritmo di Schoof per contare i punti di una curva ellittica su Zp. Esercizi di ricapitolazione.