Introduction a la Cryptologie - Euclide–Bezout et applications

Michael Eisermann

Description

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

Sujets

• Théorème fondamental de l'arithmétique
• Pré-ordre
• Algorithme d'Euclide

Informations

• Publié par: profil-infoe-2012
• Nombre de lectures: 27
• Langue: Français

Extrait