Cours d'arithmétique - 2 ème année de DUT

Informations

• Publié par: Neseng
• Nombre de lectures: 31
• Langue: Français

Extrait

Arithm´etique i`eme2 ann´ee de DUT Informatique Version 2.1 3 f´evrier 2009 Ph. Roux 2002-2009Table des mati`eres Table des mati`eres 2 1 cours magistral 3 1.1 Divisibilit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 L’algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Identit´es de Bezout . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.3 Conversion d’un entier en base p . . . . . . . . . . . . . . . . 7 1.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 Th´eor`eme de d´ecomposition en facteurs premiers . . . . . . . 8 1.2.2 Recherche de grands nombres premiers . . . . . . . . . . . . . 12 1.3 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.1 Calcul modulo n . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.2 Le Th´eor`eme Chinois . . . . . . . . . . . . . . . . . . . . . . . 25 1.4 L’ensemble Z/nZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4.1 Structure d’anneau et de corps . . . . . . . . . . . . . . . . . 29 1.4.2 Polynˆomes et r´esidus quadratiques . . . . . . . . . . . . . . . 34 1.4.3 G´en´erateurs deZ/nZ . . . . . . . . . . . . . . . . . . . . . . . 38 1.5 Cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.5.1 Codage d’un texte ou d’un document . . . . . . . . . . . . . . 39 1.5.2 Les principes de la cryptographie moderne . . . . . . . . . . . 41 1.5.3 Cryptosyst`eme `a cl´e sym´etrique: Le DES . . . . . . . . . . . . 44 1.5.4 Cryptosyst`eme `a cl´e asym´etrique: le RSA . . . . . . . . . . . 45 1.5.5 Protection des cartes bancaires . . . . . . . . . . . . . . . . . 48 1.6 Autres Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 1.6.1 les fonctions de Hachage . . . . . . . . . . . . . . . . . . . . . 51 1.6.2 Codes correcteurs d’erreurs . . . . . . . . . . . . . . . . . . . 53 1.7 Aspect historiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 1.7.1 l’arithm´etique dans l’antiquit´e . . . . . . . . . . . . . . . . . . 55 1.7.2 Pierre de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . 55 1.7.3 Marin Mersenne . . . . . . . . . . . . . . . . . . . . . . . . . . 56 1.7.4 Cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 1.7.5 RSA data-security . . . . . . . . . . . . . . . . . . . . . . . . 57 1.7.6 Le bug du P*ntium . . . . . . . . . . . . . . . . . . . . . . . . 58 1.7.7 l’histoire de GNUPG . . . . . . . . . . . . . . . . . . . . . . . 59 Bibliographie 61 2DUT Informatique Arithm´etique Math´ematiques Chapitre 1 cours magistral L’arithm´etique est la partie des math´ematiques qui ´etudie les ensembles ∗N ={0; 1; 2; ...}, N ={1; 2; ...}, Z ={...; −2; −1; 0; 1; 2; ...} munis des op´erations naturelles qui leur sont associ´ees: • l’addition + • la multiplication× • et la divisibilit´e | Ces op´erations sont bien suˆr ind´ependantes de la mani`ere dont on repr´esente les nombres entiers. Par d´efaut on repr´esente les nombres entier en base 10: nX k n n−1 2x = (a a ...a a a ) = a 10 =a ×10 +a ×10 +...a ×10 +a ×10+an n−1 2 1 0 10 k n n−1 2 1 0 k=0 ou` leschiffresa ...a ,a appartiennent `a{0; 1; 2; ...9}maisonpourraittoutaussin 1 0 bien travailler dans une base p quelconque, ou` la notation des entiers est d´efinie par nX k n n−1 2x = (b b ...b b b ) = b p =b ×p +b ×p +...b ×p +b ×p+bn n−1 2 1 0 p k n n−1 2 1 0 k=0 ou` leschiffrescettefoisappartiennent`a{0; 1; 2; ...p}.Celaposeunprobl`emepour les bases p > 10 (les chiffres de 0 `a 9 ne suffisent plus). Pour r´esoudre ce probl`eme on peut utiliser soit des groupements de chiffres soit des lettres pour remplacer les chiffres manquants. Par exemple en Hexad´ecimal (base 16) on peut utiliser les chiffres: 1; 2; 3; 4; 5; 6; 7; 8; 9; A; B; C; D; E; F ou 01; 02; 03; 04; 05; 06; 07; 08; 09; 10; 11; 12; 13; 14; 15 alors (123456789) = (111010110111100110100010101) = (75BCD15) ou (07051112130105)10 2 16 16 La longueur de l’´ecriture d’un nombre x en base p est la partie enti`ere de ln(x) ln (x) =p ln(p) 3  ( 0 ? :  : + : N ( - q 1) 1) b  q b 2) q b  a b r ( + q - DUT Informatique Arithm´etique Math´ematiques 1.1 Divisibilit´e 1.1.1 L’algorithme d’Euclide D´efinition 1.1.1 On dit qu’un entier a divise un autre entier b si et seulement si il existe un entier c tel que b =a×c ce qu’on note a|b. Si a ne divise pas b on le note a∤b. Les r`egles ´el´ementaires de divisibilit´e: • ∀a∈Z 1|a, a|a, a|0, et 0∤a • si a|b alors∀c∈Z, a|bc • si a|b et a|c alors∀x,y∈Z a|bx+cy • si a|b et b|c alors a|c • si a|b et b|a alors a =±b • si a> 0, b> 0 et a|b alors a≤b ´D´efinition 1.1.2 Etant donn´e deux entiers a et b on note • PGCD(a,b) le plus grand entier naturel qui divise a et b, • PPCM(a,b) le plus petit multiple commun a` a et b. Th´eor`eme 1.1.3 (Division Euclidienne) ∗ ∗∀a∈Z, b∈N , ∃!(q,r)∈Z×N tel que a =b×q+r avec 0≤r