Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale Calcul matricielTopics traitant de calcul matriciel [tout]Lister tous les topics de mathématiques
Niveau terminale
Partager :

Déchiffrement de Hill

Posté par
kikou36 19-05-13 à 22:28

On travaille avec la clé (7:3:5:8) tels que a=7 b=3 c=5 d=8
1. Déterminer la matrice A telle que
ax+by(congru) x'[26] et
cx+dy(congru) y'[26]
soit équivalent à A(x)=(x')
                              (y) (y')
2. Monter que A est inversible et déterminer sa matrice inverse que l'on écrira sous la forme (1/41)*B ,où B est une matrice à coefficients entiers.
3. Monter qu'il existe un unique entier m compris entre 0 et 25 tel que 41m(congru)1[26].
4. Montrer que mB(x')=(x)
                             (y') (y)
On dit que mB est la matrice de décodage, et on admettra que cette matrice est unique.
-------------------------------------------
1) je trouve A=(a b)=(7 3)
                       (c d) (5 8)

2) je trouve B=(8 -3)
                      (-5 7)
3) Je pose 41m-26k=1 et avec le theoreme de Gauss je trouve m=26K+7 donc l'unique m entre 0 et 25 est 7
4) je fais la multiplication de matrice et je trouve :
m*B*(x')=(56x'-21y' )
       (y') (-35x'+49y')

Comment retomber sur (x) ?
                                     (y)


Désolé pour la mise en des matrices mais je ne pense pas qu'on puisse faire autrement ?
Merci d'avance pour votre aide.

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 22:44

M= \begin{pmatrix} \\ a&b \\ \\ c&d \\ \end{pmatrix}



\begin{pmatrix} \\ x' \\ \\ y' \\ \end{pmatrix}=M\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}

est-ce bien cela?

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 22:44

A=M

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 22:46

Oui c'est ça. Comment fais tu pour afficher les matrices de cette façon ?

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 22:52


Citation :
Oui c'est ça. Comment fais tu pour afficher les matrices de cette façon ?


Regarde ici:
http://www.commentcamarche.net/contents/624-latex-expressions-mathematiques

pour activer du latex il faut encadrer la formule en latex avec des balises
(clique sur le bouton LTX en bas)

1) et 2) sont corrects je pense.

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 22:55

La 3) est correct aussi je pense.
Pour la 4) mon calcul ne doit pas être faut mais je pense que le travaille n'est pas terminé pour aboutir à la question mais je ne sais pas comment faire.

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 22:56

la réponse pour 3) est correcte mais l'explication n'est pas complète il faut résoudre l'équation correctement.

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 22:58

Oui j'ai toute une démonstration sur mon brouillon je ne l'ai pas rédiger sur le post.
Et merci pour le lien vers le tuto.

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:05

mB\begin{pmatrix} \\ x' \\ \\ y' \\ \end{pmatrix}=mBA\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}

7B\begin{pmatrix} \\ x' \\ \\ y' \\ \end{pmatrix}=7\begin{pmatrix} \\ 41&0 \\ \\ 0&41 \\ \end{pmatrix}\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}=\begin{pmatrix} \\ 7\times 41&0 \\ \\ 0&7\times 41 \\ \end{pmatrix}\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}



PS:
Pour faire des matrices tu fais un copier-coller sur les formules que j'ai déjà écrites et tu n'oublies pas de les encadrer avec la balise latex.
faire aperçu avant de poster définitivement

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:09

