L3 Mathématiques 2011-2012
Algèbre effective
Responsable du module : Frédéric Eyssette
Responsable du L3 Mathématiques : Adam Parusiński
Horaires
12 Cours Magistraux d'1h30, 12 Travaux Dirigés d'1h30, 12 Travaux Pratiques d'1h30
CM : mercredi 13h15-14h45 amphi Biologie
TD : vendredi 10h15-11h45 M 3.1
TP : vendredi 8h30-10h PV 212 et 213
Contrôle
Il y aura 4 notes :
- 2 TP [CTP1, CTP2]
- 1 Partiel en cours [CP]
- 1 Contrôle Terminal [CT]
Note finale = 0,4*CT + 0,2*(CTP1+CTP2+CP)
Programme détaillé
Lontemps considéré comme purement théorique l'arithmétique est
aujourd'hui au cœur d'applications comme les codes correcteurs utilisés
entre autres pour la lecture des CD/DVD ou les codes secrets à clé
public utilisés pour les échanges sécurisés sur Internet.
Le but de ce module est de vous en faire comprendre les bases mathématiques et d'aller jusqu'aux applications.
Arithmétique sur les entiers
1) Calculs de pgcd et relation de Bézout
Algorithme d'Euclide
Suite de Fibonacci et complexité de l'algorithme d'Euclide
Calcul des coefficients de Bézout : algorithme d'Euclide étendu
2) Équations diophantiennes linéaires
Résolution de congruences et de systèmes de congruences par l'algorithme d'Euclide étendu
Équations diophantiennes linéaires à 2 ou 3 variables
Calcul d'inverse dans Z/nZ
Théorème des restes chinois
Exemples
3) Nombres premiers et Tests de primalité
Petit théorème de Fermat, nombres pseudo-premiers, nombres de Carmichael
Test de primalité
Test de Miller-Rabin
4) Calculs dans Z/nZ
Caractérisation des éléments inversibles
Groupe des éléments inversibles
Nombre d'éléments inversibles, calcul de ce nombre
Théorème d'Euler généralisant celui de Fermat
Ordre d'un élément inversible
5) Codes secrets
Puissances rapides modulaires
Cryptage RSA
6) Algorithmes de factorisation
Décomposition d'un entier en facteurs premiers
Méthode rho de Pollard
Arithmétique sur les polynômes
1) Calculs de pgcd et relation de Bézout
Algorithme d'Euclide étendu pour les polynômes à une variable
Elimination des dénominateurs
Croissance des coefficients
2) Décomposition d'un polynôme en produit de polynômes sans facteur multiple
Dans Q[x]
Dans Z/pZ[x]
3) Factorisation d'un polynôme à coefficients dans Z/pZ
Algorithme de Berlekamp
Séances
TP 0 : Un bref survol de Maple et la
correction (en Maple) et en pdf , un mémento
Semaine 1 (5-9 septembre) : CM uniquement
CM 1 : Présentation, calcul de pgcd d'entiers, algorithme d'Euclide, complexité, relation de Bézout, algorithme d'Euclide étendu
Semaine 2 (12-16 septembre)
CM
2 : Applications de la relation de Bézout, équations
Diophantiennes linéaires, inverses dans Z/nZ, théorème des restes
chinois
TD 1 : Calcul de pgcd d'entiers et relations de Bézout
TP 1 : Calcul de pgcd d'entiers et relations de Bézout (en Maple) et en pdf , un corrigé en Maple et en pdf
Semaine 3 (19-23 septembre)
CM 3 : Nombres premiers, Petit théorème de Fermat, Test de primalité
TD 2 : Équations diophantiennes linéaires , un corrigé de l'exercice 3
TP 2 : Équations diophantiennes linéaires (en Maple) et en pdf , un corrigé en Maple et en pdf
Semaine 4 (26-30 septembre)
CM 4 : Nombres pseudopremiers, nombres de Carmichael, test de Miller-Rabin
TD 3 : Nombres premiers et pseudopremiers
TP 3 : Tests de primalité (en Maple) et en pdf , un corrigé en Maple et en pdf
Semaine 5 (3-7 octobre)
CM 5 : Calcul dans Z/nZ, nombre d'éléments inversibles, théorème d'Euler, ordre d'un élément
TD 4 : Calculs dans Z/nZ
TP 4 : Contrôle en TP [CTP1] le sujet en Maple et en pdf , un corrigé en Maple et en pdf
Semaine 6 (10-14 octobre) : Fête de la Science
CM 6 : Générateurs de (Z/nZ)*
TD 5 : Calculs dans Z/nZ
TP 5 : Calculs dans Z/nZ en Maple et en pdf , un corrigé en Maple et en pdf
Semaine 7 (17-21 octobre)
CM 7 : Code cryptographique RSA, puissances rapides
TD 6 : Générateurs de (Z/nZ)* , un corrigé
TP 6 : Puissances rapides, RSA en Maple et en pdf , un corrigé en Maple et en pdf
Semaine 8 (24-28 octobre)
CM 8 : Décomposition d'un entier en facteurs premiers : méthode naïve, factorisation de grands entiers : méthode rho de Pollard
TD 7 : Révision, Factorisation des entiers
TP 7 : Factorisation des entiers : méthode naïve (en Maple) et en pdf , un corrigé en Maple et en pdf
Semaine 9 (7-10 novembre) : Pas de TD ni TP, vendredi 11 novembre
CM : Désolé
Semaine 10 (14-18 novembre)
CM : Contrôle Partiel en cours [CP] : le sujet et le corrigé
TD 8 : Polynômes à une variable Q[x], Z[x], Z/pZ[x]. Calcul du pgcd, algorithme d'Euclide, relation de Bézout.
TP 8 : Factorisation de grands entiers : Méthode rho de Pollard en Maple et en pdf , son corrigé en Maple et en pdf
Semaine 11 (21-25 novembre)
CM
9 : Polynômes à une variable Q[x], Z[x], Z/pZ[x]. Calcul du pgcd,
algorithme d'Euclide, relation de Bézout. Décomposition d'un polynôme
en produit de polynômes sans facteur multiple
TD 9 : Polynômes à une variable
TP 9 : Décomposition d'un polynôme en produit de polynômes sans facteur multiple (en Maple) et en pdf , un corrigé en Maple et en pdf
Semaine 12 (28 novembre-2 décembre)
CM 10 : Factorisation dans Z/pZ[x], l'algorithme de Berlekamp
TD 10 : Polynômes encore
TP 10 : Contrôle en TP [CTP2] le sujet en Maple et en pdf , un corrigé en Maple et en pdf
Semaine 13 (5-9 décembre)
CM 11 : Factorisation dans Z/pZ[x], un example
TD 11 : Factorisation dans Z/pZ[x], Polynômes toujours
TP 11 : Factorisation dans Z/pZ[x] en Maple et en pdf , un corrigé en Maple et en pdf
Semaine 14 (12-16 décembre)
CM 12 : Factorisation dans Z[x]
TD 12 : Pgcd de polynômes, polynômes irréductibles : Un exercice de rédaction
TP 12 : Factorisation dans Z/pZ[x] en Maple et en pdf
Mardi 17 janvier
Contrôle terminal [CT] : le sujet et un corrigé