Course Syllabus
Obiettivi
Coerentemente con gli obiettivi formativi del Corso di Studio, l'insegnamento si propone di fornire alcuni concetti e alcune tecniche di Teoria dei numeri, fondamentali per introdurre lo studente alla comprensione del funzionamento dei principali sistemi crittografici a chiave pubblica, che fanno uso dell'aritmetica modulo n e delle curve ellittiche su campi finiti.
I risultati di apprendimento attesi comprendono: la conoscenza di classici test di primalità di tipo probabilistico, e del test deterministico AKS; la conoscenza della struttura di gruppo di una curva ellittica su un campo finito e applicazioni al problema del logaritmo discreto e al problema della fattorizzazione di un numero intero; la capacità di analizzare e riproporre le dimostrazioni presentate durante le lezioni e di risolvere alcuni facili problemi facendo uso delle tecniche presentate; la capacità di approfondire, anche in maniera autonoma, alcuni dei risultati presentati durante il corso
Contenuti sintetici
ll Corso presenta alcuni risultati di Teoria dei numeri, con particolare riguardo a test di primalità e metodi di fattorizzazione usando argomenti classici di Teoria dei numeri e le curve ellittiche.
Programma esteso
- Richiami sui numeri interi e sui campi finiti, aritmetica modulare, funzione di Eulero, teorema cinese del resto.
- Introduzione ai sistemi crittografici; chiave pubblica e chiave privata.
- Numeri primi: cenni sul Teorema di Dirichlet. Primalità e fattorizzazione:numeri pseudoprimi, alcuni test di primalità (Fermat, Jacobi, Miller-Rabin, AKS), metodo rho per la fattorizzazione; complessità computazionale di un algoritmo.
- Un'introduzione ai caratteri di Dirichlet.
- Cenni sulla funzione zeta di Riemann e sulle funzioni L(χ,s); fattorizzazione di Eulero; cenni su ipotesi generalizzata di Riemann e ripercusssioni sui test di primalita
- Crittosistema di Diffie ed Hellman. Il problema del logaritmo discreto.
- Curve ellittiche: equazione di Weierstrass, gruppo dei punti di una curva ellittica, curve ellittiche su campi finiti.
- Endomorfismi di curve ellittiche.
- Teorema di Hasse (dimostrazione: cenni)
- Punti di torsione e Weil pairing
- Alcuni crittosistemi basati sulle curve ellittiche.
- Il problema del Logaritmo discreto. Attacco MOV. Baby step - Giant step.
- Firma digitale (DSA e ECDSA).
- Isogenie di curve ellittiche: definizione e cenni sul loro uso nel problema del logaritmo discreto
Prerequisiti
Conoscenze di base sulle strutture algebriche, generalmente acquisite nei corsi di Algebra di un corso di Laurea di Primo Livello, con particolare riguardo ai gruppi, gruppi abeliani finitamente generati e ai campi finiti.
Modalità didattica
Lezioni frontali (8 CFU), articolate in: lezioni teoriche in cui si fornisce la conoscenza di definizioni, risultati e teoremi rilevanti e altre in cui si intende fornire competenze e abilità necessarie per utilizzare tali nozioni nella risoluzione di esercizi e nell'analisi di problemi.
Per stimolare la partecipazione, sono proposti con regolarità agli studenti alcuni esercizi, la cui risoluzione viene da essi caricata sul sito e-learning.
In totale: 56 ore di lezione in presenza. Si utilizza un approccio didattico ibrido che combina didattica frontale (DE) e didattica interattiva (DI). La DE include la presentazione e spiegazione dettagliata dei contenuti teorici. La DI prevede interventi attivi degli studenti tramite esercizi e problemi, brevi interventi, discussioni collettive e lavori di gruppo o individuali. Non è possibile stabilire precisamente a priori il numero di ore dedicate alla DE e alla DI, poiché le modalità si intrecciano in modo dinamico per adattarsi alle esigenze del corso e favorire un apprendimento partecipativo e integrato, combinando teoria e pratica.
Materiale didattico
I principali testi di riferimento sono:
- N. Koblitz, A course in Number Theory and Cryptography, volume 114 of Graduate texts in Mathematics, Springer-Verlag, second edition, 1994.
- H.E. Rose, A course in Number Theory, II edizione, Oxford: Clarendon press, 1994
- Lawrence C. Washington, Elliptic Curves, Number Theory and Criptogtaphy CRCPress
Altri testi:
- Maria Welleda Baldoni, Ciro Ciliberto, Giulia Maria Piacentini Cattaneo, Elementary Number Theory, Cryptography and Codes, 2009 Springer-Verlag Berlin Heidelberg
- Graham Everest, Thomas Ward Introduction to Number Theory, Springer-Verlag London Limited 2005
- A. Languasco, A. Zaccagnini, Introduzione alla Crittografia, Hoepli Editore, 2004.
Periodo di erogazione dell'insegnamento
II semestre.
Modalità di verifica del profitto e valutazione
Esame scritto e orale
- La prova scritta consiste in alcuni esercizi da cui si evinca la capacita' dello studente a usare gli strumenti introdotti nelle lezioni
- Per quanto riguarda l'orale, obbligatorio per tutti, questo consiste in due parti:
Prima parte: discussione dello scritto;
Seconda parte: lo studente puo' scegliere se
- fare una classica prova orale in cui mostri la conoscenza e la padronanza degli argomenti trattati durante il corso, spieghi le motivazioni che hanno portato a trattare alcuni argomenti teorici che hanno risvolti applicativi e
dia gli enunciati e le dimostrazioni dei teoremi; - dare un seminario in cui si approfondisca un argomento solo accennato durante il corso.
entrambe le modalità dovranno permettere di verificare la conoscenza e padronanza dei contenuti del corso e la capacità di rielaborare i concetti appresi e di esporli in modo rigoroso.
Valutazione dell’esame: Voto in trentesimi 18-30/30
Lo studente è ammesso a sostenere la prova orale se raggiunge la votazione di 18/30 nello scritto
La discussione dello scritto e la prova orale concorrono alla valutazione finale, che è ottenuta dalla media tra la votazione ottenuta nello scritto+discussione (accorpati) e dalla seconda parte dell’orale.
Orario di ricevimento
Su appuntamento.
Sustainable Development Goals
Aims
In line with the educational objectives of the Degree in Mathematics, the course aims to provide the student with some of the fundamental concepts, methods and some techniques of Number theory, essential for understanding the main asymmetric Cryptographic systems based on modular arithmetic or on elliptic curves over finite fields.
The student is expected to have knowledge of main probabilistic primality tests, the deterministic test AKS; the knowledge of the structure of the group of elliptic curves over finite fields, with applications to the problem of discrete logarithm and of factorisation. It is also expected they have the ability to give proofs presented in the course, using given techniques to solve easy problems and the ability to study some more details of results presented during the course.
Contents
Some classical results in Number Theory are presented, with particular regard to factorizzation methods and primality tests, using modular arithmetic and Elliptic Curves.
Detailed program
- Integers and finite fields; Euler function; modular arithmetic
- Definition of a Cypher: public and private key
- Some topics about Prime numbers: Notes on Dirichlet's Theorem; Number Prime Theorem.
- An introduction to Dirichlet's characters.
- Prime numbers and factorization: pseudoprimes; primality tests (Fermat, Jacobj, Miller-Rabin AKS); (p-1)-pollard method for factorization; complexity of the alghoritms.
- Some remark about Riemann's zeta function; Euler'sFactorization; Riemann's hypothesis; extended Riemann's hypothesis and some consequence on primality tests.
- Diffie-Hellman cypher; discrete logarithm
- Elliptic curves; group of the points of an elliptic curve on a finite field.
- Endomorphisms.
- Torsion points and Weil pairing.
- Hasse Theorem
- Cryptosystems on elliptic curves.
- Discrete Logarithm on Elliptic Curves
- Digital Signature: DSA, ECDSA
- Isogenies and chryptographic attacks.
Prerequisites
Basic Algebra: algebraic structure; abelian groups; finite fields.
Teaching form
Lectures (8 credits). They will be of two different kind: they will give knowledge of basic definitions, relevant results and theorems. On the other side, we intend to give skills to use results and knowledge in solving exercises and analysing problems
Some exercise will be made available regularly on the e-learning website to encourage participation.
A hybrid teaching approach is used, that combines lecture-based teaching (DE) and interactive teaching (DI). DE involves detailed presentation and explanation of theoretical content. DI includes active student participation through exercises and problems, short presentations, group discussions, and group or individual work. It is not possible to precisely determine in advance the number of hours dedicated to DE and DI, as these methods are dynamically intertwined to adapt to the course's needs and promote a participatory and integrated learning environment, combining theory and practice.
Lectures (56 hours) and practical sessions/tutorials are conducted in person and are primarily in Italian, and when necessary, in English.
Textbook and teaching resource
Main reference books:
- N. Koblitz, A course in Number Theory and Cryptography, volume 114 of Graduate texts in Mathematics, Springer-Verlag, second edition, 1994..
- H.E. Rose, A course in Number Theory, II edizione, Oxford: Clarendon press, 1994
- Lawrence C. Washington, Elliptic Curves, Number Theory and Criptogtaphy CRCPress
Other help books:
- Maria Welleda Baldoni, Ciro Ciliberto, Giulia Maria Piacentini Cattaneo, Elementary Number Theory, Cryptography and Codes, 2009 Springer-Verlag Berlin Heidelberg
- Graham Everest, Thomas Ward Introduction to Number Theory, Springer-Verlag London Limited 2005
- A. Languasco, A. Zaccagnini, Introduzione alla Crittografia, Hoepli Editore, 2004
Semester
II term.
Assessment method
Written and Oral examination.
- The written part consists of exercises where the students show their ability in using methods and tools introduced in the course.
- The oral part consists of two parts:
1) discussion about written part;
2) the student may decide between:
- to give a classical oral exam, where he must show his competence about subjects considered in the lectures, also giving motivations for applications of theoretical topics;
- to give a talk about a particular subject, which was considered not very deeply in the course.
In any case, the oral exam must verify the full knowledge of the subjects considered in the course, and the capacity of the student to be rigorous in the exposition.
The final result is achieved considering the average between the mark obtained in written+discussion (together), and the mark obtained in the subsequent oral part.
Mark range: 18-30/30.
Office hours
By direct agreement.
Sustainable Development Goals
Staff
-
Francesca Dalla Volta
