Niveau: Supérieur, Master
Introduction a la Cryptologie Chapitre 3 : Euclide–Bezout et applications Michael Eisermann (Institut Fourier, UJF Grenoble) Annee 2008-2009 IF / IMAG, Master 1, S1-S2 document mis a jour le 7 juillet 2009FOURIERINSTITUTfi www-fourier.ujf-grenoble.fr/~eiserm/cours _ crypto 1/25 Objectifs de ce chapitre Developpement mathematique : Preciser le vocabulaire : divisibilit e, nombres premiers, pgcd. Etablir les lemmes de Gauss et d'Euclide, puis illustrer leur utilit e. Etablir la decomposition en facteurs premiers : existence et unicit e. Developpement algorithmique : Etablir l'algorithme d'Euclide : correction et complexit e. Etablir l'algorithme d'Euclide–Bezout : correction et complexit e. Discuter les probl emes li es a la factorisation de grands entiers. 2/25 Sommaire 1 Les algorithmes d'Euclide et d'Euclide–Bezout Divisibilit e et nombres premiers L'algorithme d'Euclide L'algorithme d 'Euclide–Bezout 2 Le theoreme fondamental de l'arithmetique Les lemmes de Gauss et d'Euclide Decomposition en facteurs premiers Probl emes algorithmiques 3 Exercices Le pire cas de l'algorithme d'Euclide Non-unicit e des coefficients de Bezout Factorielle et coefficient binomial Un joli theoreme de Dirichlet 3/25 Motivation Le theoreme fondamental de l'arithmetique dit que tout entier positif a s' ecrit de mani ere unique comme produit de nombres premiers positifs : a = 2 ? 2 · 3 ? 3
- algorithme d'euclide–bezout
- joli theoreme de dirichlet
- pgcd
- algorithme d'euclide
- pre-ordre
- algorithme d'euclide explicit
- correction du resultat renvoye
- theoreme fondamental de l'arithmetique
- preuve de correction