[RÉSOLU][Spé] DM Arithmétique pour Lundi - Cryptage - Le Cod

[Hick_Jeck]

Bonjour à tous,
Voici la première partie de mon DM de spé maths à rendre pour lundi que j'ai commencé à traiter, mais je bloque à une question. On verra plus tard pour la partie B. J'ai notamment besoin de votre aide pour la rédaction qui me parait limite.


1. Ici, la rédaction ici me paraît TRÈS problématique puisque je passe d'une congruence à une égalité :/ .
Y:
y = 24
y = ax + b

0;)5<26 d'où x = 5 correspond à F dans le tableau.

X:
y = 23

0;)4<26 d'où x = 4 correspond à E dans le tableau.

K:
y = 10

0;)17<26 d'où x = 17 correspond à R dans le tableau.

...

M:
y = 12

0;)19<26 d'où x = 19 correspond à T dans le tableau.

Je préciserais dans ma copie qu'une lecture du tableau aurait permis de répondre directement à la question en décalant 19 fois vers la gauche, et lorsqu'un arrive à A, on repart Z. Est-ce correct au niveau de la rédaction ?

2a. H:
x = 7
y = ax + b
y = 7*7 + 17
y = 66
c(y) = 14 car 66 = 26 * 2 + 14
14 correspond à O dans le tableau.

etc...

2b.

Or
D'où


Donc y et y' ont le même reste dans la division euclidienne par 26, d'où c(y) = c(y'). Donc les codes obtenus avec les clés (a;b) et (a';b') sont identiques.

Au passage, j'ai un petit doute sur l'utilisation de c(y). c est bien une fonction qui à x associe son reste modulo 26 hein ?

2c. Là, je bloque. J'aurais besoin de votre aide . Il faut probablement se servir de la question précédente, vu qu'on a pas fait de statistique encore. Merci d'avance si vous pouvez m'aiguiller.

Merci .
Hick_Jeck

[Hick_Jeck]

Petit up SVP. C'est relativement urgent puisque c'est pour Lundi, et ça m'énerve de bloquer sur une seule question jusqu'à maintenant :cry: .

Amicalement,
Hick_Jeck

[Ben314]

Pour le 1), c'est parfaitement correct et la remarque de la fin est trés bien.
En ce qui concerne le passage "congruence -> égalité", cela provient simplament du fait que, si a et b sont congrus modulo 26 et qu'il sont tout les deux entre 0 et 25 alors ils sont égaux (car a-b est entre -25 et 25 et, comme c'est un multiple de 26, ce ne peut être que 0)

2)a) O.K.

2)b) Principe : O.K., mais la rédaction à la fin ne vas pas :l'énoncé te dit que c(x) est le reste de la division de ax+b par 26 (et pas de x par 26).
Donc ici, tu as deux "codes différents" et il faut leur donner des noms différents, par exemple :
c(x) est le reste de la division de ax+b par 26
c'(x) est le reste de la division de a'x+b' par 26
et ce que tu as montré, c'est que c(x)=c'(x) [le même x, mais, à priori, pas la même fonction de "codage"]

2)c) C'est vrai que si tu avais fait un peu de dénombrement, ce serait plus façile, mais avec juste un peu de bon sens, on peu trouver.
On te demande de compter les codes différents, c'est à dire le nombre de couples (a,b) avec a et b dans les intervalles demandés.
Imagine que tu les écrit tous (ne le fait pas, c'est trés long...) :
(1,0) , (1,1) , (1,2) , ... , (1,25)
(2,0) , (2,1) , (2,2) , ... , (2,25)
(3,0) , (3,1) , (3,2) , ... , (3,25)
.
.
.
(24,0),(24,1),(24,2), ... ,(24,25)
Tu n'as pas une petite idée du nombre qu'il y en a ?

[Hick_Jeck]

Merci de ta réponse complète et rapide .
Si j'ai bien compris, il y en a 24*26 = 624 .

Edit : D'après ton schéma, a 25. Or il peut être égal à 25. Donc c'est plus
25*26 = 650.
La rédaction par un tableau me parait par contre limite, surtout connaissant ma prof.

2d.
Voir brouillon sur la feuille :p .
Le problème qui apparaît dans le codage est le fait que deux lettres différentes soient associés à la même lettre codée, posant ainsi des problèmes sur le décodage.

Voici la deuxième partie de mon DM qui s'annonce plus corsée pour moi j'ai l'impression.


1a.
on pose a = 26 et b = 7
26 = 3*7+5 donc 5 = a-3b
7 = 1*5+2 donc 2 = 4b-a
5 = 2*2+1 donc 1 = 3a-11b
2 = 2*1+0

D'où 7*(-11) + 26*3 = 1
7*(-11) - 26*(-3) = 1

(u;v) = (-11;-3) est une solution de l'équation 7u-26v = 1

De plus, 7u = 7*(-11) = -77
Donc 7u = -77 = -3*26 + 1
Donc

1b. Il faut remonter les étapes ? Une petite aide ?

[Ben314]

Pour le 2)c), tu as raison, j'ai oublié la dernière ligne.
Si tu préfère, tu peut dire qu'il y a d'abord 25 choix possibles pour 'a' puis, pour chaque 'a' il y a 26 choix possible pour 'b' ce qui fait 25x26 choix possibles au total.
Perso, même avec des poiltillés, le tableau explique bien pourquoi on fait le produit de 25 et de 26 (25 lignes et 26 colonnes = 25x26 cases)

