Fondement de L’Algorithmique Algébrique  (FLAG)

Mots-clés.

Algorithme, algèbre linéaire efficace, applications cryptographie et codes.

Langue d’enseignement.

Français, certains documents fournis en anglais.

Résumé.

Cette UE est la suite de la partie calcul formel de MODEL.

Il s’agit de présenter des algorithmes rapides fondamentaux pour le calcul formel sur les entiers et les polynômes en une variable. Pour cela, nous nous appuyerons fortement sur l’algèbre linéaire.

Nous montrerons d’abord comment linéariser certains problèmes afin de les résoudre. Les systèmes linéaires qui en découlent ont souvent une certaine structure provenant naturellement du problème originel. C’est pourquoi, nous montrerons ensuite comment nous pouvons exploiter l’algèbre linéaire structurée afin de nous affranchir des complexités classiques de l’algèbre linéaire dense et résoudre certains de ces systèmes en temps sous-quadratique.

Ces problèmes trouvent des applications en cryptographie et en théorie des codes, par exemple. Une implantation rigoureuse de ces algorithmes sera aussi étudiée.

Semainier.

  1. Introduction aux corps finis
  2. Demi-pgcd : l’algorithme d’Euclide rapide
  3. Algèbre linéaire structurée I : interpolation rapide de polynômes et partage de clef secrète de Shamir
  4. Algèbre linéaire structurée II : systèmes linéaires creux et algorithme de Wiedemann
  5. Factorisation de polynôme sur un corps fini
  6. Anneaux d’entiers p-adiques, remontée de Hensel et reconstruction rationnelle
  7. Introduction à la théorie des codes et codes cycliques
  8. Résultant, systèmes polynomiaux et tours d’extensions

Modalités d’évaluation.

Deux examens répartis comptant pour 50% de la note finale chacun.

Répartition horaire.

 

Équipe pédagogique.

L’équipe pédagogique est constituée de


Ce document a été traduit de LATEX par HEVEA