Congruences et code ASCII

[sow97]

Salut les matheux !

J'ai un DM de spé Maths qui porte sur les congruences et je bloque sur une question. Voici l'énoncé :

En informatique, le code ASCII associe à chaque caractère (lettre, chiffre, signe de ponctuation...) un entier compris entre 0 et 255 que l'on appelle son code ASCII. La fonction code du tableur renvoie le code ASCII du caractère. L'extrait de tableur ci-dessous donne le codage des caractères M a t h.

....A...B....C....D
1..M...a....t.....h
2..77..97..116..104

On décide ainsi de crypter le code ASCII par la fonction de cryptage f définie ainsi : pour tout entier n tel que 0 ;) n ;) 255, f(n) est le reste de la division euclidienne de 7n par 256.

1) Vérifier que le codage du mot "Math" devient : 27-167-44-216
2) Soient n et m deux entiers compris entre 1 et 255.
a) Montrer que si f(n) = f(m) alors 7(n-m) ;) 0[256].
b) En déduire que deux caractères différents sont codés par deux entiers différents.

C'est sur cette dernière question (2b) que je bloque... Je n'arrive pas à faire le lien entre mes résultats précédents et cette affirmation.
Avez-vous des pistes ?

[Ben314]

Salut,
A la question 2)a) tu as montré que, si f(m)=f(n) (i.e. si les caractères m et n ont le même code) alors 7(n-m) ;) 0[256] et pour répondre à la b), il faudrait en déduire que n=m (i.e. que c'était deux fois le même caractère !)

Pour ce faire, il suffit de se rappeler de la définition d'une congruence : dire que 7(n-m) ;) 0[256], ça veut dire que 256 divise 7(n-m).
Sauf que pgcd(7,256)=... donc ...


Après, je sais pas si tu as une suite au D.M., mais évidement, la question intéressante, c'est évidement "comment faire pour décrypter ce code", c'est à dire comment retrouver la valeur de n [256] lorsque l'on connait seulement la valeur de m=7n [256] ?

[sow97]

Si je pars sur ton conseil :
256 divise 7(n-m), or PGCD(7;256)=1 donc 7 et 256 sont premiers entre eux
donc 256 divise n-m
donc n-m ;) 0[256]
donc n ;) m[256]

Ca à l'air simple pourtant mais je ne parviens pas à trouver n=m... Je reconnais que je ne suis pas vraiment à l'aise avec les congruences :(

[Ben314]

En fait, une fois que tu as ça :

...donc n m[256]

au fond, c'est fini (d'ailleurs, j'avais même pas pensé qu'il fallait dire un truc en plus après...)

Tes nombres n et m, c'est des codes ASCII : ils sont entre 0 et 255 donc s'il sont congrus modulo 256, ça veut dire qu'il ont même reste de division par 256 et donc tout simplement qu'ils sont égaux...

Sinon, concernant les congruences, il y a deux "points de vue" et c'est des fois l'un, des fois l'autre le plus malin :

Dire que a b [c], ça signifie que : l'entier c divise b-a et aussi que a et b ont même reste de division euclidienne par c.

C'est facile de vérifier que les deux disent exactement la même chose, mais dans les exos, c'est soit l'un, soit l'autre qu'on utilise...

[sow97]

En effet, j'avais oublié de prendre en compte les encadrements ! Quand on a toutes les données en tête c'est vrai que ça marche mieux :) Merci beaucoup !

[sow97]

Voilà la suite du DM :
3)a) Justifier l'existence d'un couple d'entiers relatifs (u;v) tel que 256u+7v=1.
b) Vérifier que (-5;183) est un tel couple.
c) En déduire que 183xf(n) ;) n[256].
Et là, ça coince... Je ne vois pas par où commencer... Un point de départ svp ?

[Ben314]

Pour le a), c'est du cours (et c'est un peu long à redémonter...) : deux entiers a et b sont premiers entre eux si et seulement si il existe deux entiers u et v tels que au+bv=1 (théorème dit "de Bézout" : indispensable en arithmétique)

Le b), c'est un simple calcul.

Le c)... aussi vu que, modulo 256, f(n), c'est simplement 7n. donc il faut calculer 183*7n modulo 256

[sow97]

Les deux dernières questions :
d) Définir alors une fonction de décryptage g.
e) Vérifier que g(27)=77.

Qu'est-ce qu'une fonction de décryptage ? Une fonction g(n) qui, lorsqu'on a n, donne le codage du caractère ? Sans passer par le reste de la division de 7n par 256 ?

[Ben314]

Qu'est-ce qu'une fonction de décryptage ? Une fonction g(n) qui, lorsqu'on a n, donne le codage du caractère ? Sans passer par le reste de la division de 7n par 256 ?

Ben... non, comme son nom l'indique, une fonction de DÉcryptage, ça sert à... décrypter, c'est à dire à retrouver la valeur de n lorsque l'on connait uniquement la valeur de f(n).

Içi, la fonction de cryptage, c'est :

Donc la fonction de décryptage g, c'est celle qui donne g(0)=0 ; g(7)=1 ; g(14)=2 ; ... ; g(195)=101 ; g(249)=255.

Enfin bref, celle qui décrypte...

[sow97]

Je ne parviens pas a la trouver...
Je suis arrivée a g(n)=183f(n)-256k, que faire apres ?