Pour la deuxième partie,
1a. O.K. sauf que, (à part pour vérifier), c'est pas la peine de calculer 7u=-77. Tu sait déja que 7u=1+26v.

Le 1b. revient à résoudre une équation. Comme la lettre 'aprés codage' est b, cela signifie que l'on sait que y=1. On cherche la lettre de départ, c'est à dire le (ou les) x tels que ax+b=y modulo 26.
Ici, cela signifie 7x+17=1 modulo 26.
Pour résoudre cette équation, on fait un peu comme dans R. On commence par 'faire passer' le 17 de l'autre coté en retranchant 17 des deux cotés.
Si on était dans R, pour 'faire passer' le 7 (de 7x) de l'autre coté, on diviserait les deux cotés par 7, sauf que (pour le moment) tu ne sait pas faire de division modulo 26...
MAIS, diviser par 7 (dans R) cela veut dire multiplier par 1/7 c'est a dire par un nombre dont le produit avec 7 fait 1.
Qui donc peut replacer ce "1/7" de R ? Il faudrait un nombre dont le produit avec 7 (modulo 26) fasse 1... BINGO : il faut multiplier des deux cotés par -11 et, à gauche, on aura (-11)*7x=(-11*7)*x=1*x=x donc en fait on aura une formule de la forme x=??? que sera bien sûr la solution du problème.

[Hick_Jeck]

D'accord . Voici comment je rédigerais les choses :

1b.
On a y = 1 (d'après le tableau de l'énoncé)
Trouver x le code initial de la lettre recherchée revient à résoudre une équation du type :


D'où
Or
Donc


Est-ce suffisant ? Je pense surtout aux deux dernières lignes.

1c.

Or 0;)x;)25, donc x=20. 20 correspond à la lettre U d'après le tableau.

2. Bon, là, j'ai encore une fois besoin de votre aide.

3.
Trouvons deux entiers u et v tels que 5u-26v = 1 grâce à une division euclidienne.
26 = 5*5 + 1 donc 1 = 26 - 5*5
5*(-5) + (-1)*26 = 1

Donc (u;v) = (-5;-1) est une solution.



De plus,


Or
D'où


S :
0;)1;)25, donc x = 1, correspond à B

U :
0;)17;)25, donc x = 17, correspond à R

N :
0;)0;)25, donc x = 0, correspond à A

O :
0;)21;)25, donc x = 21, correspond à V

F :
0;)14;)25, donc x = 14, correspond à O

Le mot BRAVO était donc recherché.

Voilà. Donc j'ai besoin de votre aide pour la B.2, et aussi j'ai une question : à quoi sert la question A.2b ?

En vous remerciant,
Hick_Jeck

[Ben314]

1.b. et 1.c : Impec. (la rédaction me parrait parfaite)

Pour le 2), tu essaye de voir le "pourquoi" on a réussi à résoudre l'équation ax+b=y modulo 26 (avec a,b,y connu et x inconnu).
Si tu regarde la méthode employé, on a du multiplier par un "u" tel que au=1 modulo 26. Donc la méthode marche tout le temps à condition qu'un tel u existe.
Or "au=1 modulo 26" signifie au=1+26v pour un certain v c'est à dire
au-26v=1. Tu doit savoir que cette équation (avec a connu, u,v inconnues) a des solutions si et seulement si a et 26 sont premiers entre eux.

Pour le début du 3), à mon avis, tu écrit trop de trucs bébéte sur les congruences modulo 26. Je pense qu'il est suffisant d'écrire :
au=1+26v donc au=1 modulo 26
La suite me semble "impec".


Pour moi, la question A.2.b, elle sert à expliquer que cela ne sert à rien de prendre des codes avec a=3247 et b=1845 puisque ça donnera la même chose qu'avec a=23 (reste de la division de 3247 par 26) et b=25 (reste de la division de 1845 par 26).
En particulier elle explique pourquoi dans la question suivante, quand on cherche le nombre de codes différents, on prend a et b entre 0 et 25.
On ne prend pas a=0 car sinon y=ax+b serait égal à b à tout les coups et toutes les lettres donnerait le même code, ce qui est complètement con.
En fait, la question B.2 montre que, si on ne veut pas avoir de problème lors du décodage, il faut prendre a premier avec 26.
Si on ne prend pas a premier avec 26, l'exemple de la question A.2.d (ou a=2 n'est pas premier avec 26) montre que des lettres différentes risquent d'avoir le même code, ce qui évidement pose problème au moment du décodage !!!

[Hick_Jeck]

Oui, ok :) . Merci beaucoup pour ton aide, ça m'a vraiment été utile pour résoudre mon DM de manière concise et rigoureuse :D .

Merci enfin pour ton génie, ou du moins, le temps que tu passes à aider des élèves,
Mathématiquement,
Hick_Jeck