Congruences, code de césar

[Elina]

Bonjour,

J'aurais besoin d'aide pour cet énoncé qui me pose énormément problème. J'ai déjà un peu avancé mais il reste énormément de points où ce n'est pas très clair.

Voici l'énoncé :
On numérote les lettres de l'alphabet de 0 à 25 tel que :
A=0
B=1
C=2
etc.

Une fonction f associe à chaque nombre x le reste de la division euclidienne de ax+b par 26
On remplace les lettres initiales par celles qui correspondent aux numéros donnés par les restes.
Le couple (a;b) est la clé du codage.

1. On suppose que a et 26 sont premiers entre eux

a) On considère deux valeurs x et x' telles que f(x) = f(x'). Montrer à l'aide du théorème de Gauss que x=x'

On sait que ax+b=ax'+b. De plus, ce sont des multiples de 26.
Ainsi,
(ax+b)-(ax'+b)=0
ax+b-ax'-b=0
ax-ax'=0
a(x-x')=0
26 et a sont premiers entre eux donc 26/a(x-x')

pgcd (a;26) = 1 donc par le théorème de Gauss : 26/(x-x')

x e [0;25] et x' e [0;25]
alors 0<x<25 et -25<-x'<0 donc -25<x-x'<25
de plus, 26/x-x'
Il existe qu'un seul multiple de 26 dans [-25;25] qui est 0
Ainsi, quand f(x)=f(x'), x=x'

b) La clé (a;b) est satisfaisante si deux lettres sont codées par deux lettres également différentes. En déduire que la clé est satisfaisante dans le cas où a et 26 sont premiers entre eux.

On suppose que pgcd(a;26)=1. Ainsi, comme ax+b n'est pas égal à ax'+b (car x ne vaut pas la même valeur que x', étant associés à deux lettres différentes) on sait grâce à la question a) que x=x' <=> f(x)=f(x')
Ainsi, dans le cas où les lettres sont différentes elles ne seront pas codées de la même manière. La clé est donc satisfaisante.

Dans la suite, on considère que a et 26 sont premiers entre eux.

2. A l'aide du théorème de Bézout, montrer qu'il existe un entier u tel que : au est congru à 1 mod [26]

3. Montrer que, si y est congru à ax+b modulo 26 alors x est congru à uy-bu modulo 26
En déduire une fontion affine permettant de lire un message codé.

4. Déterminer une fonction de déchiffrement associée à la clé (11;8), puis lire le message "IFA EAYIN"

Je bloque vraiment sur cet exercice, si vous pouviez m'aider ce serait vraiment sympa !

Merci d'avance

[sos-math(21)]

Bonjour,
tes premières réponses sont globalement correctes, il faut encore soigner la rédaction qui peut encore gagner en rigueur.
Pour la suite si \(a\) est premier avec 26, cela signifie que leur PGCD est égal à 1, donc d'après le théorème de Bézout, il existe deux entiers \(u\) et \(v\), tels que \(au+26v=1\), soit en prenant les congruences, \(au\equiv 1\,[26]\).
Si on \(y\equiv ax+b\,[26]\), alors en passant le \(b\) de l'autre côté, on a \(ax\equiv y-b\,[26]\), puis en multipliant par \(u\) des deux côtés, on a \(aux=u(y-b)\,[26]\).
Or \(au\equiv 1\,[26]\), donc on a \(x\equiv u(y-b)\,[26]\). On vient donc de trouver une fonction réciproque à la fonction de chiffrement \(f\).
Il faut donc trouver une valeur pour \(u\).
Je te laisse poursuivre

[Derta]

Bonjour,
tes premières réponses sont globalement correctes, il faut encore soigner la rédaction qui peut encore gagner en rigueur.
Pour la suite si \(a\) est premier avec 26, cela signifie que leur PGCD est égal à 1, donc d'après le théorème de Bézout, il existe deux entiers \(u\) et \(v\), tels que \(au+26v=1\), soit en prenant les congruences, \(au\equiv 1\,[26]\).
Si on \(y\equiv ax+b\,[26]\), alors en passant le \(b\) de l'autre côté, on a \(ax\equiv y-b\,[26]\), puis en multipliant par \(u\) des deux côtés, on a \(aux=u(y-b)\,[26]\).
Or \(au\equiv 1\,[26]\), donc on a \(x\equiv u(y-b)\,[26]\). On vient donc de trouver une fonction réciproque à la fonction de chiffrement \(f\).
Il faut donc trouver une valeur pour \(u\).
Je te laisse poursuivre

Quelle est la réponse à la question :
x=x' en utilisant le théorème de Gauss ?

[sos-math(21)]

Bonjour,
pour la question :

On considère deux valeurs x et x' telles que f(x) = f(x'). Montrer à l'aide du théorème de Gauss que x=x'

Si on a deux nombres \(x\) et \(x'\) tels que \(f(x)=f(x')\), alors on a \(ax+b\equiv ax'+b\,[26]\)
On peut éliminer les \(b\) dans chaque membre de l'équivalence et tout passer dans le membre de gauche de sorte à avoir :
\(ax-ax'\equiv 0\,[26]\) soit \(a(x-x')\equiv 0\,[26]\).
On a donc \(26|a(x-x')\). Or \(26\) et \(a\) sont premiers entre eux donc d'après le théorème de Gauss, on a donc \(26|x-x'\).
Si on a imposé \(x\in[0\,;\,25]\), et \(x'\in[0\,;\,25]\), alors on a |x-x'|<26 et la divisibilité de \(x-x'\) par \(26\) impose donc \(x-x'=0\) et \(x=x'\).
Bonne continuation