Padronanza degli algoritmi utilizzati nel campo dell'algebra applicata, in particolare nella crittografia algebrica e nella risoluzione di sistemi di equazioni polinomiali sui campi finiti.
Prerequisiti
Concetti fondamentali di algebra, geometria e analisi e conoscenza di un linguaggio di programmazione.
Metodi didattici
Lezioni frontali e laboratoriali. Utilizzo di un linguaggio di programmazione per il calcolo simbolico.
Verifica Apprendimento
L’esame consiste di uno dei due metodi alternativi: 1) Esame orale; 2) Valutazioni in itinere più progetto. 1) Esame orale. L’esame orale prevede esercizi e domande teoriche su argomenti presentati durante il corso. La prova orale si intende superata se si raggiungono almeno 18/30. 2) Valutazioni in itinere più progetto finale. Le valutazioni in itinere settimanali (una per settimana e di circa 45 minuti) prevedono esercizi ed implementazioni relative agli argomenti trattati. Per la risoluzione si possono consultare gli appunti delle lezioni. Grazie alle valutazioni in itinere si potranno ottenere al massimo 27/30. Tale punteggio si otterrà dalla somma delle singole valutazioni in itinere. A tale punteggio si aggiunge quello del progetto finale che verrà valutato al massimo 3/30. Il progetto finale è scelto dallo studente in accordo col docente su tematiche trattate durante il corso. L’esame si intende superato se lo studente consegue tra prove in itinere e seminario un voto di almeno 18/30.
Testi
Lindsay N. Childs, A Concrete Introduction to Higher Algebra, Springer. Audrey Terras, Fourier Analysis on Finite Groups and Applications, 1999, London Mathematical Society Student Texts. R.Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, 2009. D. A. Cox , J. Little, D. O'Shea, Ideals, Varieties, and Algorithms, Fourth edition, Springer, 2015.
Contenuti
Gli interi Z. L’algoritmo euclideo. Test di primalità. Fattorizzazione di interi. Applicazioni in crittografia asimmetrica. Quozienti di Z e il cerchio finito Zn. Funzioni esponenziali complesse su Zn. I caratteri di Zn. La trasformata discreta di Fourier. Applicazioni. Nozioni fondamentali sui campi finiti e le loro estensioni. Il campo di spezzamento di un polinomio su un campo finito. Elementi primitivi di un campo finito e l'LFSR (Linear Feedback Shift Register). Automorfismi di campi. Traccia e norma. Applicazioni alla crittografia simmetrica. Anello dei polinomi su un campo. Ideali iniziali. Basi di Groebner. Il problema dell’appartenenza ad un ideale. Teoria della eliminazione e applicazioni. Varietà affini. Relazioni con gli ideali. Risultante. Teorema di estensione. Nullstellensatz in forma debole e forte. Serie formali. Moduli graduati. Successioni esatte corte. La serie di Hilbert. Lemma di Macaulay ed ideali iniziali. Un algoritmo per il calcolo della serie di Hilbert.