Inscription / Connexion Nouveau Sujet
problème de cryptographie, codage par transformation affine
Bonjour,
Ce serait gentil si vous pouviez m'aider pour résoudre ce problème :
On affecte à chaque lettre de l'alphabet un entier compris entre 0 et 25. On note E l'ensemble de ces entiers.ex : a=0, b=1...
On définit un système de codage à l'aide de la transformation f:si x appartient à E, alors x
y, où y est le reste de la division euclidienne de ax+b par 26, avec a et b entiers de E, a non nul.
a. On suppose pgcd(a,26)=1. Montrer que si f(x)=f(x'), alors x=x'. Jusque là ça va plutôt bien.
b. On suppose pgcd(a,26)=d et d différent de 1. Montrer qu'il existe alors des lettres codées de la même façon. Là j'y arrive pas du tout.
c. En déduire les couples (a,b)qui définissent un "bon" codage. Combien y a-t-il de couples? Combien y a-t-il de codages affines distincts?(ça veut dire quoi "codage affine"?) On suppose dans la suite que a est premier avec 26.
d. Montrer qu'il existe un entier a' de E tel que aa'
1(26).
e. en déduire une "formule" de décodage, c'est à dire une expression de x en fonction de y, a,b et a'si on a y=f(x).
Merci pour votre aide.
Bonjour
b. Quand tu cherches à résoudre f(x) = f(x')
tu as successivement
ax + b = ax' + b
a(x - x')= 0 modulo 26
si maintenant d est le pgcd de a et de 26
alors il existe a' et m tels que
dm = 26 et da' = a
et si tu prends x - x' = m que se passe-t-il pour a(x - x')?
c. le codage affine c'est justement le codage que l'on t'a décrit
à une lettre L on associe un nombre x
au nombre x, on associe le nombre y = ax + b (modulo 26) (transformation affine)
au nombre y on associe une nouvelle lettre L'
Tu as vu à la question a. et b. que le codage ne permet un décodage que si a et 26 sont premiers entre eux
Il y a autant de codage différents que de couples (a,b) d'élements de E avec a premier avec 26.
d. Il faut utiliser l'identité de Bézout: a est premier avec 26 ssi il existe deux entiers relatifs x et y tels que ax + 26y = 1. Cela signifie que ax = 1 (modulo 26)
En prenant pour a' le reste de la division de x par 26, on a gagné.
e. décoder c'est trouver x connaisant y tel que y = ax + b (modulo 26), donc c'est résoudre l'équation ax + b = y d'inconnue x
ajouter -b ne pose pas de pb...
diviser par a n'est pas possible.... mais on peut multiplier les deux membres de la congruence par a' (car aa' = 1 modulo 26) et ainsi on a isolé x.
Bon courage
Annuler
connectez vous