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



Prima settimana:
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.

  • vedi: Soluzioni Esercizi-svolti n.1.


    Seconda settimana:
    La complessita' del calcolo di un inverso in Z*n ( vedi: soluzioni Esercizi-svolti n.1).
    Il criptosistema RSA. Esempi con PARI/GP.
    Il test di primalita' di Miller-Rabin (vedi: nota2, Appendice).
    Il Teorema dei Numeri Primi (cenni) (vedi: Crandall-Pomerance, Thm.1.1.4; soluzioni Esercizi-svolti n.2).

  • R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica, Didattica delle Scienze 137 (1988), 48–54.


    Terza settimana:
    Il Teorema dei Numeri Primi (continua). La complessita' del test di Miller-Rabin. Fattorizzazione e primalita': complessita' a confronto.
    Ulteriori richiami su Zn e su Z*p. La funzione φ di Eulero (vedi nota sulla funzione φ di Eulero). Gruppi: definizione e proprieta'.
    Gruppi abeliani finiti: il gruppo additivo Zn e il gruppo moltiplicativo Z*p (vedi nota2).

  • Esercizi1 2012-2013


    • Quarta settimana:
    Il teorema di Lagrange e il Piccolo Teorema di Fermat (vedi nota2).
    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.


    Quinta settimana:
    L'anello Zn e il campo Zp (con p primo). Ordine di un elemento in un gruppo. 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 (vedi nota2).
    Il teorema della radice primitiva: se p e' primo, il gruppo moltiplicatiovo Z*p e' ciclico. Inoltre in Z*p ci sono φ(d) elementi di ordine d (vedi Nota sulle radici primitive modulo p).

  • Esercizi2 2012-2013


    • Sesta settimana:
    Esempi ed ed esercizi sui gruppi.
    Interi B-smooth, funzione di Dickman (vedi Crandall-Pomerance, Sect.1.4.5, e soluzioni Esercizi 2).
    L'algoritmo p-1 di Pollard (vedi Crandall-Pomerance, Sez.5.4 e Nota su "Pollard p-1"). Esperimenti con PARI/GP.

  • Esercizi3 2012-2013


    • Settima settimana:
    Introduzione alle curve ellittiche: equazione di Weierstrass ; esempi di curve ellittiche su Z p, con p primo.
    Costruzione geometrica della somma fra punti di una curva ellittica su R. Curve ellittiche su Zp (con p primo) (vedi Crandall-Pomerance Cap.7, Sez.7.1, e soluzioni Esercizi-svolti n.5: n.1-5).


    Ottava settimana:
    Esercizi sulle curve ellittche su Z p, con p primo. Teorema di Hasse. Struttura del gruppo dei punti di una curva ellittica su Zp.
    Introduzione al metodo di fattorizzazione con le curve ellittiche ECM di Lenstra: descrizione di un ciclo dell'algoritmo. Esempi con PARI/GP.

  • Esercizi-svolti n.5.


    • Nona settimana:
    Il metodo di fattorizzazione con le curve ellittiche ECM di Lenstra: descrizione dell'algoritmo. Complessita' probabilistica dell'algoritmo.
    La seconda fase dell'algoritmo. Esempi con PARI/GP.

    (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
    Nota sul metodo delle curve ellittiche).

  • Esercizi5 2012-2013; Esercizi-svolti 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; Nota "Calcolo dell'indice...."; 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 logaritmo discreto: esperimenti con PARI/GP.
    Introduzione al crivello quadratico per la fattorizzazione di numeri interi.

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


    Tredicesima settimana:
    Il crivello quadratico: descrizione del crivello.
    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.