Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2016-2017

T e o r i a   E l e m e nt are   d e i  N u m e r i

Laurea Specialistica, anno 1, crediti 6.

Docente: Laura Geatti


      



ORARIO

1o semestre: 3 ottobre 2016 - 28 gennaio 2017.

   LUNEDI MARTEDI MERCOLEDI GIOVEDI VENERDI
   ore 9:30 - 11       Lezione
   Aula C5
           
   ore 14-16                   Lezione
   Aula C4
  • 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:
  • 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.
    Programma dettagliato    Diario delle lezioni

    Testo di riferimento principale: R. Crandall and C. Pomerance: Prime Numbers. A computational perspective, Springer-Verlag 2002.
    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 2017.

    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: Soluzioni pdf Risultati html

    • Sessione estiva :
    • appello3: 26 giugno 2017, ore 10-12, Aula B8 (Ed. Didattici)
    • appello4: 18 luglio 2017, ore 10-12, Aula B8 (Ed. Didattici)

    • Sessione autunnale:
    • appello5: 7 settembre 2017, ore 9:30-11:30, Aula 16 (SOGENE)

    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 2016-2017
    • Esercizi1 pdf
    • Esercizi2 pdf
    • Esercizi3 pdf
    • Esercizi4 pdf
    • Esercizi5 pdf
    • Esercizi6 pdf
    • ECpari (comandi di base) rtf
    • ECpari (fase 1) rtf
    • ECpari (ECM a carte scoperte) rtf
    • Esercizi7 pdf

    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

MATERIALE