L3  Mathématiques          2015-2016
Algèbre effective



Responsable du module :  Frédéric Eyssette
Page du L3 Mathématiques  et  Emploi du temps  ,  Calendrier universitaire 
Responsable du L3 Mathématiques : Clemens Berger

Comment utiliser le logiciel SAGE .

Horaires
12 Cours Magistraux d'1h30, 12 Travaux Dirigés ou Travaux Pratiques d'1h30
CM : lundi 13h15-14h45 M 3.2
TD ou TP : lundi 15h-16h30 M 3.2 ou PV 215

Contrôle
Il y aura 3 notes :
- 1 Contrôle en Cours d'1h30, le 19 octobre [C1]
- 1 Contrôle en Cours et en TP d'1h+1h30, le 14 décembre [C2]
- 1 Contrôle Terminal Écrit de 2h [CT]
Note finale en session 1 = 0,4*CT + 0,3*(C1+C2)

Note finale en session 2 = un autre Contrôle Terminal Écrit de 2h

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.

Le programme sera choisi parmi :

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

Comment utiliser le logiciel SAGE .

Semaine 1 (7 septembre) :
CM 1 : Présentation, calcul de pgcd d'entiers, algorithme d'Euclide, relations de Bézout, algorithme d'Euclide étendu.
TD 1 : Pgcd d'entiers, relations de Bézout, théorème de Gauss :  le TD1  , 

Semaine 2 (14 septembre) :
CM 2 : Applications des relations de Bézout : équations Diophantiennes linéaires, théorème des restes chinois, inverses dans Z/nZ, (Z/nZ)*, fonction d'Euler phi(n).
TP 1 : Calcul de pgcd d'entiers, algorithme d'Euclide, complexité :  le TP1  ,  un corrigé en Sage  et  en pdf 
Comment utiliser le logiciel SAGE

Semaine 3 (21 septembre) :
CM 3 : Théorèmes de Fermat, d'Euler. Ordre d'un élément inversible de Z/nZ.
TD 2 : Calculs dans Z/nZ, Fonction d'Euler phi(n) :  le TD2

Semaine 4 (28 septembre) :
CM 4 : Test de primalité. Nombres pseudo-premiers, de Carmichael.
TP 2 : Relations de Bézout et applications :  le TP2 en Sage  et  en pdf  ,  un corrigé en Sage  et  en pdf 

Semaine 5 (5 octobre) :
CM 5 : Test de primalité (suite) : Puissances rapides.
TD 3 : Théorèmes de Fermat, d'Euler. Ordre d'un élément inversible de Z/nZ :  le TD3

Semaine 6 (12 octobre) :
CM 6 : Test de primalité (fin) : Test de Miller. Codes cryptographiques RSA.
TP 3 : Nombres pseudo-premiers, de Carmichael :  le TP3 en Sage  et  en pdf  ,  un corrigé en Sage  et   en pdf

Semaine 7 (19 octobre) :
[C1] : Contrôle : le sujet

Semaine 8 (26 octobre-1er novembre) :
Pause Pédagogique

Semaine 9 (2 novembre) :
Désolé : je suis absent (malade).
Que ça ne vous empêche pas de travailler le TD4 !
CM 7 : Résolution de x2 = 1 (mod n). Générateurs de (Z/nZ)*.
TD 4 : Résolution de x2 = 1 (mod n). Générateurs de (Z/nZ)*:  le TD4  et  un corrigé 

Semaine 10 (9 novembre) :
CM 8 : Résolution de x2 = 1 (mod n). Générateurs de (Z/nZ)*.
TP 4 : Efficacité du Test de Miller :  un corrigé en Sage  et  en pdf 

Semaine 11 (16 novembre) :
CM 9 : Générateurs de (Z/nZ)*.
TD 5 : Résolution de x2 = 1 (mod n). Générateurs de (Z/nZ)*:  le TD4  et  un corrigé 

Semaine 12 (23 novembre) :
CM 10 : Polynômes. Division Euclidienne. Pgcd, algorithme d'Euclide. Polynômes premiers entre eux, irréductibles.
TP 5 : Polynômes. Pgcd, algorithme d'Euclide :  le TP5 en Sage  et  en pdf  ,  un corrigé en Sage  et  en pdf 

Semaine 13 (30 novembre) :
CM 11 : Factorisation. Polynômes primitifs.
TD 6 : Polynômes. Division Euclidienne, Pgcd. Racines. Polynômes premiers entre eux, irréductibles :  le TD5  et  un corrigé partiel 

Semaine 14 (7 décembre) :
CM 12 : Facteurs multiples. Décomposition sans facteur multiple. Racines multiples.
TP 6 :  le TP6 en Sage  et  en pdf  ,  un corrigé en Sage  et  en pdf 

Semaine 15 (14 décembre) :
[C2] : Contrôle :  le sujet sur papier  et  le sujet en Sage   

Examen [CT] : Lundi 11 janvier 13h-15h Amphi M (H. Poincaré)