Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2017-2018

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



Appelli sessione invernale:

Giovedi' 1 febbraio 2018, ore 9:30-11:30, Aula L3 SOGENE
Martedi' 27 febbraio 2018, ore 9:30-11:30, Aula L3 SOGENE
Foto 22 dicembre 2017: foto1    foto2

ORARIO

1o semestre: 25 settembre 2016 - 22 dicembre 2017.

   LUNEDI MARTEDI MERCOLEDI GIOVEDI VENERDI
   ore 9:30 - 11:15       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
    Foto 22/12/2017 1    2

    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: Giovedi' 1 febbraio 2018, ore 9:30-11:30, Aula L3 SOGENE
    • appello2: Martedi' 27 febbraio 2018, ore 9:30-11:30, Aula L3 SOGENE

    • Sessione estiva :
    • appello3:
    • appello4:
    • Sessione autunnale:
    • appello5:
    • appello6:

    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 2017-2018
    • Esercizi1 pdf
    • Esercizi2 pdf
    • Esercizi3 pdf
    • Esercizi4 pdf
    • Esercizi5 pdf
    • Esercizi6 pdf
    • Curve ellittiche in PARI/GP rtf
    • ECM fase 1: esempi rtf
    • 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
    • Esercizi7 (preliminari al crivello quadratico) pdf   Soluzioni pdf

MATERIALE