Algorithmique de base
Descritpion du cours
- Recherche dichotomique, tris, arbres. Complexité. Algorithmes élémentaires pour les graphes.
- PGCD, PGCD étendu, théorème chinois et arithmétique modulaire.
- Opérations sur les polynômes (opérations élémentaires, PGCD, interpolation, relations coefficients/racines).
- Multiplication rapide de polynômes (Schoolbook, Karatsuba, Toom-Cook, transformation de Fourier rapide, Number Theoretic Transform).
- Factorisation des polynômes, en particulier sur les corps finis.
- Localisation des racines de polynômes si le temps le permet.
- Résultants, initiation aux bases de Groebner.
- Arithmétique multiprécision. Inversion multiprécision (méthode de Newton, exponentiation, … ). Autres applications de la méthode de Newton (racine carrée).
- Réduction modulaire (Réduction de Montgomery, bases normales et gaussiennes si le temps le permet).
Compétences à acquérir
Notion de complexité, algorithmique nécessaire pour les codes correcteurs d’erreurs et la cryptographie classique et post-quantique.
Mots-clés
Tri, graphes, arithmétique, polynômes, calcul modulaire.
Biographie des enseignants
Gianira Alfarano est titulaire d’une chaire de professeur junior à l’université de Rennes depuis septembre 2024. Elle travaille sur les codes correcteurs d’erreurs et leurs applications en cryptographie.