Algèbre et Arithmétique Effectives
Université Grenoble Alpes - 2024/2025
Cette page est dédiée au cours d'Algèbre et Arithmétique Effectives (L3 Informatique, Parcours Mathématiques et Informatique) de l'année académique 2024/2025 à l'Université Grenoble Alpes.
Page Web L3MIModalités de ControlePRESENTATION DU COURS - SLIDES
Horaire et lieu des cours:
Mardi : 8h – 9h30 (CM) et 9h45 – 11h (TD) en F116 (Bâtiment F, Campus de Saint-Martin-d'Hères)
Mercredi : 13h30 – 15h (TP) en F213 (Bâtiment F, Campus de Saint-Martin-d'Hères)
Références :
- La page web de M. Bruno Grenet (pour le cours de AAE en 2022/2023 et 2023/2024).
- Cours d’algèbre, Michel Demazure, Paris : Cassini, 2ème édition (2008). (Plusieurs exemplaires disponibles à la bibliothèque Joseph Fourier.)
- A Computational Introduction to Number Theory and Algebra, Victor Shoup, Cambridge University Press, 2nd edition, 2009. (Téléchargeable librement en cliquant sur le lien.)
- Modern Computer Algebra, Joachim von zur Gathen et Jürgen Gerhard, Cambridge University Press, 3rd edition (2013). (Plusieurs exemplaires disponibles à la bibliothèque Joseph Fourier.)
Informations pour les étudiants
Cahier de bord :
- 10/09/2024 : Présentation du cours. Rappels de divisibilité: $a$ divise $b$, diviseur commun, plus grand commun diviseur (pgcd), nombres premiers entre eux. Algorithme originaire d'Euclide par soustraction et pseudo-code. Preuve de terminaison et correction. Algorithme de Division Euclidienne par soustraction et pseudo-code. Algorithme d'Euclide classique et pseudo-code. Démonstration de quelques énoncés de divisibilité.
TD1: Exercice 1.
PRESENTATION DU COURS - SLIDESCours 1TD 1 - 11/09/2024 : TP1 - partie 1. Pour la prochaine fois, s'assurer d'avoir complété les premiers 7 exercices (jusqu'à la division euclidienne avec des entiers relatifs).
TP 1 - 17/09/2024 : Quelques rappels de théorie de la complexité: taille d'un entier, notation asymptotique (Grand-$O$, Grand-$\Omega$, $\Theta$). Coût de l'algorithme d'Euclide (borne supérieure sur le nombre de divisions euclidiennes). Variante de l'algorithme binaire du PGCD. Identité de Bézout et Algorithme d'Euclide Étendu. Exemples.
TD1: Exercices 2,3,4.
Cours 2TD 1 - 18/09/2024 : TP1 - partie 2. Un exercice sur l'algorithme d'Euclide Étendu a été ajouté au fichier précédent. Pour la prochaine fois, terminer tous les exercices du fichier.
TP 1 - 24/09/2024 : Preuve de correction de l'algorithme d'Euclide Étendu. Rappels: définitions de nombre premier et composé. Lemme de Gauss (avec démonstration). Théorème Fondamental de l'Arithmétique (avec démonstration). Rappels: définition de relation d'équivalence, classes d'équivalence et ensemble des classes d'équivalence.
TD1: Exercice 6. TD2: Exercice 1, 4.
Cours 3TD 1TD 2 - 25/09/2024 : TP2. Pour la prochaine fois, terminer tous les exercices du fichier.
TP 2 - 30/09/2024 : Définition de rélation d'équivalence modulo $n$. Exemples pour $n=1,2,3$. Notation $\mathbb Z/n\mathbb Z.$ Théorème: pour toute classe d'équivalence de $\mathbb Z/n\mathbb Z$ il existe un représentant canonique entre 0 et $n-1$, qui est donné par le reste de la division euclidienne. Opérations d'addition et multiplication sur $\mathbb Z/n\mathbb Z$. Démonstration qu'elles sont bien définies. Propriétés des opérations. Définition d'élément inversible dans $\mathbb Z/n\mathbb Z$. Proposition: $a$ est inversible dans $\mathbb Z/n\mathbb Z$ si et seulement si pgcd$(a,n)=1$. Algorithme pour calculer l'inverse d'un élément dans $\mathbb Z/n\mathbb Z$.
Cours 4 - 01/10/2024 : Exemples sur le calcul de l'inverse d'un élément de $\mathbb Z/n\mathbb Z$. L'ensemble $\left(\mathbb Z/n\mathbb Z\right)^{\times}$ des éléments inversibles. Si $p$ est premier alors $\mathbb Z/p\mathbb Z$ est un corps. Résolution de congruences linéaires (existence des solutions et calcul des solutions). Résolution d'un système de congruences linéaires: algorithme des restes chinois et preuve de correction.
TD3: Exercice 1,2,3,4,5. Terminer (ou au moins essayer) tous les exercices du TD3 pour la prochaine séance (vendredi 4/10).
Cours 5TD 3 - 02/10/2024 : TP3. Pour la prochaine fois, s'assurer d'avoir complété les premiers 8 exercices (jusqu'au théorème des restes chinois).
TP 3 -
04/10/2024 : TD4: Exercices 1 et 2.
TD 4 - 08/10/2024 : TD4: Exercices 3 et 4. Correction exercices du TD4.
Définition de groupe. Exemples. Ordre d'un groupe. Théorème de Lagrange (version 1), avec démo. Définition de sous-groupe d'un groupe. Exemples. Proposition pour montrer qu'un sous-ensemble non vide est un sous-groupe. Le sous-groupe engendré par un élément. L'ordre d'un élément. Définition de groupe cyclique.
Cours 6TD 4 - 09/10/2024 : TP4.
TP 4 - 23/10/2024 : Contrôle continu.
CC - 05/11/2024 : Exemples de groupes cycliques. Relation de congruence modulo un sous-groupe et groupe quotient. Théorème de Lagrange (version 2). Définitions d'anneau, corps, diviseurs de zéro, anneau intègre. Exemples. TD5: Exercices 1 et 2.
Cours 7TD 5 - 06/11/2024 : Définition d'idéal d'un anneau. Relation de congruence modulo un idéal et anneau quotient. Définition d'homomorphisme de groupes, image et noyau. Exemples.
TD5: Exercice 4.
TP4: Continuation TP4.
Cours 8TD 5TP 4 - 12/11/2024 : TD5: Correction exercice 4 et 5. Quelques remarques et propositions sur les homomorphismes de groupes. Définition d'isomorphisme. Exemples. Premier théorème d'isomorphisme (de groupes), avec démonstration.
Cours 9TD 5 - 13/11/2024 : TP4: Échange de clé à la Diffie-Hellmen et problème du logarithme discret. Continuation du TP4.
TP 4 - 17/11/2024 : Exemple d'application du premier théorème d'isomorphisme. Définition d'homomorphisme d'anneaux, image et noyau. Quelques remarques et propositions sur les homomorphismes d'anneaux. Définition d'isomorphismes. Premier théorème d'isomorphisme (d'anneaux). Version du théorème des restes chinois en termes d'isomorphismes d'anneaux.
TD6: Exercice 1 et 2.
Cours 10TD 6