Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Introduction a la Cryptologie - Euclide–Bezout et applications

De
7 pages
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


Voir plus Voir moins

Vous aimerez aussi