Syllabus del corso
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, campin finiti, e vari strumenti di teoria dei numeri.
I risultati di apprendimento attesi comprendono: la conoscenza di classici test di primalità di tipo probabilistico; la conoscenza 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.
Obiettivi formativi e risultati di apprendimento attesi, espressi secondo i cinque Descrittori di Dublino:
Conoscenza e capacità di comprensione (knowledge and understanding):
Lo studente acquisirà conoscenze avanzate di Teoria dei numeri con particolare riferimento all’aritmetica modulare, ai campi finiti, ai test di primalità (probabilistici e deterministici), e ai fondamenti matematici di alcuni principali sistemi crittografici a chiave pubblica. Tali conoscenze saranno fondate su una solida preparazione matematica di base e intermeda e consentiranno di comprendere il ruolo delle strutture algebriche e aritmetiche in contesti applicativi.
Capacità di applicare conoscenza e comprensione (applying knowledge and understanding):
Lo studente sarà in grado di applicare le tecniche apprese per analizzare criticamente i principali algoritmi crittografici basati su problemi di teoria dei numeri (come la fattorizzazione e il logaritmo discreto), e per risolvere problemi teorici ed esercizi, anche con elementi computazionali, connessi ai contenuti trattati.
Autonomia di giudizio (making judgements):
Lo studente svilupperà la capacità di valutare criticamente l’efficacia e la sicurezza di vari protocolli crittografici, e di interpretare autonomamente risultati teorici e dimostrazioni, individuando ipotesi rilevanti e metodi di generalizzazione.
Abilità comunicative (communication skills):
Lo studente acquisirà la capacità di esporre con rigore e chiarezza i concetti teorici e le tecniche apprese, sia in forma scritta sia orale, utilizzando una terminologia matematica appropriata e adeguata al contesto scientifico e applicativo.
Capacità di apprendimento (learning skills):
Lo studente sarà in grado di approfondire autonomamente argomenti affini o complementari, consultando la letteratura matematica specialistica e comprendendo articoli e testi avanzati di teoria dei numeri e crittografia matematica..
Contenuti sintetici
ll corso presenta risultati di algebra e teoria dei numeri di interesse crittografico, e le loro applicazioni. Particolare attenzione sara rivolta ad aspetti algoritmici e di complessita computazionale. Gli argomenti includearanno test di primalità e metodi di fattorizzazione.
Programma esteso
- Richiami di vari argomenti sui numeri interi e l'aritmetica modulare, con attenzione ad aspetti di complessita` computazionale.
- Introduzione ai sistemi crittografici a chiave segreta e a chiave pubblica. Firme digitali.
- Numeri primi: cenni al Teorema di Dirichlet sui primi in progressione aritmetica, e al teorema dei numeri primi.
- I campi finiti e la legge di reciprocita` quadratica.
- Analisi dettagliata del crittosistema RSA: rischi e accortezze.
- Il logaritmo discreto in un campo finito, e sue applicazioni (incuso il crittosistema di Diffie-Hellmann).
- Primalità: test di primalità probabilistici (Fermat, Jacobi, Miller-Rabin), e test deterministici in certi casi.
- Metodi di fattorizzazione: metodo rho, metodo delle factor bases.
- A seconda del tempo e dell'interesse, cenni a qualche altro argomento di interesse o conseguenze crittografiche, quali: caratteri e serie di Dirichlet; stime di somme di caratteri; la funzione zeta di Riemann; fondamenti sulle curve ellittiche; il test di primalita` (deterministico) AKS.
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à esercizi da svolgere a casa. Le soluzioni saranno discusse a richiesta in classe, o a ricevimento.
Il corso comprende 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
Sono fornite delle note del corso, tratte in parte dal seguente testo, che si invita a consultare per approfondimenti:
- N. Koblitz, A course in Number Theory and Cryptography, volume 114 of Graduate texts in Mathematics, Springer-Verlag, second edition, 1994.
Si vedano le note per eventuali altre letture suggerite.
Periodo di erogazione dell'insegnamento
II semestre.
Modalità di verifica del profitto e valutazione
Esame scritto e orale
-
La prova scritta richiedera` la risoluzione di alcuni esercizi, principalmente di carattere pratico.
-
Nella prova orale si dovra` mostrare la conoscenza e la padronanza degli argomenti trattati durante il corso (inclusi enunciati e dimostrazioni dei teoremi).
Lo studente è ammesso a sostenere la prova orale (obbligatoria) se raggiunge la votazione di 18/30 nello scritto
Lo svolgimento dello scritto e la prova orale concorrono alla valutazione finale del corso.
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, finite fields, and various tools from number theory.
Learning objectives and expected outcomes are as follows, formulated according to the five Dublin Descriptors:
Knowledge and understanding:
Students will acquire advanced knowledge in number theory, with emphasis on modular arithmetic, finite fields, probabilistic primality tests, and the mathematical foundations of public-key cryptographic systems. This knowledge will build upon a solid undergraduate background and will provide insight into the algebraic and arithmetic structures underlying modern cryptographic protocols.
Applying knowledge and understanding:
Students will be able to apply the learned techniques to critically analyze cryptographic algorithms based on number-theoretic problems (e.g., factorization, discrete logarithm), and to solve both theoretical and computational problems related to the topics covered in the course.
Making judgements:
Students will develop the ability to assess the mathematical soundness and security of cryptographic protocols, to interpret theoretical results and proofs independently, and to identify relevant hypotheses and methods for generalization.
Communication skills:
Students will be able to present theoretical concepts and techniques clearly and rigorously, both in written and oral form, using appropriate mathematical language suited to both scientific and applied contexts.
Learning skills:
Students will be capable of independently exploring related or more advanced topics, consulting the mathematical literature and understanding specialized texts and research articles in number nheory and cryptographic mathematics.
Contents
The course focuses on algebraic and number theoretic results that are of cryptographic interest, and their applications in cryptography. Special attention will be given to algorithmic aspects, and of computational complexity. Topics covered will include primality tests and factorization methods.
Detailed program
- Review of various topics on integers and modular arithmetic, with special attention to aspects of computational complexity.
- Introduction to cryptographic systems, both secret-key and public-key. Digital signatures.
- Prime numbers: discussion od some deeper results such as Dirichlet's Theorem on primes in arithmetic progressions and the prime number theorem.
- Finite fields and the quadratic reciprocity law.
- Deeper analysis of the RSA cryptosystem: risks and requirements.
- Primality: probabilistic primality tests (Fermat, Jacobj, Miller-Rabin), and deterministic tests in some cases.
- The discrete logarithm in a finite field, and applications (such as the Diffie-Hellmann cryptosystem).
- Factorization: Pollard's rho method, the factor bases method.
- Depending on time and interest, selected additional topics of cryptographic interest or consequences, such as: characters and Dirichlet series; character sum bounds; Riemann's zeta function; basics on elliptic curves; the AKS (deterministic) primality test.
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
Periodic exercise sheets will be made available on the e-learning website to encourage participation. The solutions will be discussed in class on request, or during officie hours.
The course comprises a total of 56 one-hour in-class lectures (usually combined in pairs).
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 will be in Italian by default, and when necessary, in English.
Textbook and teaching resource
Lecture notes for the course are made available. They are partially inspired from the following textbook, which is recommended for further reading:
- N. Koblitz, A course in Number Theory and Cryptography, volume 114 of Graduate texts in Mathematics, Springer-Verlag, second edition, 1994.
Please see the notes for other recommended sources.
Semester
II term.
Assessment method
Written and oral examination.
-
The written part requires solving a set of exercises, mainly of practical character.
-
The oral examination will serve to demonstrate the knowledge of the topics of the course (including statements and proofs of theorems).
Admission to the (compulsory) oral exam requires obtaining a mark of at least 18/30 in the written exam.
Both the written and oral exam will contribute to the final mark for the course.
Office hours
By direct agreement.
Sustainable Development Goals
Staff
-
Sandro Mattarei
