Algorithmique de base

• 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).

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.