- Oggetto:
- Oggetto:
Algebra computazionale e crittografia
- Oggetto:
Computational algebra and cryptography
- Oggetto:
Anno accademico 2025/2026
- Codice attività didattica
- MAT0367
- Docenti
- Andrea Ferraguti (Titolare)
Riccardo Walter Maffucci (Titolare) - Corso di studio
- Laurea in Matematica
- Anno
- 1° anno, 2° anno, 3° anno
- Periodo
- Secondo semestre
- Tipologia
- D.M. 270 TAF D - A scelta dello studente
- Crediti/Valenza
- 6
- SSD attività didattica
- MATH-02/A - Algebra
- Erogazione
- Tradizionale
- Lingua
- Italiano
- Frequenza
- Facoltativa
- Tipologia esame
- Orale
- Prerequisiti
-
Sono necessarie per affrontare efficacemente i contenuti dell’insegnamento le seguenti conoscenze matematiche: aritmetica modulare, algebra lineare, gruppi, anelli, campi.
It is necessary to have good knowledge of the following mathematical concepts: modular arithmetic, linear algebra, groups, rings, fields.
- Oggetto:
Sommario insegnamento
- Oggetto:
Avvisi
- Oggetto:
Obiettivi formativi
Lo scopo dell’insegnamento è quello di fornire i concetti matematici che sono alla base della moderna crittografia e della teoria computazionale dei grafi.
The aim of the course is to provide the mathematical concepts that are the basis of modern cryptography and computational graph theory.
- Oggetto:
Risultati dell'apprendimento attesi
Occorrerà essere in grado di:
- comprendere le idee e le motivazioni che sono alla base dello sviluppo dimetodi algebrici e di teoria dei numeri nella crittografia (con particolare enfasi sulla crittografia a chiave pubblica).
- padroneggiare i metodi di fattorizzazione e i test di primalità
- conoscere le strutture algebrico-geometriche fondamentali per la crittografia: gruppi, anelli e campi finiti, polinomi, matrici, estensioni di campi, reticoli.
- conoscere le principali classi di crittosistemi e di firme digitali.
- conoscere i problemi connessi alla teoria dei grafi moderna, algoritmi e applicazioni.
It will be necessary to be able to:- understand the ideas and motivations behind the development of algebraic and nuber theoretical methods in cryptography (with particular emphasis on public-key cryptography).
- master factorization methods and primality tests.
- know the fundamental algebraic-geometric structures for cryptography: groups, rings and finite fields, polynomials, matrices, field extensions, lattices
- know the main classes of cryptosystems and digital signatures.
- learn about the problems related to modern graph theory, algorithms and applications.
- Oggetto:
Programma
- Cenni storici: cifrario di Vigenére, Enigma.
- Crittografia a chiave pubblica. Aritmetica modulare ed RSA.
- Algoritmi di fattorizzazione: Pollard, Fermat, quadratic sieve, frazioni continue.
- Test di primalità probabilistici e deterministici, numeri di Carmichael.
- Metodo di Diffie Hellman per lo scambio delle chiavi.
- El Gamal e problema del logaritmo discreto.
- Algoritmi per il logaritmo discreto: babystep-giantstep, Pohling-Hellman. Meet in the middle.
- Crittografia basata sui codici: il protocollo di McEliece.
- Crittografia basata sui reticoli. Subset sum problem. Richiami sugli spazi vettoriali. Il problema del vettore più corto. Algoritmo di Babai. Il protocollo GGH.
- Protocolli a conoscenza zero. Firme digitali.
- Introduzione ai grafi. Successioni grafiche, teorema di Havel-Hakimi.
- Cammini, vertici separanti, ponti, blocchi. Connettività, componenti connesse.
- Grafi ad albero, alberi ricoprenti. Algoritmo span tree e min span tree. Problema del cammino più breve.
- Grafi planari e poliedri. Algoritmo dei cicli lunghi. Teorema di Kuratowski.
- Colorazioni, algoritmi, teorema dei quattro colori.
- Cenni sulla teoria estremale dei grafi.
- Cenni sui codici correttori, codici sferici.
- Historical notes: Vigenére cipher, Enigma.
- Public-key cryptography. Modular and RSA arithmetic.
- Quadratic extensions of F_p, quadratic reciprocity.
- Factorization algorithms: Pollard, Fermat, quadratic sieve, continuous fractions.
- Probabilistic and deterministic primality tests, Carmichael numbers.
- Goldwasser-Micali scheme.
- Diffie Hellman's method for exchanging keys.
- El Gamal and discrete logarithm problem.
- Algorithms for discrete logarithm: babystep-giantstep, Pohling-Hellman. Paradox of birthdays and meet in the middle.
- Entropy and security of cryptosystems.
- Elliptic curves over finite fields. The discrete logarithm for elliptic curves. Lenstra's algorithm.
- Lattice-based encryption. Subset sum problem. References to vector spaces. The problem of the shortest vector. Babai algorithm. The GGH.
- Zero-knowledge protocols. Digital signatures.
- Basics of post-quantum cryptography.
- Introduction to graph theory. Graphical sequences, theorem of Havel-Hakimi.
- Walks, separating vertices, bridges, blocks. Connectivity, connected components.
- Tree graphs, spanning trees. Span tree and min span tree algorithms. Shortest path problem.
- Planar graphs and polyhedra. Algorithm of long cycles. Theorem of Kuratowski.
- Colorings, algorithms, four colour theorem.
- Introduction to extremal graph theory.
- Overview of error correcting codes, spherical codes.
- Oggetto:
Modalità di insegnamento
L'insegnamento consiste di una successione di lezioni frontali di due ore ciascuna.The teaching consists of a sequence of lectures lasting two hours each.- Oggetto:
Modalità di verifica dell'apprendimento
Esame orale. Il voto sarà espresso in trentesimi.Oral exam. The final grade is given on a 30-point scale.- Oggetto:
Attività di supporto
Testi consigliati e bibliografia
- Oggetto:
- Galbraith, "Mathematics of public key cryptography"
- Silverman, Pipher, Hoffstein, "An introduction to mathematical cryptography", Springer, 2008.
-
Stinson, Paterson, "Cryptography: Theory and Practice", Taylor & Francis, 2018.
- Frank Harary, "Graph theory" Reading, Mass. : Addison-Wesley, [1969]
- Galbraith, "Mathematics of public key cryptography"
- Registrazione
- Aperta
- Oggetto:
