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



Prima settimana:
Fattorizzazione e primalita': richiami sul criptosistema RSA.
Complessita' delle operazioni aritmetiche sugli interi: somma, sottrazione, prodotto, divisione con resto, massimo comun divisore con l'algoritmo di Euclide, elevamento ad una potenza intera.
Complessita' delle operazioni aritmetiche su Zn : somma, prodotto, elevamento ad una potenza intera.

  • R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica, Didattica delle Scienze 137 (1988), 48–54.
  • Soluzioni Esercizi-svolti n.1.


    Seconda settimana:
    Gruppi: definizione, proprieta' ed esempi. Gruppi abeliani finiti: il gruppo additivo Zn e il gruppo moltiplicativo Z*n (vedi nota2).
    La complessita' del calcolo di un inverso in Z*n (vedi soluzioni Esercizi-svolti n.1).
    La funzione φ di Eulero (vedi nota sulla funzione φ di Eulero).
    Il Teorema di Lagrange, il Piccolo Teorema di Fermat (vedi nota2).

  • Esercizi-svolti n.3: esercizi 1--9;
  • Esercizi 2011 n.1: esercizi 1--8 (se necessario, usare PARI/GP).


    • Terza settimana:
    Richiami sull'anello Zn e sul campo Zp (con p primo). Conseguenze del Piccolo Teorema di Fermat. I numeri di Carmichael. (vedi nota2 - Gruppi, anelli, campi e applicazioni).
    Il test di primalita' di Miller-Rabin (vedi nota2, Appendice). Esempi con PARI/GP.
    Il Teorema dei Numeri Primi (vedi Crandall-Pomerance, Thm.1.1.4; soluzioni Esercizi-svolti n.2).

  • Esercizi-svolti n.3: esercizi 10--19;
  • Esercizi 2011 n.2 (se necessario, usare PARI/GP).


    • Quarta settimana:
    Il paradosso del compleanno. Il metodo di fattorizzazione ρ di Pollard, il Lemma di Floyd;
    la complessita' probabilistica del metodo ρ di Pollard. (vedi Crandall-Pomerance, sect. 5.2.1; Nota su Pollard ρ). Esempi con PARI/GP.

  • Esercizi-svolti n.4: esercizi 1--3;
  • Esercizi 2011 n.3: esercizi 1--9.


    • Quinta settimana:
    Isomorfismi di gruppi. Ordine di un elemento in un gruppo. Gruppi ciclici. Esempi.

  • Esercizi 2011 n.4.


    • Sesta settimana:
    - Dimostrazione del teorema della radice primitiva: se p e' primo, Z*p e' ciclico. Inoltre in Z*p ci sono φ(d) elementi di ordine d. Esempi ed esercizi. (vedi Nota sulle radici primitive modulo p).
    - Interi B-smooth, funzione di Dickman (vedi Crandall-Pomerance, Sect.1.4.5, e soluzioni Esercizi 2).
    - Introduzione all'algoritmo p-1 di Pollard (vedi Crandall-Pomerance, Sez.5.4 e Nota su "Pollard p-1;")

  • Esercizi-svolti n.3: esercizi 20--24;
  • Esercizi-svolti n.4 dal sito EAL2009.


    • Settima settimana:
    - Interi B-smooth e algoritmo p-1 di Pollard: esperimenti con PARI/GP.
    - Introduzione alle curve ellittiche: equazione di Weierstrass ; esempi di curve ellittiche su Z p, con p primo (vedi Crandall-Pomerance Cap.7, Sez.7.1, e soluzioni Esercizi-svolti n.5: n.1).

  • Esercizi 2011 n.3: esercizi dal n.9 in poi.


    • Ottava settimana:
    - Costruzione geometrica della somma fra punti di una curva ellittica su R. Curve ellittiche su Zp (con p primo). Teorema di Hasse. Struttura del gruppo dei punti di una curva ellittica su Zp
    - Il metodo di fattorizzazione con le curve ellittiche ECM di Lenstra: descrizione dell'algoritmo.

    (vedi 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
    Soluzioni Esercizi-svolti 5, n.1,2; Nota sul metodo delle curve ellittiche).

  • Esercizi-svolti n.5.


    • Nona settimana:
    - ECM: stima della complessita' probabilistica (vedi: Nota sul metodo delle curve ellittiche).
    - ECM fase 1 e fase 2: esperimenti con PARI/GP.

  • Esercizi 2011 n.5.


    • Decima settimana:
    - Il logaritmo discreto. Introduzione al calcolo dell'indice.
    - Il calcolo dell'indice: l'algoritmo generale.

  • Crandall-Pomerance, Cap.6, Sez.6.4.1; Esercizi-svolti n.6.


    • Undicesima settimana:
    - Il Il calcolo dell'indice: la stima della complessita' probabilistica.
    L'algoritmo baby-step-giant-step per la risoluzione del logaritmo discreto in un gruppo ciclico.
    - Applicazioni del logaritmo discreto alla crittografia: Diffie-Hellman-Merkle key-exchange, El Gamal encryption.

  • Crandall-Pomerance, Cap.5, Sez.5.3;
  • Larry Washington, Elliptic curves - Number theory and Criptography, pag. 133-137
  • Note su "Calcolo dell'indice" e su "Applicazioni del logaritmo discreto alla criptografia".


    • Dodicesima settimana:
    - Il crivello quadratico per la fattorizzazione di numeri interi: introduzione all'algoritmo.
    - Il crivello quadratico: descrizione del crivello. Esempi con PARI/GP (continua).

  • Crandall-Pomerance, Cap.6, Sez.6.1; Nota ``Crivello quadratico".
  • Esercizi-svolti n.7.


    Tredicesima settimana:
    - Il crivello quadratico: analisi dettagliata di un esempio.

  • Vedi "Esempio di fattorizzazione etc..." + Spiegazione.


    Quattordicesima settimana:
    - Il crivello quadratico: stima probabilistica della complessit\`a.
    - Preliminari al criterio di Pocklington. Esercizi.

  • Nota ``Crivello quadratico".
  • Esercizi-svolti n.8.


    • Quindicesima settimana:
    - Il criterio di Pocklington.
    - Certificati di primalita'. Esempi con PARI/GP.

  • Esercizi-svolti n.8.


    • Sedicesima settimana:
    - Cenni all'algoritmo di Goldwasser-Kilian.
    - Esempi ed esercizi di ricapitolazione.


    Fine







    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 Zn.