Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2019-2020

Laurea Specialistica, anno 1, crediti 6.

Docente: Laura Geatti


CORSO CHIUSO


ORARIO

1o semestre: 23 settembre 2019 - 17 gennaio 2020.

  • Ricevimento: dopo le lezioni in aula, per appuntamento, per e-mail. Il venerdi' dopo la lezione posso fermarmi presso gli edifici didattici.

PROGRAMMA

  • Obiettivi formativi: analizzare il funzionamento e la complessita' di vari algoritmi per la fattorizzazione di numeri interi e per la risoluzione del logaritmo discreto. Tali algoritmi sono gli ''antagonisti'' di diversi criptosistemi attualmente in uso.

  • Argomenti fra i seguenti:
  • Primalita' e fattorizzazione: complessita' a confronto, criptosistema RSA, test di primalita' di Miller-Rabin;
  • Algoritmi per fattorizzare numeri: Metodo ρ di Pollard, metodo p–1, metodo delle curve ellittiche, crivello quadratico;
  • Logaritmo discreto: Baby-step-Giant-Step, calcolo dell'indice.
  • Certificati di primalita': criterio di Pocklington, algoritmo di Goldwasser-Kilian.
  • Curve ellittiche: contare i punti di una curva ellittica su campo finito.
  • Lattices: algoritmo LLL.
    Programma dettagliato    Diario delle lezioni

    Foto 2019: foto1

    Testi di riferimento principali:
    R. Crandall and C. Pomerance: Prime Numbers. A computational perspective, Springer-Verlag 2002.
    L. Washington: Elliptic Curves: Number Theory and and Cryptography, , Chapman and Hall /CRC 2003.

    Prerequisiti: Calcolo modulo n. Vedi: Corso di Algebra e Logica (Laurea Triennale in Ing. Informatica) AL2015


