Teoria dei numeri e sue applicazioni

Responsabile didattico: Pietro Corvaja

Durata: 18 ore

Programma

Lo scopo del corso è duplice: si presentano alcuni aspetti classici dell’aritmetica, focalizzando l’attenzione su questioni algoritmiche; inoltre si mostrano le recenti applicazioni dell’aritmetica alla crittografia a chiave pubblica.

Struttura decimale, scrittura in basi arbitrarie, operazioni e loro complessità. Fattorizzazione, teorema fondamentale dell’aritmetica. Algoritmo euclideo, frazioni continue, equazioni diofantee.
Piccolo teorema di Fermat, congruenze. Funzione di Eulero, ordine moltiplicativo rispetto a moduli composti.
Test di primalità. Algoritmo di Pollard.
Algoritmi numerici su Z/Zn. Algoritmi di ricerca di numeri primi.
Crittografia a chiave pubblica.

 


Elenco corsi 2006/2007