M1MI2016 : Codes et cryptologie 2012/2013 Corrigé du DS n 2 PDF

UNIVERSITÉ dORLÉANS SCL1 MA02 Département de

Arithmétique : Corrigé Feuille 4 (Congruences ). Exercice 1. Calculons le reste de 78 divisé par 6 i.e on cherche 0 ≤ x < 6 tel que. 78 ≡ x [6]. Modulo 6

M1MI2016 : Codes et cryptologie 2012/2013 Corrigé du DS n 2

Corrigé du DS n. ◦. 2. Exercice 1. Résoudre le système de congruences :.. x ≡ 1 mod 3 x ≡ 2 mod 11 x ≡ 51 mod 61. Solution. L'algorithme d

Exercices congruences.pdf

Exercices sur les congruences. Corrigé. Exercice 1. 1). 2). 3). Exercice 2. N. 0. 1. 2. 3. 4.

Exercices à savoir faire

Résoudre dans Z les systèmes de congruence suivants. (1). {︃. ≡ 3 (mod 12) Peut-on le corriger ? 3. Montrer que l'on peut détecter un chiffre inexact ou ...

DIVISIBILITE et CONGRUENCE – Feuille dexercices

Les corrigés des exercices seront à retrouver sur le Padlet Terminales Maths 2) Dans le système de numération en base 10 déterminer

Congruences et théorème chinois des restes

Cherchons à résoudre le système de congruences suivant :.. x ≡ 1 (mod 3) x ≡ 2 (mod 5) x ≡ 3 (mod 7). On pose M = 3 × 5 × 7 = 105. M1 = 105/3

Congruence

Exercice 4. On dit que a mod n est inversible si il existe b mod n tel que ab ≡ 1 mod n. 1. Trouver tous les éléments inversibles modulo 5 6

CONGRUENCES DANS Z – Exercices corrigés

Exercice 1 : Trouver le reste de la division euclidienne de 1952 par 7. Cela revient à chercher la classe de congruence de 1952 modulo 7.

CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

(d) Laissée comme exercice. (e) a − a = kn b − b = ln =⇒ ab − a b = ab système de représentants modulo p contenant 0. Alors pour chaque k parmi 1 ...

Mathématiques : du lycée aux CPGE scientifiques

exercice de niveau moyen 3 un exercice assez difficile

M1MI2016 : Codes et cryptologie 2012/2013 Corrigé du DS n 2

Exercice 1. Résoudre le système de congruences : équivaut donc à la congruence x ? a mod (3×11) avec a = 1×(?1×11)+2×(4×3) = 13. Le système se réduit ...

UNIVERSITÉ dORLÉANS SCL1 MA02 Département de

Arithmétique : Corrigé Feuille 4 (Congruences ). Exercice 1. Exercice 8. a) Factorisons 455 en produit de nombres premiers. On a 455 = 5×91 =.

Feuille 1 : Arithmétique élémentaire et congruences

Indication : on pourra traduire le problème comme un système de congruences et utiliser le théorème des restes chinois. Exercice 12 a et b sont premiers entre

Exercices congruences.pdf

Exercices sur les congruences. Exercice 1 Exercice 2. Compléter la table de congruence suivante modulo 5 ... Corrigé. Exercice 1.

Congruences et théorème chinois des restes

Résolution des équations sur les congruences. Supposons que l'on cherche à résoudre : Cherchons à résoudre le système de congruences suivant :.

Exercices corrigés arithmétique

Exercices corrigés d'arithmétique. Diviseurs –Division euclidienne : Exercice 1 : le premier et les deux derniers systèmes n'ont pas de solutions.

Congruence

Exercice 4. On dit que a mod n est inversible si il existe b mod n tel que ab ? 1 mod n. 1. Trouver tous les éléments inversibles modulo 5 6

Mathématiques pour

1.4 Congruences. 11. TD – Le codage affine. 13. Exercices corrigés 3.4 Résolution de systèmes à l'aide de matrices. 77. Exercices corrigés.

