Arithmétique
Note aux collègues : les documents disponibles sur cette page et dont je suis l'auteur (ou co-auteur) sont placés sous GNU FDL et vous êtes libres de les utiliser. Vous trouverez ici le source LaTeX des devoirs, et là le code C d'illustration.
Bienvenue sur cette page consacrée au module LM220 (arithmétique) de la licence math-info de l'UPMC, pour lequel j'assure en cette fin d'année 2006 les TD du groupe 2, du groupe 1, partagé avec Nicolas Billerey, et parfois des groupes 8 et 9, prêtés par un collègue et néanmoins ami. Vous trouverez ci-dessous les ressources indispensables en pdf, ainsi que des illustrations en C de certains aspects du cours.
Le cours est assuré par Jean-Jacques Risler pour les étudiants orientés math, et par Alain Kraus pour le public à tendance un peu plus informatique. Un polycopié de cours très complet, débordant parfois de ce qui est traité en amphi et sera exigible à l'examen, a été rédigé par Alain Kraus et distribué en TD. Vous pouvez aussi le télécharger en pdf.
Vous trouverez d'autres informations intéressantes pour le TD sur la page d'Esther Aflalo, qui a généreusement conçu et tapé les feuilles d'exercices disponibles sur sa page ou ci-dessous. Par ailleurs, Nicolas Billerey tient à jour une autre page LM220 (plus disponible) avec notament la progression séance par séance des groupes dont il s'occupe. Enfin, il convient de mentionner la page officielle du module, avec notamment les annales de l'an dernier.
Les indispensables
À tout seigneur, tout honneur : le polycopié de cours. Je ne saurais trop vous rappeler à quel point sa fréquentation est enrichissante.
Fidèles compagnons du cours, les feuilles d'exercices. Elles reprennent certains des exercices du cours (mais pas tous), et en proposent bien d'autres. Ci-dessous disponibles en pdf, avec une brève description et les références aux parties du cours correspondantes.
- Euclide, Bézout, et le PGCD ; groupes. (Chap. 1 et 2.)
- Arithmétique dans Z et Z/nZ. (Chap. 4, sections 1 à 4.)
- Rivest, Shamir et Adleman. (Chap. 4, section 5.)
- Polynômes sur un corps, en une variable. (Chap. 5.)
- Corps finis. (Chap. 6)
- Codes correcteurs. (Chap. 7)
Enfin, après avoir bien travaillé, il n'est pas inutile de faire le point et de tester un peu la solidité de ses (vastes) connaissances. Pour ce faire, rien de mieux que quelques devoirs, surveillés ou non.
- Un premier DS sur le programme de la feuille 1. Disponible en trois saveurs : 1, 2, et... 5 !
- Un DS sur le contenu de la feuille 2. Moins de variantes cette fois : juste 1 et 2-et-5.
- Un DM pour changer : révision générale ! Quelques questions difficiles, mais c'est pour la bonne cause : démontrer un résultat intéressant. Un corrigé de ce DM.
- Un troisième DS, sur RSA, et l'arithmétique des polynômes. Avec même des démonstrations en question de cours ! Versions 1 et 2.5.
- Un deuxième DM, autour des polynômes à coefficients entiers, et de leur éventuelle irréductibilité. Au menu : lemme de Gauss, critères d'Eisenstein et de réduction modulo p. Un corrigé possible.
- Le quatrième et dernier devoir surveillé. Il porte sur les corps finis et les calculs élémentaires qu'on peut y faire. Toujours en versions 1 et 2.5
Histoire de valider définitivement les connaissances acquises durant le semestre, et pour respecter la tradition, l'examen pointe le bout de son nez.
- Examen principal, le 15 janvier 2007, sujet et son corrigé par les enseignants.
- La deuxième session a eu lieu le 5 février : le sujet et son corrigé par les enseignants.
Des illustrations
J'encourage tous les étudiants ayant un goût pour l'informatique, surtout ceux l'ayant choisie comme orientation, à essayer d'implémenter dans le langage de leur choix les méthodes vues en cours qui sont suffisament algorithmiques pour s'y prêter. Pour citer Knuth, « Science is what we understand well enough to explain to a computer. »
Joignant le geste à la parole, j'ai commis en C quelques fragments de code illustrant certains aspects du cours. Ceux-ci n'ont pas la prétention d'être un exemple de bonne programmation en C, en particulier la gestion des erreurs est souvent sommaire voire inexistante. De plus, je n'ai jamais tenté d'optimiser la vitesse d'exécution, ce qui n'est ni le but ici, ni dans le cadre de mes compétences.
Par contre, les algorithmes sont en principe tous mathématiquement corrects, pour peu que l'utilisateur entre des valeurs dans le domaine attendu (en particulier, non nulles quand il le faut). Merci de me signaler les éventuelles erreurs, voire de me proposer des implémentations plus élégantes si vous le souhaitez.
Les sources C des exemples sont disponibles en vrac ici. Ces fichiers font également l'objet de pages explicatives, et parfois digressives. Les thèmes illustrés sont :
- L'algorithme d'Euclide étendu et certaines choses élémentaires que l'on peut faire avec.
- La méthode d'exponentiation rapide en base 2.
- Un peu de calcul modulaire : résolution de systèmes de congruences linéaires dans un cas simple et dans le cas général.
- Les principes mathématiques du cryptosystème RSA.
- D'autres choses intéressantes quand elles auront été vues en cours.
- Ah bah finalement non, c'est fini pour cette année ! :-(