ESAMI

    L'esame consiste in un compito scritto e in un progetto.
    Per presentare il progetto è necessario aver fatto un compito scritto sufficiente (con voto almeno 18).
    Il voto del compito vale fino al 30 settembre 2020. Chi fa lo scritto in settembre, si porti avanti col progetto per tempo.

    Per partecipare agli scritti, è necessario iscriversi mediante il sito Delphi.
    Portare un documento di riconoscimento.
    Non sono consentiti libri, appunti ne' palmari.
    Non è consentito uscire durante il compito.


      • Sessione invernale
      • appello1: Soluzioni pdf Risultati html
      • appello2: Risultati html

      • Sessione estiva :
      • appello3: 15 giugno 2020, ore 10:00 (vedi avviso)
      • appello4: 13 luglio 2020, ore 10:00 (vedi avviso)

      • Sessione autunnale:
      • appello5: 7 settembre 2020, ore 10:00 (vedi avviso per eventale aula o modalita' online)
      • appello6: 21 settembre 2020, ore 10:00 (vedi avviso per eventale aula o modalita' online)

      Progetti (gruppi di due persone al massimo) (più stelle = più difficile)

      • Metodo delle curve ellittiche (prima fase, seconda fase).
      • Logaritmo discreto (calcolo dell'indice).
      • Crivello quadratico.
      • Contare punti su curve ellittiche su campi finiti
      • Test di primalita' di Atkin.


      ESERCIZI

      Esercizi 2019-2020

      Esercizi svolti
      • Esercizi1 (complessita') pdf   Soluzioni pdf
      • Esercizi2 (numeri primi, numeri B-smooth) pdf   Soluzioni pdf
      • Esercizi3 (gruppi, anelli, campi) pdf (vedi anche pdf e soluzioni pdf )
      • Esercizi4 (esercizi con PARI/GP, in aggiornamento...) pdf
      • Esercizi5 (curve ellittiche) pdf   Soluzioni pdf
      • Esercizi6 (logaritmo discreto in Z*p) pdf   Soluzioni pdf
      • Esercizi7 (preliminari al crivello quadratico) pdf   Soluzioni pdf

    MATERIALE

      Software
      • GMP software for long integer arithmetic.
      • PARI/GP computer algebra system for doing fast computations in number theory.
      • PARI-DOC User's Guide to PARI/GP   GPTutorial1    GPTutorial2
        • SAGE software matematico (include PARI/GP)
      • Alpertron Factorizaciòn usando curvas elípticas online

      Testi
      Articoli di carattere espositorio, conferenze
      • Joe Malkevitch: Mathematics and internet security, Feature column of Am. Math. Soc., April 2006 link
      • L. Adleman : conferenza all'ACM per il premio Turing 2002.
      • Victor Miller : Elliptic curve cryptography Presentazione, 24 maggio 2007.
      • Post-quantum Cryptography Winter School 2016 link
      • Phong Nguyen, Lattice based Cryptography talk
      • L'associazione nazionale di crittografia "De Componendis Cifris" link
      • NSA 50 years of crypto etc.. pdf

      Materiale per argomenti
      • Fattorizzazione
        • Metodo delle curve ellittiche
          • Curve Ellittiche in Wikipedia
          • H. Lenstra: Factoring integers with elliptic curves, Annals of Math. 126, (1987) 649-673 pdf (l'introduzione e' chiara e accessibile)
          • R. Brent: Factorization of the tenth Fermat number, Math. Comp. 68 (1999) 429–451. (pdf)
          • Metodo delle curve ellittiche in Wikipedia.
          • Elliptic curve method web pages.
          • Elliptic Curve Tutorial di certicom link
          • P. Zimmerman: The elliptic curve method. (April 2003)pdf
          • Ecmnet.
          • Foto di Hendrik Lenstra.
        • Il crivello quadratico
          • Il crivello quadratico in Wikipedia.
          • Carl Pomerance, Smooth numbers and the quadratic sieve, pdf.
          • Carl Pomerance, A tale of two sieves, pdf (La favola dei due crivelli).
          • La fattorizzazione di RSA129 (1994) txt.
          • Esempio di fattorizzazione usando il crivello quadratico txt Spiegazione pdf
          • Un altro esempio pdf Spiegazione pdf
          • Radici quadrate modulo p. Algoritmo di Shanks-Tonelli txt.
          • L'algoritmo di Shanks-Tonelli in Wikipedia.
          • Il Lemma di Hensel in Wikipedia.
          • Foto di Carl Pomerance
      • Logaritmo discreto
        • Il logaritmo discreto in Wikipedia.
        • Discrete logarithm web pages.
        • C. Pomerance: Elementary thoughts on discrete logarithms, “Algorithmic number theory” MSRI Publications 44, Cambridge University Press 2008, pdf.
        • Chris Studholme, The discrete log problem, june 2002, pdf
        • Baby-step-Giant-step method in Wikipedia.
        • J. Pollard: Monte Carlo methods for index computation (mod p), Math. Comp. 32 (1978). (Canguri, pdf, 7 p.).
        • Esempio di calcolo di un logaritmo discreto (mini calcolo dell'indice) 1, 2, 3, 4.
        • Esempio di calcolo di un logaritmo discreto (usando il metodo del calcolo dell'indice)txt.
        • Il logaritmo discreto sulle curve ellittiche CerticomTutorial
        • Diffie-Hellman-Merkle key exchange in Wikipedia.
        • El Gamal encryption in Wikipedia.
        • Foto di Dan Shanks
        • Foto di Taher ElGamal
        • Foto di Ralph Merkle, Martin Hellman, Whit Diffie.
      Note
      • nota1 Aritmetica sui numeri interi.
      • nota2 Gruppi, anelli, campi e applicazioni.
      • Nota sui gruppi abeliani finiti.
      • Nota sulla funzione φ di Eulero.
      • Espansioni decimali di 1/n.
      • Nota sul Teorema dei numeri primi di Chebyshev.
      • Nota sul metodo ρ di Pollard.
      • Nota sul metodo p-1 di Pollard.
      • Nota sul metodo delle curve ellittiche.
      • Nota sulle radici primitive modulo p.
      • Nota sul "calcolo dell'indice" per la risoluzione del logaritmo discreto in Z p*.
      • Nota sull'algoritmo Baby-Step-Giant-Step per la risoluzione del logaritmo discreto su un gruppo ciclico.
      • Nota su esempi di applicazioni del logaritmo discreto alla crittografia.
      • Nota sul Crivello Quadratico.
      • Nota sulla sommatoria Σ 1/p.
      • Nota "smooth numbers estimates".
      • Nota sull'algoritmo di Shanks-Tonelli.
      • Nota sulle radici quadrate modulo p e modulo pk.
      • Nota sui test di primalita' di Pocklington and di Goldwasser-Kilian. Esempi pdf
      • Nota sull'algoritmo di Cornacchia.
      • Nota sull'algoritmo di Cantor-Zassenhaus.

      NUMEROLOGIA & VARIE



      Il corso di Teoria Elementare dei Numeri





      Altro

      • L'associazione BEST per la promozione della mobilità degli studenti di Ingegneria in Europa.