Congruences - Arithmétique Spé Maths terminale S : Exercices

Spé Maths terminale S : Exercices. Corrigés en vidéo avec le cours sur jaicompris.com. Apprendre `a calculer avec les congruences.

Exercices darithmétique

— Résoudre dans Z les congruences suivantes : 1) 3x ? 4 mod 7;. 2) 9x ? 12 mod 21;. 3) 103x ? 612 mod 676. Exercice 18. — Donner la congruence modulo 17 de (

Exercices - Congruences - bigmaths / mathématiques pour le

TS 1 Exercices Exercices - Congruences Exercice 1 Soient a b et n trois entiers naturels tels que a b[n] 1 Si a 0[n] alors ab b 0[n] donc ab 0[n] 2 4 9 = 36 = 6 6 donc 4 9 0[6] 3 Faux le preuve dans la question pr ec edente Exercice 2 Recopier et completer le tableau ci-dessous qui donne modulo 6 le produits des entiers de 0 a 5

M1MI2016 : Codes et cryptologie 2012/2013

Corrigé du DS n

◦2 Exercice 1.Résoudre le système de congruences :??x≡1 mod 3 x≡2 mod 11 x≡51 mod 61

Solution.L"algorithme d"Euclide étendu :

rkukvkqk 111 0
30 13

21 -31

1-1 42

fournit l"égalité de Bézout 4×3-1×11 = 1. Le système formé des deux premières équations

équivaut donc à la congruencex≡amod (3×11) aveca= 1×(-1×11)+2×(4×3) = 13. Le système se réduit donc à :???x≡13 mod 33 x≡51 mod 61

L"algorithme d"Euclide étendu :

rkukvkqk 611 0

330 11

281 -11

5-1 25

36 -111

2-7 131

113 -241

fournit l"égalité de Bézout 13×61-24×33 = 1. Ce système est donc équivalent à la

congruencex≡bmod (33×61) avecb= 13×(13×61) + 51×(-24×33) =-30083. Ainsi, le système équivaut à la congruence : x≡112 mod 2013 (en réduisantbmodulo 33×61 = 2013). Exercice 2.Montrer que pour toutn?Z, on an7≡nmod 42. Solution.On a 42 = 2×3×7. Soitn?Z. D"après le petit théorème de Fermat appliqué avec le nombre premier 2, on an2≡nmod 2. On a doncn7= (n2)3×n≡n4mod 2 donc n

7≡n2mod 2ien7≡nmod 2. De même on an3≡nmod 3, doncn7= (n3)2×n≡n3

mod 3ien7≡nmod 3. Enfin, on a aussin7≡nmod 7, de sorte que 2×3×7|n7-n, soit encoren7≡nmod 42. 2

Exercice 3.On pose

f:Z/256Z→Z/256Z x?→137x+ 187

et pourn?N>0, on notef(n)la fonctionfitéréen-fois, c"est-à-diref◦f◦ ··· ◦f◦f?

nfois. (1) Calculerf(2). (2) Montrer par récurrence surk?Nqu"il existe des suites (ak)k?Net (bk)k?Nd"éléments deZ/256Ztelles que : f (2k)(x) =akx+bk pour toutx?Z/256Z(on précisera la valeur deak+1en fonction deak, et celle de b k+1en fonction deaket debk). (3) Calculer les valeurs deaket debkpour 0≤k≤8 (il est conseillé de présenter le résultat sous la forme d"un tableau). En déduire que pour toutx?Z/256Z, on a f (256)(x) =x.

(4) On considère le générateur linéaire congruentiel dansZ/256Zdonné par la récurrence

linéaire : x n+1=f(xn) = 137xn+ 187 Montrer que toutes les suites engendrées par ce générateur sont de période 256, quelle que soit leur initialisation. (5) Montrer que l"applicationf(27)n"a pas de point fixe (ied"élémentx?Z/256Ztel que f (27)(x) =x). En déduire que la plus petite période de (xn)n?Nvaut 256 (on pourra d"abord montrer qu"elle divise 256). Solution.(1) On af(2)(x) =f(137x+187) = 137(137x+187)+187 = 1372x+(137+1)×187, soit : f (2)(x) = 81x+ 206 (en utilisant 137

2≡81 mod 256 et 138×187≡206 mod 256).

(2) On a bien sûrf(x) =a0x+b0aveca0= 137 etb0= 187, ce qui prouve l"énoncé pour k= 0. Supposons maintenant que (?x?Z/256Z)f(2k)(x) =akx+bk. Pourx?Z/256Z, on a : f (2k+1)(x) =f(2k)?f(2k)(x)) =akf(2k)(x) +bk =ak(akx+bk) +bk =a2kx+ (ak+ 1)bk de sorte quef(2k+1)(x) =ak+1x+bk+1avec : a k+1=a2kbk+1= (ak+ 1)bk ce qui achève la récurrence. (3) En utilisant les formules de la question précédente, on obtient : k0 1 2 3 4 5 6 7 8 ak137 81 161 65 129 1 1 1 1 bk187 206 252 120 240 224 192 128 0 3 En particulier, on af(28)(x) =xpour toutx?Z/256Z, de sorte quef(28)= IdZ/256Z. (4) D"après la question précédente, on axn+256=f(28)(xn) =xnpour toutn?N: la suite (xn)n?Nest périodique de période 256 (indépendamment dex0). (5) D"après la question (3), on af(27)(x) =x+128 pour toutx?Z/256Z: comme 128?= 0 dansZ/256Z, l"équationf(27)(x) =xn"a pas de solution,ief(27)n"a pas de point fixe. On sait que (xn)n?Nest périodique : soitT?N>0la plus petite période. D"après la question précédente, on aT≤28: soit 28=qT+rla division euclidienne de 28parT. Pour toutn?N, on axn=xn+28=xn+r+qT=xn+rparT-périodicité : la suite (xn)n?N est aussir-périodique. Commer < T, on a nécessairementr= 0 par minimalité deT, de sorte queT|28. On a doncT= 2kaveck≤8. Si on avaitk <8, on auraitT|27, doncf(27)(xn) =xn+27=xn, etxnserait un point fixe def(27)pour toutn?N. C"est impossible en vertu de ce qu"on a vu plus haut : on a nécessairementT= 28= 256. Exercice 4.Alice et Bob communiquent en utilisant le protocole RSA. La clé publique de

Bob estN= 209 ete= 7.

(1) Alice veut transmettre le messagem= 5 à Bob : quel messageMva-t-il recevoir? (2) Quelle est la clé secrète de Bob? (3) Bob reçoitM= 2 : quel est le messagemqu"Alice lui a envoyé? Solution.(1)Mest le reste de 57= 78125 modulo 209,ieM= 168. (2) On aN= 11×19, de sorte que?(209) = (11-1)(19-1) = 180. L"algorithme d"Euclide

étendu :

rkukvkqk

1801 0

70 125

51 -251

2-1 262

13 -772

fournit l"égalité de Bézout 3×180-77×7 = 1. Comme-77≡103 mod 180, la clé secrète

de Bob estd= 103. (3)mest le reste de 2103modulo 209. On a 27= 128<209<28= 256 : écrivons

103 = 8×12 + 7. On a 28≡47 mod 209, donc :

k1 2 4 12

28k47 119 158 64

Ainsi, 2103≡64×128 mod 209, soitm= 41.

On peut aussi utiliser le théorème chinois pour calculerm. On a 210≡1 mod 11 donc 2

103≡23mod 11iem≡8 mod 11, et 218≡1 mod 19 donc 2103≡213mod 19iem≡3

mod 19 : on vérifie sans peine quem= 41 en utilisant l"égalité de Bézout 7×11-4×19 = 1.

quotesdbs_dbs2.pdfusesText_2

[PDF] M1MI2016 : Codes et cryptologie 2012/2013 Corrigé du DS n 2