Algorithmique des corps finis

6 ECTS - 27 CM / 18 TD / 15 TP

Description

Les corps finis sont utilisés en cryptographie et pour diverses applications en télécommunication (codes correcteurs d’erreurs,…). Ils sont aussi indispensables pour de nombreux algorithmes du calcul formel (factorisation de polynômes à coefficients rationnels, étude de suites d’entiers,…), ainsi que pour la théorie des nombres et certaines des méthodes de calcul associées.

• Construction, représentation et calculs dans les corps finis. Comparaison de diverses représentations.
• Etude du groupe multiplicatif.
• Algorithmes de base pour le calcul de logarithmes discrets: pas de géant/pas de bébé, algorithme rho de Pollard, Pohlig-Hellman.
• Algorithmes de factorisation des polynômes: méthode de Berlekamp, méthode de Zassenhauss.
• Lien entre corps finis et suites linéaires récurrentes, algorithme de Berlekamp-Massey.
• Programmation de certains algorithmes.

Objectifs