Prima settimana (24 e 27 settembre 2019):
- Il criptosistema RSA. Complessita' polinomiale, esponenziale e subesponenziale di un algoritmo (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.
- R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica,
Didattica delle Scienze 137 (1988), 48–54.
- vedi: Soluzioni Esercizi-svolti n.1.
- Per i prerequisiti vedi Nota1 e Nota2.
Seconda settimana (1 e 4 ottobre 2019):
- Classi resto in Zn che ammettono inverso moltiplicativo. Calcolo dell'inverso mediante l'agoritmo di Euclide esteso. Stima della complessita' dell'algoritmo di Euclide esteso e del calcolo di un inverso modulo n.
- La funzione φ di Eulero. Gruppi: definizione ed esempi.
- vedi: Soluzioni Esercizi-svolti n.1.
- Nota sulla funzione φ di Eulero;
Terza settimana (8 e 11 ottobre 2019):
- Il Teorema di Lagrange. Il Piccolo Teorema di Fermat. I numeri di Carmichael. Il teorema di Miller-Rabin.
- Il Test di primalita' di Miller-Rabin e la sua complessita'. Il teorema dei numeri primi (cenni). Complessita' probabilistica della costruzione di uno pseudoprimo di grandezza prefissata. Il criptosistema RSA: i moduli N=pq di clienti distinti devono essere diversi e non devono avere fattori in comune. Esempi con PARI/GP.
- Nota2, Appendice (test di Miller-Rabin);
- Nota sul Teorema dei Numeri Primi di Chebyshev;
Quarta settimana (15 e 18 ottobre 2019):
- Numeri primi. Il teorema dei numeri primi: conseguenze. L'algoritmo di fattorizzazione per divisioni successive e la sua complessita'. Numeri B-smooth. La funzione di Dickman.
- Il paradosso del compleanno. Il metodo di fattorizzazione ρ di Pollard.
Il Lemma di Floyd: conseguenze.
Esempi con PARI/GP.
- Crandall-Pomerance, Sect.1.1.5, e soluzioni Esercizi-svolti 2.
- Crandall-Pomerance, Sect.1.4.5, e soluzioni Esercizi-svolti 2.
- Nota sul Teorema dei Numeri Primi di Chebyshev;
- Nota sull'algoritmo ρ di Pollard.
- Crandall-Pomerance, Sez.5.2.1.
Quinta settimana (22 e 25 ottobre 2019):
- Il Lemma di Floyd: dmostrazione. La complessita' probabilistica del metodo ρ di Pollard. Esempi con PARI/GP.
- Gruppi: ordine di un elemento. Gruppi: gruppi ciclici. Esempi ed esercizi.
- Ordine di un elemento e teorema di Lagrange. Omomorfismi,
isomorfismi. Lemma di Gauss.
- Nota sull'algoritmo ρ di Pollard.
- Nota sulla radice primitiva.
Sesta settimana (29 ottobre 2019):
- Il teorema della radice primitiva: dimostrazione.
-
- Nota sulla radice primitiva.
Settima settimana (5 e 8 novembre 2019):
- Criterio della radice primitiva. Il logaritmo discreto in Zp*, e in generale in un gruppo ciclico: definizione e proprieta'. Esempi di calcolo del logaritmo discreto.
- Il metodo naif per la risoluzione del logaritmo discreto e la sua complessita'. Il calcolo dell'indice (Index calculus) in Zp*. Diffie-Hellman-Merkle key-exchange.
- Nota sul "calcolo dell'indice".
Ottava settimana (12 e 15 novembre 2019):
- Stima della complessita' probabilistica del "Calcolo dell'indice" per la risoluzione del logaritmo discreto in Zp*. Il criptosistema El Gamal. Esercizi. L'algoritmo Baby-Step-Giant-Step per la risoluzione del logaritmo discreto in un gruppo ciclico arbitrario.
- Esercizi.
- Nota sul "Calcolo dell'indice".
- Nota su "Baby-Step-Giant-Step"
Nona settimana (19 e 22 novembre 2019):
- Il metodo di fattorizzazione p-1 di Pollard e la sua complessita' computazionale probabilistica. Esempi con PARI/GP.
- Curve ellittiche: introduzione. Equazione di Weierstrass di una curva ellittica su un campo K diverso da Z 2 e Z 3. Esempi di curve ellittiche su Zp. Curve ellittiche regolari su R: discriminante non nullo ed esistenza della retta tangente alla curva in ogni punto.
- Nota sul "Pollard p-1".
- Crandall-Pomerance, Cap.7, Sez.7.1; soluzioni Esercizi-svolti n.5: n.1-5.
- L. Washington, Cap.4, sez. 4.1.
- Curve ellittiche: esercizi svolti.
Decima settimana (26 e 29 novembre 2019):
- Curve ellittiche: somma e duplicazione di punti. Dalla costruzione geometrica alle formule algebriche. Curve ellittiche su Zp. Teorema di Hasse. Cenni alla struttura del gruppo E(Zp). Esempi.
- Introduzione al metodo di fattorizzazione con le curve ellittiche. Fase 1.
- Crandall-Pomerance, Cap.7, Sez.7.1; soluzioni Esercizi-svolti n.5: n.1-5.
- L. Washington, Cap.4, sez. 4.1.
- Introduzione di: H. Lenstra,
Factoring integers with elliptic curves, Annals of Math. 126, (1987) 649-673 pdf
- Nota sul metodo di fattorizzazione con le curve ellittiche.
- Curve ellittiche: esercizi svolti.
Undicesima settimana (3 dicembre e 6 dicembre 2019):
- Il metodo di fattorizzazione con le curve ellittiche: fase 1 e fase 2.
- Stima della complessita' probabilistica di ECM.
- Crandall-Pomerance, Cap.7, Sez.7.4;
- Introduzione di: H. Lenstra,
Factoring integers with elliptic curves, Annals of Math. 126, (1987) 649-673 pdf
- Nota sul metodo di fattorizzazione con le curve ellittiche.
Dodicesima settimana (10 dicembre e 13 dicembre 2019):
- Introduzione al crivello quadratico.
- Lezione cancellata per maltempo.
- Crandall-Pomerance, Cap.6, Sez.6.1.1, 6.1.2.
- Nota "Crivello quadratico".
Tredicesima settimana (17 dicembre e 20 dicembre 2019):
- Il crivello quadratico: l'algoritmo. Esempi.
- Complessita' probabilistica del crivello quadratico.
- Crandall-Pomerance, Cap.6, Sez.6.1.1, 6.1.2.
- Nota "Crivello quadratico".
- Nota "Esempio di Crivello quadratico".
Quattordicesima settimana (7 e 10 gennaio 2020):
- Test di primalita' di Pocklington. Esempi.
- Test di primalita' di Goldwasser-Kilian.
- Nota "Pocklington e Goldwasser-Kilian" ed "Esempi".
Quindicesima settimana (14 e 17 gennaio 2020):
- Esempi ed esercizi.
- Esempi ed esercizi.