congruences

[Manon]

Bonjour je ne comprends pas cet exercice :

On crypte un message avec un chiffrement affine défini par yax+b[26] où a, b, x et y désignent des nombres entiers naturels compris entre 0 et 25. Déterminer les nombres entiers c et d tels que x=cy+d(26) pour a=3 et b=6. (le = étant ici un congru)

merci d em'aider je ne comprends pas !

[SoS-Math(4)]

Bonjour,

Donc on a : y=3x+6 ( modulo 26) soit y-6=3x ( modulo 26)

On ne peut diviser les 2 membres d'une congruence par 3, mais on va multiplier les 2 cotés par un entier k, tel 3k=1 ( modulo 26)

En faisant plusieurs essais il faut trouvez cet entier k.

sosmaths

[Manon]

3k=1(26) donc je résous :

3k-26y=1 donc :

théorème d'euclide :
26 3 2
3 2 1
2 1 0

d'où:

1=3-2 or 2=26-3*8
1=3-(26-3*8) donc 1=3*9-26*1

donc les couples de la forme : (26k+9;3k+1) marchent soit k=?

je n'arrive pas à finir

[SoS-Math(4)]

Dans ta solution, comme l'inconnue est k, tu peux pas utiliser k, mais k' par exemple;

solution S={(26k'+9;3k'+1), k' entier relatif}

donc k=26k'+9 en faisant k'=0 tu obtiens k=9

Effectivement , 3*9=1 (modulo 26)

Donc tu multiplies par 9, les 2 côtés de la congruence : y-6=3x (modulo 26)

sosmaths

[Manon]

donc la réponse est 3?

[SoS-Math(4)]

la réponse à quoi ?
il faut finir l'exercice.
sosmaths

[Manon]

en fait je ne comprends pas ce qu'il faut faire pour la suite

je connais les solutions et je dois en déduire k non ?

[SoS-Math(4)]

Donc tu multiplies par 9, les 2 côtés de la congruence : y-6=3x (modulo 26) ( conseil d'un message précédent)

On obtient : 9(y-6)=9*3x ( modulo 26)


soit : 9y-54= 27x ( modulo 26)

or 54=2( modulo 26) et 27=1 (modulo 26)

donc on obtient : 9y-2=x (modulo 26)

or -2= 24( modulo 26)

donc 9y+24=x( modulo 26)

Et voilà !
sosmaths

[Manon]

d'accord merci !

mais alors e dois trouver combien pour x ? je remplace y par quoi ?

[SoS-Math(4)]

x c'est le numéro de la lettre que tu veux coder(A=0;B=1...;Z=25) et y c'est le numéro de la lettre codée.

Fais quelques essais avec des valeurs de x pour trouver y ( codage) ou pour trouver x connaissant y ( décodage).

sosmaths