Equations à coéfficients dans Z/29Z
Bonjour,
Je souhaiterais savoir si quelqu'un a une méthode pour résoudre le problème suivant.
On se place dans Z/29Z.
On souhaite déterminer une matrice A INVERSIBLE de taille 3x3 et un vecteur w de taille 3 vérifiant :
$ A . \begin{pmatrix}
21\\
14\\
27
\end{pmatrix} + w =
\begin{pmatrix}
17\\
0\\
19
\end{pmatrix}$
$ A . \begin{pmatrix}
7\\
0\\
8
\end{pmatrix} + w =
\begin{pmatrix}
10\\
20\\
7
\end{pmatrix}$
$ A . \begin{pmatrix}
17\\
14\\
19
\end{pmatrix} + w =
\begin{pmatrix}
6\\
20\\
19
\end{pmatrix}$
$ A . \begin{pmatrix}
4\\
8\\
18
\end{pmatrix} + w =
\begin{pmatrix}
1\\
26\\
17
\end{pmatrix}$
Pour le moment je n'ai trouvé qu'une solution en utilisant l'aide de l'ordinateur.
Le problème provient de la cryptographie.
Merci
Laurent
Je souhaiterais savoir si quelqu'un a une méthode pour résoudre le problème suivant.
On se place dans Z/29Z.
On souhaite déterminer une matrice A INVERSIBLE de taille 3x3 et un vecteur w de taille 3 vérifiant :
$ A . \begin{pmatrix}
21\\
14\\
27
\end{pmatrix} + w =
\begin{pmatrix}
17\\
0\\
19
\end{pmatrix}$
$ A . \begin{pmatrix}
7\\
0\\
8
\end{pmatrix} + w =
\begin{pmatrix}
10\\
20\\
7
\end{pmatrix}$
$ A . \begin{pmatrix}
17\\
14\\
19
\end{pmatrix} + w =
\begin{pmatrix}
6\\
20\\
19
\end{pmatrix}$
$ A . \begin{pmatrix}
4\\
8\\
18
\end{pmatrix} + w =
\begin{pmatrix}
1\\
26\\
17
\end{pmatrix}$
Pour le moment je n'ai trouvé qu'une solution en utilisant l'aide de l'ordinateur.
Le problème provient de la cryptographie.
Merci
Laurent
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je ne comprends pas la remarque de RAJ : il y a $12$ inconnues (les coeffs de $A$, et les $w_i$), et $12$ équations. On peut écrire ça sous la forme d'un grand système $12*12$, dont le déterminant modulo $29$ est non nul : il y a une unique solution, qui doit être, si mes calculs sont corrects :
$A := \left[
{\begin{array}{rrr}
18 & 24 & 16 \\
0 & 17 & 10 \\
6 & 12 & 12
\end{array}}
\right] $
qui est bien inversible,
et $w = {}^t (17\quad 27\quad 14)$.
Cordialement,
Ritchie
Ca m'a l'air de fonctionner. Il y a douze inconnues.
Pour chacune des lignes des quatre équations prises ensemble (les lignes de chacun des A.xi+wj=yi), on obtient pour chacune d'elle un système de quatre équtions à quatre inconnues :
On fait alors (1)-(3), ce qui relie deux inconnues. Après à l'aide de l'ordi, j'ai résolu en testant les 29 couples de valeurs possibles pour ces deux inconnues. Ensuite on injecte dans (2) pour trouver l'inconnue du vecteur w, puis dans (1) par exemple pour déterminer la dernière valeur. On vérifie ensuite que les quatre valeurs trouvées vérifient bien les 4 équations.
On fait de même encore deux fois pour obtenir les 8 autres valeurs.
On vérifie ensuite que la matrice A obtenue est inversible (mod 29).
Ainsi j'ai trouvé :
$ A = \begin{pmatrix}
28 & 26 & 7 \\
21 & 27 & 23 \\
4 & 0 & 8
\end {pmatrix}$
et w = (19,8,2)
Désolé, si ce n'est pas clair, mais de toute manière, un ordinateur est quasi indispensable avec cette méthode, à moins d'aimer les calculs...
Laurent
En fait, après vérifications sur ordinateur, ni ma solution ni la tienne ne conviennent. IL faut donc prendre pour A la matrice suivante (désolé, flemme du latex) :
2 20 4
6 28 9
24 18 17
et pour w :
22
22
22
Maple confirme bien qu'il s'agit de la bonne solution (ouf!).
En fait, on peut quand même le faire à la main, puisqu'il s'agit finalement de résoudre 3 systèmes 4,4 du type B*X = b, avec toujours la même matrice B...
Mais bon, si l'ordi est là, c'est plus rapide:
Cordialement,
Ritchie
Ton problème se ramène à une équation dans $\mathbb{M}_4(\Z/29\Z)$ de la forme $\mathcal{A}.V=T$ où $\mathcal{A},\ V,\ T$ sont les trois matrices $4\times 4$ suivantes : $$ \mathcal{A}=\begin{pmatrix} A & w \\ 0&1\end{pmatrix} \qquad ; \qquad V=\begin{pmatrix} v_1&v_2&v_3&v_4 \\ 1&1&1&1 \end{pmatrix} \qquad ; \qquad T=\begin{pmatrix} t_1&t_2&t_3&t_4 \\ 1&1&1&1 \end{pmatrix} $$ en appelant $v_1= \begin{pmatrix} 21\\ 14\\ 27 \end{pmatrix}$ et $t_1=\begin{pmatrix} 17\\ 0\\19 \end{pmatrix}$ et pareillement pour $v_2, t_2, \ldots, v_4,t_4$
Alors si $V$ est inversible, la solution unique sera $$\mathcal{A}=T.V^{-1} $$ \lien{http://wims.unice.fr/\~wims/wims.cgi?lang=fr} (suivre calculatrice de matrice)
permet calcul du déterminant $\det V = 1184 \in \Z$, et en prenant le modulo 29 on obtient $\det V = 24 \neq 0 \in \Z/29\Z$.
Donc V est inversible, et WWIMS en donne même la valeur dans $\mathbb{M}_4(\Q)$. En passant dans WWIMS multiplieur de matrice, on calcule $T.V^{-1}$ comme matrice à coefficients dans $\Q$.
Alors il n'y a plus qu'à aller dans WWIMS Calculatrice sur un corps fini, pour obtenir la traduction dans $\Z/29\Z$ de chacun des coefficients de la matrice $\mathcal{A}$ obtenue, puis d'en extraire $A$ et $w$.
On retrouve la solution donnée par Ritchie : $$A= \begin{pmatrix}2& 20& 4 \\
6& 28& 9 \\
24& 18& 17 \end{pmatrix} \qquad ; \qquad w=\begin{pmatrix}22 \\ 22 \\ 22 \end{pmatrix}$$ Alain
Laurent
Soient $A_0,A_1,A_2,A_3$ des points de $K^3$.
Soient $B_0,B_1,B_2,B_3$ des points de $K^3$.
Si $(A_0,A_1,A_2,A_3)$ est un repère affine (c-à-d si $A_0,A_1,A_2,A_3$ ne sont pas coplanaires), alors il existe un endomorphisme affine et un seul $f$ de $K^3$ tel que $f(A_i)=B_i$ pour tout $i\in[\![0,3]\!]$.
Ici 29 est un nombre premier, donc $\Z/29\Z$ est un corps.
On prend $K=Z/29\Z$.