Citation :
4. Montrer que mB(x')=(x)
                             (y') (y)


est faux.

Par contre, l'égalité est vraie modulo 26

car:
\\ \begin{pmatrix} \\ 7\times 41&0 \\ \\ 0&7\times 41 \\ \end{pmatrix}\equiv \begin{pmatrix} \\ 1&0 \\ \\ 0&1\\ \end{pmatrix} \mod{26}

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 23:19

Ducoup on obtient la matrice



\\ $ \begin{pmatrix} \\ 287x \\ \\ 287y \\ \end{pmatrix}$ \\

or il faut montrer que mB \\ $ \begin{pmatrix} \\ x' \\ \\ y' \\ \end{pmatrix}$ \\ = \\ $ \begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}$ \\

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:20

Si l'énoncé est posé tel quel alors il n'est pas correct.

Tous les calculs pour crypter/décrypter se font modulo 26.

Deux matrices  sont "égales" modulo 26 si leurs coefficients situés au même emplacement sont égaux modulo 26.

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 23:21

Désolé j'avais pas vu ta réponse, donc on a le droit d'appliquer des congruences à l'intérieur des matrices, je ne savais pas.

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 23:23

oui il est préciser dans l'énoncé "(les calculs étant faits modulo 26)"

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:24

Ce ne sera pas égal mais "égal" modulo 26

J'ai déjà fait ce calcul plus haut.

Il faut se rappeler que AB=BA=\begin{pmatrix} \\ 41&0 \\ \\ 0&41 \\ \end{pmatrix}

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:26


\\ \begin{pmatrix} \\ x' \\ \\ y' \\ \end{pmatrix} \\

est définie plus haut, ce n'est pas n'importe quoi.

Pas la peine de mettre des $ dans les formules. Le forum ne les reconnait pas.
Il ne reconnait que les balises latex

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 23:28

Citation :
Deux matrices  sont "égales" modulo 26 si leurs coefficients situés au même emplacement sont égaux modulo 26.


D'accord donc si j'ai bien compris c'est égal modulo 26 car

287 1[26] et que xx[26] et yy[26] ?

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:30

Oui, l'opération modulo un entier fixe est compatible avec la multiplication des matrices.
C'est facile à voir quand on multiplie une matrice deux-deux par une matrice colonne à deux lignes.

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:30

Oui on peut dire cela.

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:33

Matriciellement cela se voit bien:

\\ \begin{pmatrix} \\ 287&0 \\ \\ 0&287 \\ \end{pmatrix}\equiv \begin{pmatrix} \\ 1&0 \\ \\ 0&1 \\ \end{pmatrix}\mod{26}

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 23:34

Maintenant il faut que je m'en serve pour déchiffrer un code, je ferai ça demain.
En tout cas merci beaucoup pour ton aide, j'aurai appris plusieurs choses

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:35

7B\begin{pmatrix} \\ x' \\ \\ y' \\ \end{pmatrix}=7\begin{pmatrix} \\ 41&0 \\ \\ 0&41 \\ \end{pmatrix}\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}=\begin{pmatrix} \\ 7\times 41&0 \\ \\ 0&7\times 41 \\ \end{pmatrix}\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}\equiv   \\ \\ \begin{pmatrix} \\ 287&0 \\ \\ 0&287 \\ \end{pmatrix}\equiv \begin{pmatrix} \\ 1&0 \\ \\ 0&1 \\ \end{pmatrix}\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}\equiv \begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}\mod{26}

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 23:35

Oui effectivement, mais j'ignorais que l'on pouvais faire ça. Je ne l'ai jamais vu en cours.

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:36

J'imagine que les calculatrices modernes savent multiplier des matrices.

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 23:37

Tant qu'il n'y a pas de variable oui.

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:38

les coefficients d'une matrice produit sont des combinaisons linéaires des coefficients des matrices qu'on multiplie.

l'opération de prendre le reste modulo un entier est compatible avec le produit et la somme d'entiers

Posté par
FDPre : Déchiffrement de Hill 19-05-13 à 23:40

J'avais écrit une coquille:

7B\begin{pmatrix} \\ x' \\ \\ y' \\ \end{pmatrix}=7\begin{pmatrix} \\ 41&0 \\ \\ 0&41 \\ \end{pmatrix}\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}=\begin{pmatrix} \\ 7\times 41&0 \\ \\ 0&7\times 41 \\ \end{pmatrix}\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}=  \\ \\ \begin{pmatrix} \\ 287&0 \\ \\ 0&287 \\ \end{pmatrix}\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}\equiv \begin{pmatrix} \\ 1&0 \\ \\ 0&1 \\ \end{pmatrix}\begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}\equiv \begin{pmatrix} \\ x \\ \\ y \\ \end{pmatrix}\mod{26}

Posté par
kikou36re : Déchiffrement de Hill 19-05-13 à 23:44

Je n'avais pas remarqué x)
Merci pour ta patiente et tes explications détaillées !

Posté par
kikou36re : Déchiffrement de Hill 21-05-13 à 09:58

Bonjour,
Voici une question de la partie suivante :
1) Dans le dechiffrement, quelle condition particuliere sur 41 et 26 permet de repondre à la question 2 ( que j'ai mis plus haut sur le topic) ?

Posté par
FDPre : Déchiffrement de Hill 21-05-13 à 10:28

Il faut pouvoir trouver un inverse y multiplicatif à 41 modulo 26.

C'est à dire 41y \equiv 1 \mod{26}

on ne peut le faire que si 26 et 41 sont premiers entre eux.

C'est assez facile à voir:

41y \equiv 1 \mod{26} est équivalent à:

il existe k entier tel que:

41y=1+26k<=>41y-26y=1

Le théorème de Bézout affirme qu'on ne peut résoudre cette équation en y,k que si 41 et 26 sont premiers entre eux.

Posté par
kikou36re : Déchiffrement de Hill 21-05-13 à 18:01

Facile à voir, la oui mais je ne pense pas que j'y aurais pensé x) Mais en tout cas j'ai compris !
Merci !


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !