Bonjour,
Voici un exercice qui me fait bloquer,je ne sais si c'est moi ou mon professeur qui fait souvent des fautes dans les énoncés. De plus je n'ai jamais étudier le théorème de Bezout et algorithme d'Euclide étendu,je les ai découverts seule; voilà 2 jours que je cherche. Je mets ce sujet en terminal car j'ai cru comprendre que c'était de votre niveau

1-Dans le cas d'un codage affine de clé (7,17) on cherche une lettre dont le codage finale est B
a- à l'aide de l'algorithme d4euclide, trouvez deux nombres u et v tels que 7u-26v=1
justifier que 7u=1(mod26)à l'aide du théorème de Bezout.  (J'ai trouvé u=-11 et v=-3 et j'ai justifié la formule)
b- soit x le code intitial de la lettre cherchée
démontrer que x vérifie (E): 7x=-16 (mod 26).   (ça c'est OK avec 7x+17=1 puisque la lettre décodée est B
(à partir de là je bloque)... En déduire que x=-16(mod26)
c-en déduire l'entier x compris entre 0 et 25 solution de (E),puis la lettre cherchée.

2 Expliquer pourquoi la méthode ci-dessus assure le décodage de n'importe quelle lettre dès qu'on choisit une clé (a;b) telle que a soit premier avec 26.
merci à vous pour votre aide

*** message déplacé ***
_{* Océane > le multi-post n'est pas toléré sur le forum ! *}

en fait j'ai pu voir un exercice similaire sur le site,je suppose donc que mon professeur c'est une nouvelle fois trompé (grrr) et qu'il voulait dire x=-16u(mod26) et non x=-16(mod26)
https://www.ilemaths.net/sujet-cryptographie-affine-25086.html
Désolé de le voir maintenant alors que je post,pourtant cela fait 2 journées complètes que je cherche,je me doutais qu'il y avait une erreur.

donc je vais faire moi-même la démonstration
on sait que 7x=-16 (mod26)
et 7u=1 (mod26)
7=1/u (mod26)
x=-16/7 (mod26)
x=-16/(1/u) (mod26)
x=-16u (mod26)

par contre je n'arrive pas à faire la suite

avec x=-16u(mod 26)
si je fais l'algorithme étendu d'euclide cela fait x=3 (http://www.apprendre-en-ligne.net/crypto/rabin/euclide.html) alors que x devrait être égal à 20

Veni, Vidi, Vici » en utilisant le chiffre de C'est César est : « YHQL YLGL YLFL »
b) La phrase qui a pour code « DOHD MDFWD HVW » est : Alea Jacta Est

2. Cryptographie affine :

A. Codage affine :

- 1. Le mathématicien qui se cache derrière yxketm est Fermat. (erreur dans l'énoncer)
- 2. a) Mon prénom, Melody, codé avec la clé (7 ; 17) est : xtqlmd.
    b) tableau excel
    c) -Lorsque a = 0, chaque lettre codée sera identique.
        -Lorsque a = 13, puisque 13 est un multiple de 26, le reste c(x) sera toujours égal à 0, donc chaque lettre codée sera toujours A.
    d) tableau excel
On constate dans ce tableau que plusieurs mots initiaux différents sont codées par le même mot, cette fonction n'est donc pas une bonne fonction de codage.
Afin que les lettres ne soient pas codées par la même lettre et que la fonction soit efficace, il faut que a et 26 soient premiers entre eux, donc que leur PGCD est 1.
    e) En mathématiques, on dit que des entiers sont premiers entre eux, lorsque ces nombres n'ont aucun diviseur autre que 1 et -1 en commun.
    f) Les nombres entiers de l'intervalle [0 ;25] premiers avec 26 sont  1; 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25
    g) Le nombre de clés utilisables pour coder un texte est 26 x12=312 (car il y a 12 nombres premiers avec 26).

B. Décodage :

- 1. a) On a la clé (7 ; 17) et on veut trouver un u et un v  qui vérifie l'expression 7u - 26v = 1.
D'après l'algorithme d'Euclide on a :
26 = 7 x 3 + 5
7 = 5 x 1 + 2
5 = 2 x 2 + 1
2 = 2 x 1
Soit le PGCD (7 ; 26) est 1.
Deux ce fait ont sait que 7u - 26v = 1 est une équation de type :  au + bv = PGCD (a ; b) = d
On a :
26 = 7 x 3 + 5 soit 5 = 26 - 3 x 7
7 = 5 x 1 + 2 soit 2 = 7 - 1 x 5
5 = 2 x 2 + 1 soit 1 = 5 - 2 x 2
2 = 2 x 1+ 0
Donc on a :
1 = (7 - 1 x (26 - 3 x 7 )) - 1 x (( 26 - 3 x 7 ) - 2 x ( 7 - 1 x ( 26 - 3 x 7 )))
1 = -11 x 7 - (-3) x 26
On a donc u = -11 et v = -3
1=7(-11)-26(-3)
On a  u = -11 or le reste de la division euclidienne de 7u (= 7 x (-11) = -77) par 26 est 1. On écrit cette expression : 7u = 1 (mod 26).

b) Pour la lettre dont le codage final est B, nous avons l'égalité y = 1 (mod 26) et on a la clé (7 ; 17) soit y = 7 x +17 donc on a :
7 x +17 = 1 (mod 26)
7 x = 1 - 17 (mod 26)
7 x = - 16 (mod 26) : E

Nous savons que 7 x =-16(mod26)
Et d'autre part 7u=1(mod26)
7=1 /u (mod26)
donc x =- 16 /7 (mod26)
x =-16 / (1 /u) (mod26)
x =-16u (mod26)   (erreur dans l'énoncé)
Qui n'est en fait que x = (1-17)u (mod26) c'est-à-dire x =(y-b)u (mod26)

c) sachant que dans ce cas y=1 a=7 et b=17 et u=-11
x = -16(-11) (mod26)
x =176 (mod26) Or 176 n'appartient pas à [0 ; 25]
x = 156+20 (mod26)
x = 6x26+20 (mod26)
x =20 (mod26)
donc x correspond à 20 qui est la lettre U


- -2. La méthode de décodage f(x) =(y-b)u (mod26).est valable pour tous x premier avec 26 appartenant à l'intervalle [0 ; +∞] lorsque la clé est (a,b)  car il s'agit d'une fonction affine
- qui correspond à f(x)=a x +b sachant que a et b sont des constantes et x est la variable.


- 3. En utilisant la méthode indiquée dans la partie B, avec la clef (5 , 13)
au+26v=1
a=5
5u+26v=1
on trouve u=-5 et v=1
avec la formule   x=(y-b)u (mod26)

y=5 x +13 (mod26) soit 5 x =y-13 (mod26)
En prenant u=-5 on a x = (y-13) u(mod26)=(y-13) (-5) (mod26)

•La lettre S correspond à y=18
x = (y-13) (-5) (mod26)
donc on a x = (18-13)(-5) (mod26)=-25(mod26)=1(mod26)
Et 1 correspond à la lettre B

•La lettre U correspond à y=20
x = (y-13) (-5) (mod26)
donc on a  x=(20-13)(-5) (mod26)=-35(mod26)=-11(mod26) Or -11 n'appartient pas à [0 ; 25]
                                                         = -35+26 (mod26) =17 (mod26)
et 17 qui correspond à la lettre R.


•La lettre N correspond à y=13
x = (y-13) (-5) (mod26)
En prenant u=-5 on a x = (13-13)(-5)(mod26)=0 (mod26)
Et 0 correspond à la lettre A.

•La lettre O correspond à y=14.
x = (y-13) (-5) (mod26)
En prenant u=-5 on a  x =(14-13)(-5) (mod26)=-5(mod26) Or -5 n'appartient pas à [0 ; 25]
                                                                              = -5+1x26 (mod26)=21(mod26)
et 21 correspond à la lettre V.

•La lettre F correspond à y=5
x = (y-13) (-5) (mod26)
En prenant u=-5 on a  x =(5-13)(-5) (mod26) = 40(mod26) Or 40 n'appartient pas à [0 ; 25]
                                                       = 40-1x26(mod26)= 14(mod26)
ce qui correspond à la lettre 0.

Le mot qui se cache derrière SUNOF ave la clé (5 ; 13) est BRAVO !!