COMPUTER ALGEBRA

Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita all’anno accademico di tuo interesse? Ecco come fare >>
English course description
Anno accademico
2017/2018
Docente
FABIO STUMBO
Crediti formativi
6
Periodo didattico
Primo Semestre
SSD
MAT/02

Obiettivi formativi

L'obiettivo del corso è approfondire gli aspetti teorici alla base di alcuni importanti algoritmi algebrici comunemente usati nelle applicazioni con particolare riferimento alla Crittografia e alla Teoria dei Codici.

Le principali conoscenze acquisite sono:
* struttura dei campi finiti;
* significato di complessità computazionale di un algoritmo;
* caratteristiche fondamentali dei cifrari simmetrici ed asimmetrici;
* algoritmi di fattorizzazione di numeri e polinomi;
* test di primalità per numeri interi;
* algoritmi di codifica e correzione degli errori per la trasmissione di messaggi.

Le principali abilità acquisite sono:
* saper calcolare la complessità computazionale di un algoritmo;
* saper cifrare messaggi usando i cifrari studiati;
* riconoscere la primalità di un numero intero;
* fattorizzare un numero intero;
* saper fattorizzare polinomi a coefficienti interi o in un campo finito;
* saper codificare e decodificare un messaggio ed essere in grado di riconoscere e correggere gli errori avvenuti durante la trasmissione secondo gli algoritmi studiati.

Prerequisiti

Sono sufficienti le conoscenze elementari di algebra acquisite nel corso di Algebra del primo anno. In particolare:
* nozioni sui gruppi, anelli e campi;
* struttura dei campi finiti;
* calcolo del MCD e algoritmo euclideo.

Contenuti del corso

Il corso prevede 48 ore di lezione frontale nel corso delle quali verranno svolti sia la teoria che gli esercizi.
La suddivisione approssimativa delle lezioni è:
1. Preliminari algebrici (12 ore):
* Algoritmo euclideo.
* Teorema di Eulero-Fermat.
* Sistemi di congruenze.
* Campi finiti.
* Elementi primitivi.
* Radici dell'unità e classi ciclotomiche
* Complessità computazionale.
2. Criptografia (6 ore):
* Permutazioni e sostituzioni.
* Algoritmi a sostituzione.
* Algoritmi a trasposizione.
* Algoritmo di Hill.
* Algoritmi simmetrici: DES e AES.
* Algoritmi a chiave pubblica: cifrario RSA, cifrario ElGamal.
* Funzioni di hash: SHA-1.
* Firma digitale: DSA.
3. Fattorizzazione dei numeri interi (4 ore):
* Crivelli: il crivello di Eratostene.
* Algoritmi di fattorizzazione: algoritmo (p-1) di Pollard, algoritmo Rho di Pollard.
* Test di primalità: algoritmo di Miller-Rabin, algoritmo AKS.
4. Fattorizzazione di polinomi (4 ore):
* Algoritmo di Berlekamp.
* Lemma di Hensel.
* Fattorizzazione in Q[x].
5. Codici autocorretivi (22 ore):
* Distanza di Hamming.
* Disuguaglianze di Hamming, Singleton e Gilbert-Varshamov.
* Codici lineari, codici di Hamming.
* Codici ciclici, codici BCH e codici Reed-Solomon.
* Codifica e decodifica.
* Decodica a sindromi, decodifica di Slepian.
* Decodifica di Meggitt nei codici ciclci
* Algoritmi di decodifica nei codici BCH: PGZ, Forney, Sugyiama, Berlekamp-Massey

Metodi didattici

Il corso è organizzato secondo lezioni frontali convenzionali, generalmente di 2 ore ciascuna.

Modalità di verifica dell'apprendimento

L'obiettivo della prova d'esame consiste nella verifica del raggiungimento
delle abilità previste.
Tale verifica viene effettuata tramite una prova scritta della durata di
3 ore e composta da esercizi riguardanti gli argomenti svolti a lezione.
La prova scritta è composta da domande e/o esercizi di punteggio
variabile per un totale non inferiore a 30.
Il totale dei punti ottenuti nella prova (limitato a 30 se maggiore) è
il voto riportato dallo studente.
L'esame è superato se il voto è almeno 18.
La prova orale è opzionale, su richiesta dello studente.
L'eventuale prova orale contribuisce al voto finale con un punteggio
compreso tra -3 e 3.

Testi di riferimento

1) Fabio Stumbo, Computer Algebra, Ed. Aracne
2) Fabio Stumbo, Teoria dei Codici