Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2017-2018
Primo semestre.
Diario delle lezioni di Teoria Elementare dei Numeri

Prima settimana (26 e 29 settembre 2017):
Richiami sul calcolo in Z_n. 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 Z_n: somma e prodotto. Caratterizzazione degli elementi di Z_n che ammettono inverso moltiplicativo. Stima della complessita' dell'algoritmo di Euclide.

• vedi: Soluzioni Esercizi-svolti n.1.
• Per i prerequisiti vedi Nota1 e Nota2.
  
  

  Seconda settimana (3 e 6 ottobre 2017):
  Stima della complessita' del calcolo dell'inverso moltiplicativo di una classe resto in Z_n mediante l'agoritmo di Euclide esteso. La funzione φ di Eulero. Il criptosistema RSA. Un esempio con PARI/GP. Il Piccolo Teorema di Fermat.

  • Nota sulla funzione φ di Eulero;
  • R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica, Didattica delle Scienze 137 (1988), 48–54.
    
  
  

  Terza settimana (10 e 13 ottobre 2017):
  Il Piccolo Teorema di Fermat. I numeri di Carmichael. Il teorema di Miller-Rabin. Il test di primalita' di MiIler-Rabin. La complessita' di un ciclo del test di Miller-Rabin. Il Teorema dei Numeri Primi: significato e conseguenze. Complessita' probabilistica dell'individuazione di un primo di grandezza prefissata. L'algoritmo di fattorizzazione per divisioni successive e la sua complessita'.

  • Nota2, Appendice (test di Miller-Rabin);
  • per gli esperimenti con PARI/GP, vedi: MRsteps txt
  • Nota sul Teorema dei Numeri Primi di Chebyshev;
  • Crandall-Pomerance, Thm.1.1.4; soluzioni Esercizi-svolti n.2.
  
  

  Quarta settimana (17 e 20 ottobre 2017):
  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. Gli interi B-smooth: definizione.

  • Nota su Pollard ρ.
  
  

  Quinta settimana (24 e 27 ottobre 2017):
  Interi B-smooth: la funzione di Dickman. L'algoritmo p-1 di Pollard e la sua complessita' probabilistica. Esempi con PARI/GP. Esercizi.

  • Crandall-Pomerance, Sect.1.4.5, e soluzioni Esercizi-svolti 2.
  • Crandall-Pomerance, Sez.5.4.
  • Nota su Pollard p-1.
  
  

  Sesta settimana (7 e 10 novembre 2017):
  Introduzione alle curve ellittiche: equazione di Weierstrass di una curva ellittica su un campo K diverso da Z ₂ e Z ₃. 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).

  • Crandall-Pomerance, Cap.7, Sez.7.1; soluzioni Esercizi-svolti n.5: n.1-5.
  • L. Washington, Cap.4, sez. 4.1.
  
  

  Settima settimana (14 e 17 novembre 2017):
  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. Complessita' probabilistica dell'algoritmo ECM. Esempi con PARI/GP.
  

  • Larry Washington, Elliptic curves - Number theory and Criptography, pag. 9-19; pag. 89-91; pag. 179-184;
  • Crandall-Pomerance, Cap.7, Sez.7.1, 7.2, 7.3, 7.4;
  • Introduzione di: H. Lenstra, Factoring integers with elliptic curves, Annals of Math. 126, (1987) 649-673 pdf
    
  • Nota sul metodo delle curve ellittiche.
  
  

  Ottava settimana (21 e 24 novembre 2017):
  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)

  • Crandall-Pomerance, Cap.6, Sez.6.4.1;
  • Nota "Calcolo dell'indice...."; Esercizi-svolti n.6.
  
  

  Nona settimana (28 novembre e 1 dicembre 2017):
  Complessita' probabilistica dell'I.C.. L'algoritmo Baby-Step-Giant-Step per la risoluzione del logaritmo discreto in un gruppo ciclico arbitrario. Complessita' dell'algoritmo BS-GS. Diffie-Hellman-Merkle key exchange. Il criptosistema a chiave pubblica El Gamal. Esempi ed esercizi.

  • Nota su "Applicazioni del logaritmo discreto alla criptografia".
  
  

  Decima settimana (5 dicembre 2017):
  Introduzione al crivello quadratico: dalle relazioni alle congruenze fra quadrati modulo n (continua).

  • Crandall-Pomerance, Cap.6, Sez.6.1.1, 6.1.2.
  • Nota ``Crivello quadratico".
  
  

  Undicesima settimana (12 & 15 dicembre 2017):
  Crivello quadratico: la fase di sieving. Stima della complessita' probabilistica del crivello quadratico.

  • Crandall-Pomerance, Cap.6, Sez.6.1.1, 6.1.2.
  • Nota ``Crivello quadratico".
  
  

  Dodicesima settimana (19 & 22 dicembre 2017):
  Certificati di primalita': il test di Pocklington. Elliptic Curve Primality Proving (ECPP): test di primailta' di Goldwasser-Kilian.

  • L. Washington, Sez. 7.2.
  • Nota ``Certificati di primalita'".
  
  

  Tredicesima settimana (9 & 12 gennaio 2018):
  Esercizi assortiti e ripasso.

  
  

  Quattordicesima settimana (16 & 20 gennaio 2018):
  Esercizi assortiti e ripasso.







Per comunicare con me via skype: mettersi in contatto con geageometria
(magari avvisarmi prima che ci mettiamo d'accordo...).

N.B.
La nota1 - "Aritmetica sui numeri interi" contiene i prerequisiti su massimo comun divisore, algoritmo di Euclide, congruenze.
La nota2 - "Gruppi, anelli, campi e applicazioni" contiene in particolare i prerequisiti sull'anello Z_n.