par Pierre » mar. 9 janv. 2018 20:40
Bonjour,
Je suis de retour avec vous pour bosser sur un sujet
type bac concernant le
chiffrement affine.
Je vous propose à l'issu de l'énoncé mes réponses, n'hésitez pas à me dire s'il y a quelque chose qui ne va pas : il s'agit d'un
travail noté.
Pour coder un message, on traduit d'abord chaque lettre en son équivalent numérique : le A=0, B=1,..., Z=25.
Soit \((E)\) l'ensemble des entiers naturels compris entre 0 et 25.
On définit le système de codage à l'aide de la transformation \(f\) suivante :
Si \(x \in E\) alors \(x\)\(\longrightarrow\)\(y\) où \(y\) est le reste de la division euclidienne de \(ax+b\) par 26, \(a\) et \(b\) entiers de \(E\) et \(a \neq 0\).
Exemple : Pour coder la lettre P avec \(a = 2\) et \(b = 3\), on procède de la manière suivante :
-
étape 1 : on lui associe l'entier n = 15.
-
étape 2 : le reste de la division de \(2 \times 15 + 3 = 33\) par 26 est 7.
-
étape 3 : on associe 7 à H. Donc P est codé par la lettre H.
1) Que dire alors du code obtenu lorsque l'on prend \(a = 0\) ?
2) a) Montrer que les lettres A et C sont codées par la même lettre lorsque l'on choisit \(a = 13\). En quoi est-ce un problème ?
b) Existe-t-il d'autres valeurs de \(a\) pour lesquelles on a le même problème ?
3) Dans toute la suite de l'exercice, on prend \(a = 5\) et \(b = 2\).
a) On considère deux lettres de l'alphabet associées respectivement aux entiers \(n\) et \(p\).
Montrer, que si \(5n+2\) et \(5p+2\) ont le même reste dans la divison par 26, alors \(n-p\) est un multiple de 26.
En déduire que \(n = p\). Que peut-on en conclure ?
b) Coder le mot NOEL.
4) On se propose de décoder la lettre \(E\).
a) Montrer que décoder la lettre \(E\) revient à déterminer l'élément \(n\) de \(\Omega\) tel que \(5n-26y=2\), où \(y\) est un entier.
b) Déterminer un couple \((n ; y)\) solution de l'équation précédente avec \(0 \leq n \leq 25\).
c) Décoder alors la lettre E.
5) Décoder le mot VUSWYN.
Vous trouverez ci-dessous mes réponses, n'hésitez pas à me dire s'il y a quelque chose qui ne va pas : il s'agit d'un
travail noté.
1) Si \(a=0\), alors pour tout \(n\), \(an+b=b\). Toutes les lettres de l'alphabet sont associées au même nombre donc elles seront codées par la même lettre correspondant au reste de la division de \(b\) par 26.
2) a) A et C sont respectivement associées à \(b\) et \(26+b\), ils ont le même reste modulo 26. En effet :
\(A = 0\) \(\longrightarrow\) \(13\times0+b=b\) \(\longrightarrow\) \(\frac{b}{26}\) \(\longrightarrow\) \(r=b\)
\(C = 2\) \(\longrightarrow\) \(13\times2+b=26+b\) \(\longrightarrow\) \(\frac{26+b}{26}\) \(\longrightarrow\) \(r=b\)
A et C sont codées par la même lettre si \(a=13\).
C'est un problème car on ne peut pas faire de distinction de codage entre les lettres A et C. Chaque lettre constituant le mot peut correspondre à plusieurs lettres.
b) Si on prend \(a=2\), \(2x+b\equiv r(mod.26)\) et que \(x=13\) on a \(26+b\equiv r(mod.26)\), comme \(26\equiv 0(mod.26)\) alors \(26+b\equiv b(mod.26)\) et donc \(r\equiv b(mod.26)\).
Si \(x=0\), on a \(2\times0+b\equiv r(mod.26)\) soit aussi \(r\equiv b(mod.26)\). Donc, si \(a=2\) on a aussi un problème.
3) a) On a :
\(5n+2\equiv 5p+2(mod.26)\)
\(5n\equiv 5p(mod.26)\)
\(n\equiv p(mod.26)\) car 5 est premier avec 26
\(n-p\equiv 0(mod.26)\)
Si \(5n+2\) et \(5p+2\) ont le même reste dans la division euclidienne par 26 alors \(n-p\) est un multiple de 26.
On a :
\(0 \leq n \leq 25\)
\(-25 \leq -p \leq 0\)
Donc \(-25 \leq n-p \leq 25\)
Or, le seul et unique multiple de 26 entre -25 et 25 est 0, donc \(n-p=0\) soit \(n=p\).
Si on prend \(a=5\) et \(b=2\), chaque lettre code une lettre distincte. De plus, si \(a \neq D(26)\) alors chaque lettre code une lettre distincte.
b) \(N = 13\) \(\longrightarrow\) \(5\times13+2=67\) \(\longrightarrow\) \(\frac{67}{26}\) \(\longrightarrow\) \(r=15\) \(\longrightarrow\) \(15=P\)
\(O = 14\) \(\longrightarrow\) \(5\times14+2=72\) \(\longrightarrow\) \(\frac{72}{26}\) \(\longrightarrow\) \(r=20\) \(\longrightarrow\) \(20=U\)
\(E = 4\) \(\longrightarrow\) \(5\times4+2=22\) \(\longrightarrow\) \(\frac{22}{26}\) \(\longrightarrow\) \(r=22\) \(\longrightarrow\) \(22=W\)
\(L = 11\) \(\longrightarrow\) \(5\times11+2=57\) \(\longrightarrow\) \(\frac{57}{26}\) \(\longrightarrow\) \(r=5\) \(\longrightarrow\) \(5=F\)
Le mot NOEL, codé avec \(a=5\) et \(b=2\) nous donne PUWF.
4) a) E correspond à 4.
Ainsi, la lettre codée E correspond à un nombre \(n\) tel que :
\(\Longleftrightarrow 5n+2\equiv 4(mod.26)\)
\(\Longleftrightarrow 5n-2\equiv 0(mod.26)\)
\(\Longleftrightarrow 5n-2 = 26y\) où y est un entier relatif
\(\Longleftrightarrow 5n-2=26y\)
\(\Longleftrightarrow 5n-26y=2\)
b) A l'aide de la calculatrice, le couple \((16;3)\) est solution de \(5n-26y=2\) où y est un entier relatif et \(0 \leq n \leq 25\).
c) D'après la question 4) b), la lettre dont le code est E est la lettre associée à 16 c'est-à-dire la lettre Q.
5) \(V=21 \longrightarrow 5n+2-26y=21 \longrightarrow (n;y)=(9;1) V\longrightarrow J\)
\(U=20 \longrightarrow 5n+2-26y=20 \longrightarrow (n;y)=(14;2) V\longrightarrow O\)
\(S=18 \longrightarrow 5n+2-26y=18 \longrightarrow (n;y)=(24;4) V\longrightarrow Y\)
\(W=22 \longrightarrow 5n+2-26y=22 \longrightarrow (n;y)=(4;0) V\longrightarrow E\)
\(Y=24 \longrightarrow 5n+2-26y=24 \longrightarrow (n;y)=(20;3) V\longrightarrow U\)
\(N=13 \longrightarrow 5n+2-26y=13 \longrightarrow (n;y)=(23;4) V\longrightarrow X\)
VUSWYN code pour le mot JOYEUX (quelle coïncidence).
Bonne soirée à vous et merci de m'avoir lu, ce travail est très important pour moi.
Pierre.
Bonjour,
Je suis de retour avec vous pour bosser sur un sujet [b]type bac[/b] concernant le [b]chiffrement affine[/b].
Je vous propose à l'issu de l'énoncé mes réponses, n'hésitez pas à me dire s'il y a quelque chose qui ne va pas : il s'agit d'un [b]travail noté[/b].
[quote]Pour coder un message, on traduit d'abord chaque lettre en son équivalent numérique : le A=0, B=1,..., Z=25.
Soit [tex](E)[/tex] l'ensemble des entiers naturels compris entre 0 et 25.
[quote]On définit le système de codage à l'aide de la transformation [tex]f[/tex] suivante :
Si [tex]x \in E[/tex] alors [tex]x[/tex][tex]\longrightarrow[/tex][tex]y[/tex] où [tex]y[/tex] est le reste de la division euclidienne de [tex]ax+b[/tex] par 26, [tex]a[/tex] et [tex]b[/tex] entiers de [tex]E[/tex] et [tex]a \neq 0[/tex].[/quote]
[b][u]Exemple [/u][/b]: Pour coder la lettre P avec [tex]a = 2[/tex] et [tex]b = 3[/tex], on procède de la manière suivante :
- [b]étape 1[/b] : on lui associe l'entier n = 15.
- [b]étape 2[/b] : le reste de la division de [tex]2 \times 15 + 3 = 33[/tex] par 26 est 7.
- [b]étape 3[/b] : on associe 7 à H. Donc P est codé par la lettre H.
[quote]1) Que dire alors du code obtenu lorsque l'on prend [tex]a = 0[/tex] ?
2) a) Montrer que les lettres A et C sont codées par la même lettre lorsque l'on choisit [tex]a = 13[/tex]. En quoi est-ce un problème ?
b) Existe-t-il d'autres valeurs de [tex]a[/tex] pour lesquelles on a le même problème ?
3) Dans toute la suite de l'exercice, on prend [tex]a = 5[/tex] et [tex]b = 2[/tex].
a) On considère deux lettres de l'alphabet associées respectivement aux entiers [tex]n[/tex] et [tex]p[/tex].
Montrer, que si [tex]5n+2[/tex] et [tex]5p+2[/tex] ont le même reste dans la divison par 26, alors [tex]n-p[/tex] est un multiple de 26.
En déduire que [tex]n = p[/tex]. Que peut-on en conclure ?
b) Coder le mot NOEL.
4) On se propose de décoder la lettre [tex]E[/tex].
a) Montrer que décoder la lettre [tex]E[/tex] revient à déterminer l'élément [tex]n[/tex] de [tex]\Omega[/tex] tel que [tex]5n-26y=2[/tex], où [tex]y[/tex] est un entier.
b) Déterminer un couple [tex](n ; y)[/tex] solution de l'équation précédente avec [tex]0 \leq n \leq 25[/tex].
c) Décoder alors la lettre E.
5) Décoder le mot VUSWYN.[/quote][/quote]
Vous trouverez ci-dessous mes réponses, n'hésitez pas à me dire s'il y a quelque chose qui ne va pas : il s'agit d'un [b]travail noté[/b].
[quote]1) Si [tex]a=0[/tex], alors pour tout [tex]n[/tex], [tex]an+b=b[/tex]. Toutes les lettres de l'alphabet sont associées au même nombre donc elles seront codées par la même lettre correspondant au reste de la division de [tex]b[/tex] par 26.
2) a) A et C sont respectivement associées à [tex]b[/tex] et [tex]26+b[/tex], ils ont le même reste modulo 26. En effet :
[tex]A = 0[/tex] [tex]\longrightarrow[/tex] [tex]13\times0+b=b[/tex] [tex]\longrightarrow[/tex] [tex]\frac{b}{26}[/tex] [tex]\longrightarrow[/tex] [tex]r=b[/tex]
[tex]C = 2[/tex] [tex]\longrightarrow[/tex] [tex]13\times2+b=26+b[/tex] [tex]\longrightarrow[/tex] [tex]\frac{26+b}{26}[/tex] [tex]\longrightarrow[/tex] [tex]r=b[/tex]
A et C sont codées par la même lettre si [tex]a=13[/tex].
C'est un problème car on ne peut pas faire de distinction de codage entre les lettres A et C. Chaque lettre constituant le mot peut correspondre à plusieurs lettres.
b) Si on prend [tex]a=2[/tex], [tex]2x+b\equiv r(mod.26)[/tex] et que [tex]x=13[/tex] on a [tex]26+b\equiv r(mod.26)[/tex], comme [tex]26\equiv 0(mod.26)[/tex] alors [tex]26+b\equiv b(mod.26)[/tex] et donc [tex]r\equiv b(mod.26)[/tex].
Si [tex]x=0[/tex], on a [tex]2\times0+b\equiv r(mod.26)[/tex] soit aussi [tex]r\equiv b(mod.26)[/tex]. Donc, si [tex]a=2[/tex] on a aussi un problème.
3) a) [b][u]On a[/u][/b] :
[tex]5n+2\equiv 5p+2(mod.26)[/tex]
[tex]5n\equiv 5p(mod.26)[/tex]
[tex]n\equiv p(mod.26)[/tex] car 5 est premier avec 26
[tex]n-p\equiv 0(mod.26)[/tex]
Si [tex]5n+2[/tex] et [tex]5p+2[/tex] ont le même reste dans la division euclidienne par 26 alors [tex]n-p[/tex] est un multiple de 26.
[b][u]On a : [/u][/b]
[tex]0 \leq n \leq 25[/tex]
[tex]-25 \leq -p \leq 0[/tex]
Donc [tex]-25 \leq n-p \leq 25[/tex]
Or, le seul et unique multiple de 26 entre -25 et 25 est 0, donc [tex]n-p=0[/tex] soit [tex]n=p[/tex].
Si on prend [tex]a=5[/tex] et [tex]b=2[/tex], chaque lettre code une lettre distincte. De plus, si [tex]a \neq D(26)[/tex] alors chaque lettre code une lettre distincte.
b) [tex]N = 13[/tex] [tex]\longrightarrow[/tex] [tex]5\times13+2=67[/tex] [tex]\longrightarrow[/tex] [tex]\frac{67}{26}[/tex] [tex]\longrightarrow[/tex] [tex]r=15[/tex] [tex]\longrightarrow[/tex] [tex]15=P[/tex]
[tex]O = 14[/tex] [tex]\longrightarrow[/tex] [tex]5\times14+2=72[/tex] [tex]\longrightarrow[/tex] [tex]\frac{72}{26}[/tex] [tex]\longrightarrow[/tex] [tex]r=20[/tex] [tex]\longrightarrow[/tex] [tex]20=U[/tex]
[tex]E = 4[/tex] [tex]\longrightarrow[/tex] [tex]5\times4+2=22[/tex] [tex]\longrightarrow[/tex] [tex]\frac{22}{26}[/tex] [tex]\longrightarrow[/tex] [tex]r=22[/tex] [tex]\longrightarrow[/tex] [tex]22=W[/tex]
[tex]L = 11[/tex] [tex]\longrightarrow[/tex] [tex]5\times11+2=57[/tex] [tex]\longrightarrow[/tex] [tex]\frac{57}{26}[/tex] [tex]\longrightarrow[/tex] [tex]r=5[/tex] [tex]\longrightarrow[/tex] [tex]5=F[/tex]
Le mot NOEL, codé avec [tex]a=5[/tex] et [tex]b=2[/tex] nous donne PUWF.
4) a) E correspond à 4.
Ainsi, la lettre codée E correspond à un nombre [tex]n[/tex] tel que :
[tex]\Longleftrightarrow 5n+2\equiv 4(mod.26)[/tex]
[tex]\Longleftrightarrow 5n-2\equiv 0(mod.26)[/tex]
[tex]\Longleftrightarrow 5n-2 = 26y[/tex] où y est un entier relatif
[tex]\Longleftrightarrow 5n-2=26y[/tex]
[tex]\Longleftrightarrow 5n-26y=2[/tex]
b) A l'aide de la calculatrice, le couple [tex](16;3)[/tex] est solution de [tex]5n-26y=2[/tex] où y est un entier relatif et [tex]0 \leq n \leq 25[/tex].
c) D'après la question 4) b), la lettre dont le code est E est la lettre associée à 16 c'est-à-dire la lettre Q.
5) [tex]V=21 \longrightarrow 5n+2-26y=21 \longrightarrow (n;y)=(9;1) V\longrightarrow J[/tex]
[tex]U=20 \longrightarrow 5n+2-26y=20 \longrightarrow (n;y)=(14;2) V\longrightarrow O[/tex]
[tex]S=18 \longrightarrow 5n+2-26y=18 \longrightarrow (n;y)=(24;4) V\longrightarrow Y[/tex]
[tex]W=22 \longrightarrow 5n+2-26y=22 \longrightarrow (n;y)=(4;0) V\longrightarrow E[/tex]
[tex]Y=24 \longrightarrow 5n+2-26y=24 \longrightarrow (n;y)=(20;3) V\longrightarrow U[/tex]
[tex]N=13 \longrightarrow 5n+2-26y=13 \longrightarrow (n;y)=(23;4) V\longrightarrow X[/tex]
VUSWYN code pour le mot JOYEUX (quelle coïncidence).[/quote]
Bonne soirée à vous et merci de m'avoir lu, ce travail est très important pour moi.
Pierre.
