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

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.

CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

(1) Dans la congruence 36x ? 80 (mod 90) on a pgcd(36

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

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 :.

Congruence - Equations diophantiennes

Cette relation est appelée la relation de congruence modulo p. Exemples Soit à résoudre le système de congruence. { x ? 5 (mod 11) x ? 7 (mod 15).

Cours S4 : Mathématiques pour linformatique

A présent essayons de résoudre des systèmes particuliers de congruences. Lemme 1.35 (Lemme chinois). On cherche à résoudre le système.

Avant propos Références 1 Questions de coût (de la vie ?)

Théorème 3.4 (Système de congruence) Soit m et n deux entiers premiers entre eux. vous pouvez commencer à résoudre les systèmes avec a = 1.

Cours darithmétique

19 Résolution de systèmes de congruences linéaires. 90. 20 Le théorème des restes chinois. 94. 21 Le théorème d'Euler. 97. Mohamed ATOUANI.

Exercices à savoir faire

Déterminer un inverse de 75 modulo 13. Exercice 4. Résoudre dans Z les systèmes de congruence suivants. (1). {?.

Observation de la transition lycée-université grâce à lanalyse

Dans les deux sujets le but est de résoudre un système de deux congruences

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

Exercice 2 Résoudre les équations. 19x ? 2 (mod 140) Exercice 3 Résoudre 42x + 150y = 18. Exercice 4 ... Exercice 15 Résoudre le système de congruences.

[PDF] Congruences et théorème chinois des restes - Apprendre-en-lignenet

Résolution des équations sur les congruences Supposons que l'on cherche à résoudre : 3x ? 5 (mod 7) Cela est facile car le modulo est premier : On sait

[PDF] chapitre 3 : congruences et arithmétique modulaire

Congruences Définition 1 1 Soit m a b entiers On dit que a est congru à b modulo m si m divise a ? b (On dit aussi que “a et b sont congrus modulo m”

[PDF] Equations diophantiennes - Congruence - livres-mathematiquesfr

x ? b (mod n) sont données par x = x0 + kmn où x0 est une solution particulière Exemple Soit à résoudre le système de congruence { x ? 5 (mod 11) x ? 7

[PDF] UN PROBLEME DE RESTES ET SA RESOLUTION PAR QIN

Qin Jiushao au XIIIe siècle résolut (ou du moins trouva une solution à) un problème de répartition de grains basé sur un système de congruences On s'

[PDF] Corrigé Feuille 4 (Congruences ) Exer

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]

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

Résoudre le système de congruences : Le système formé des deux premières équations équivaut donc à la congruence x ? a mod (3×11) avec a

[PDF] [PDF] Arithmétique - Exo7 - Cours de mathématiques

Nombres premiers · Vidéo ? partie 4 Congruences Résoudre les équations : 407x + 129y = 1 ; 720x + 54y = 6 ; 216x + 92y = 8 4 Trouver les couples (a

[PDF] Théor`eme des restes chinois - Epsilon 2000

le syst`eme de congruences défini par : ?k ? [1p]x ? ak (mod nk) admet une unique solution modulo Résoudre dans Z le syst`eme suivant :

Arithmétique dans Z: Comment résoudre un système de congruence

26 mai 2020 · Arithmétique dans Z: Comment résoudre un système de congruence - Exercice Beta Life Durée : 24:43Postée : 26 mai 2020

[PDF] Master-1 de mathématiques (MAlg 1) 2004/2005 - Institut Fourier

13 3 Résolution d'un système linéaire dans un anneau euclidien 327 Divisibilité des entiers pgcd ppcm congruences

Comment résoudre un système de congruence ?
Principe des congruences
Comment ? marche ? Pour déterminer des congruences modulo n , on élimine du nombre les multiples de n . Exemple 1 On sait que ; 15 est donc égal à un multiple de 7 plus 1 ; on a donc : On a donc un nombre limité de possibilités quand on travaille avec les congruences .
Comment fonctionne le tableau de congruence ?
Le caractère utilisé pour exprimer la congruence de deux entiers est ?.
1a ? b (n) ;2a ? b [n] ;3a ? b (mod n) ;4a ? b mod n (notation de Gauss).
Comment Ecrire congruence ?
Définition : On dit qu'un entier relatif admet un inverse modulo ( n ? N , n ? 2 ) lorsqu'il existe un entier relatif tel que a b ? 1 [ n ] . On dit aussi que est inversible modulo .

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). 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 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, 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_dbs28.pdfusesText_34