Forum de mathématiques - Bibm@th.net

Daudetarago

Membre

Inscription : 10-12-2010

Messages : 36

Puissances d'une matrice

Bonjour à toutes et à tous,

Puissances d'une matrice de codage, plus précisément, en fait.
Pour les mots à deux lettres (désolé c'est mon premier message et je ne sais pas encore utiliser laTex)
la matrice de codage est m =[[-1,1][2,-1]] coefficients dans Z/26Z
pour n>2 la matrice a la forme générale (n×n) suivante:
m= [[-1,1,0,...,0][0,-1,1,0,...,0]....[0,0,....,0,1,-1][1,0,0,....,1,-1]]
par exemple pour les mots à 4 lettres
m=[[-1,1,0,1][0,-1,1,0][0,0,-1,1][1,0,1,-1]]
on essaie de trouver par un moyen  non informatique quel est le plus petit K entier positif non nul tel que
m^K=I (I matrice identité)
On trouve avec un programme
mot à 2 lettres  K=28
mot à 3 lettres K=1281
mots à 4 lettres K=168
mots à 5 lettres K=959171
mots à 6 lettres K=14280
mots à 7 lettres K=486300999
mots à 8 lettres K=8044680
mots à 9 lettres K=45658261185
mots à 10 lettres K=4022340
Je n'ai pas trouvé pour les mots à plus de 10 lettres

Merci pour l'aide

Daudetarago

Daudetarago

Membre

Inscription : 10-12-2010

Messages : 36

Re : Puissances d'une matrice

Bonjour
On peut modifier la matrice m2 pour que son déterminant soit égal à 1 comme c'est le cas pour toutes les matrices mn
m2=[[1,-1][-1,2]]
Dans 26/26Z le plus petit entier non nul tel que m2^K2=I2
devient K2= 42
Ensuite il y a une erreur pour K10
Dans 26/26Z le plus petit entier non nul tel que m10^K10=I10
est K10= 5124 et non pas 4022340 comme indiqué auparavant

Daudetarago

Membre

Inscription : 10-12-2010

Messages : 36

Re : Puissances d'une matrice

Bonjour
Désolé il y a à nouveau une erreur
Le déterminant des matrices mn avec n=2k est égal à -1
les puissances d'exposant impair de ces matrices ont donc un déterminant égal à -1
les puissances d'exposant pair de ces matrices ont donc un déterminant égal à 1
On peut revenir donc à m2=[[-1,1][2,-1]  avec  K2=28
Le déterminant des matrices mn avec n=2k+1 est égal à 1
Toutes les puissances de ces matrices ont alors un déterminant égal à 1
Merci

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Puissances d'une matrice

Salut Dausterago,

Bienvenue sur BibMath...
Je déplace ta discussion dans la section Entraide (supérieur) pour plus d'exposition : tel qu'exposé il me semble que c'est bien davantage un problème mathématique que cryptographique.
Personnellement, je ne peux pas t'aider sur le fond.
Sur la forme :

désolé c'est mon premier message et je ne sais pas encore utiliser laTex

Objection ! Argument non valable, il te suffisait de vouloir ;-)
* Soit tu disposes de Java installé sur ta machine, alors via l'interface humain/LateX accesse=ible via un clic sur "Insérer une équation", il n'y a rien à savoir. C'est très intuitif et j'au rédigé une mini-aide (70 ko) en pdf qu'on peut appeler depuis l'Editeur,
* Soit tu te familiarises un peu avec mon tuto LaTeX pour comprendre comment ça marche en cliquant sur le lien Code LateX à côté du bouton Insérer une équation.
  Code pour afficher ta matrice (4,4):
  \begin{pmatrix}-1&1&0&1\\0&-1&1&0\\0&0&-1&1\\1&0&1&-1\end{pmatrix}
que tu insères entre  balises tex et /tex (entres crochets) comme ça (parce que ci-dessus, elles sont absentes) :
  J'utilise les balises code ici qui n'affichent que du texte pour te permettre de voir ce que tu dois écrire.
 

[tex]\begin{pmatrix}-1&1&0&1\\0&-1&1&0\\0&0&-1&1\\1&0&1&-1\end{pmatrix}[/tex]

Avec les balises tex, voilà le rendu : [tex]\begin{pmatrix}-1&1&0&1\\0&-1&1&0\\0&0&-1&1\\1&0&1&-1\end{pmatrix}[/tex]

  Je te souhaite beaucoup de réponses.

@+

Daudetarago

Membre

Inscription : 10-12-2010

Messages : 36

Re : Puissances d'une matrice

Bonjour
Pour la matrice m11 le plus petit entier non nul K11 tel que m11^K11=I11
est K11=2^4×3×5×7×23×89×5229043
Pourquoi retrouve-t-on le même facteur premier 5229043 à la fois dans K7 et dans K11 ????
m7^K7=I7     K7=3×31×5229043
Merci

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Puissances d'une matrice

Salut mec,

yoshi s'emm... à te montrer comment on code en Latex, et toi, tu viens à nouveau  écrire un truc illisible sans faire le moindre effort ?!!!

Je ne vais même pas aller plus loin,

ciao !

thadrien

Membre

Lieu : Grenoble

Inscription : 18-06-2009

Messages : 526

Site Web

Re : Puissances d'une matrice

Salut,

@Daudetarago : tu devrais vraiment coder en LaTeX car il beaucoup de matheux, moi y compris, travaillent "au visuel". Si la matrice ne ressemble pas à ce que l'on a l'habitude de voir, on n'arrive même pas à comprendre le problème.

On t'aidera quand tu auras fait l'effort de coder en LaTeX.

A+

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Puissances d'une matrice

Salut,

@Daudetarago : tu devrais vraiment coder en LaTeX car il beaucoup de matheux, moi y compris, travaillent "au visuel". Si la matrice ne ressemble pas à ce que l'on a l'habitude de voir, on n'arrive même pas à comprendre le problème.

On t'aidera quand tu auras fait l'effort de coder en LaTeX.

A+

Là, si t'as pas compris l'ami, c'est que tu es sourd de la feuille ... heu, je veux dire, que tu es aveugle des oreilles ...

Y'a plus que l'ami yoshi pour trisser et c'est bon, t'auras ton compte, sans avoir de réponse pour autant, car on ne comprend pas bien ton pb, en fait.

Si tu pouvais être plus clair ?!?

guetel seguin

Invité

Re : Puissances d'une matrice

Le produit  de deux matrices est il commutatif? Donner un example. Dans quelle cas parle t-on de matrice de Vandermonde? Quelle est sa forme.

thadrien

Membre

Lieu : Grenoble

Inscription : 18-06-2009

Messages : 526

Site Web

Re : Puissances d'une matrice

1/ Un nouveau sujet = un nouveau message
Je sais qu'il faut moins de clics pour répondre à un nouveau message que pour créer un nouveau sujet, mais c'est quand même pas à faire.

2/ J'ai les réponses à ton sujet, mais je les donnerai quand tu auras ouvert une nouvelle discussion. J'ai pas envie de secouer ma flemme alors que tu ne fais pas l'effort d'ouvrir un nouveau sujet.

Daudetarago

Membre

Inscription : 10-12-2010

Messages : 36

Re : Puissances d'une matrice

Bonjour Mesdames Messieurs
Dans [tex]\mathbb{Z}/p\mathbb{Z}[/tex] le nombre de matrices inversibles [tex]n*n[/tex] est donné par
[tex]N=p^{\frac{n(n-1)}{2}}(p^n-1)(p^{n-1}-1)...(p^2-1)(p-1)[/tex] à cause d'une histoire de colonnes linéairement indépendantes dans les matrices
On choisit une de ces matrices [tex](m_n)[/tex] et on cherche le plus petit entier K non nul tel que [tex](m_n)^K=I_n[/tex]
K est un diviseur de N
Par exemple pour la matrice de codage [tex](m_{11})[/tex]
Dans [tex]\mathbb{Z}/13\mathbb{Z}[/tex]
[tex]N_{13}=13^{55}(13^{11}-1)(13^{10}-1)...(13^2-1)(13-1)[/tex]
On trouve dans [tex]N_{13}[/tex] le facteur premier 5229043 qui est situé dans [tex](13^7-1)[/tex]
Dans [tex]\mathbb{Z}/2\mathbb{Z}[/tex]
[tex]N_{2}=2^{55}(2^{11}-1)(2^{10}-1)...(2^2-1)(2-1)[/tex]
On trouve dans [tex]N_{2}[/tex] les facteurs premiers 23 et 89 qui sont situés dans [tex](2^{11}-1)[/tex]
et on trouve les facteurs [tex]2^4,3,5\ et \ 7[/tex] aussi dans [tex]N_{2}[/tex] et [tex]N_{13}[/tex]
C'est ainsi possible que dans [tex]\mathbb{Z}/26\mathbb{Z}[/tex]

[tex]K_{11}=2^4*3*5*7*23*89*5229043[/tex]
Cordialement
Daudétarago

Daudetarago

Membre

Inscription : 10-12-2010

Messages : 36

Re : Puissances d'une matrice

Bonsoir à toutes et à tous
Autre exemple (Désolé on m'a sorti du forum crypto)
La matrice de codage à coefficients dans [tex]\mathbb{Z}/26 \mathbb{Z}[/tex]
servant à coder les mots à 3 lettres, matrice choisie par convention,
est [tex](m_3)=\begin{pmatrix}-1&1&0\\0&-1&1\\1&1&-1\end{pmatrix}[/tex]
Elle permet de trouver le code de rang k d'un mot [tex]u_1u_2u_3[/tex] en calculant [tex]\begin{pmatrix}-1&1&0\\0&-1&1\\1&1&-1\end{pmatrix}^k*\begin{pmatrix}u_1\\u_2\\u_3\end{pmatrix}[/tex]
Exemple pour le mot MAI [tex]u_1=13,u_2=1,u_3=9[/tex] (avec les conventions canadiennes) les codes successifs sont
NHE(rang 1) TWQ (rang 2) CTZ(rang 3) ...etc
On se demande quelle est la plus petite valeur  [tex]K_3[/tex] entière non nulle telle que
[tex](m_3)^{K_3}=I_3[/tex]
dans [tex]\mathbb{Z}/13 \mathbb{Z}[/tex]
[tex]N_{13}=13^3(13^3-1)(13^2-1)(13-1)=2*3^4*7*13^3*61[/tex]
dans [tex]\mathbb{Z}/2 \mathbb{Z}[/tex]
[tex]N_{2}=2^3(2^3-1)(2^2-1)(2-1)=2^3*3*7[/tex]
Les facteurs premiers de [tex]K_3[/tex] sont à chercher dans [tex]N_{2}[/tex] et [tex]N_{13}[/tex]
Ensuite on peut imaginer un programme lancé à partir de [tex]k = N_{2}* N_{13}[/tex] et qui éliminerait successivement les facteurs inutiles de [tex]k = N_{2}* N_{13}[/tex] pour obtenir finalement le plus petit diviseur    [tex]K_3 \ de \ k = N_{2}* N_{13}[/tex]  tel que [tex](m_3)^{K_3}=I_3[/tex]
On trouve ainsi [tex]K_3=1281=3*7*61[/tex] et effectivement le code de rang 1281 de MAI est MAI
La recherche des moyens d'étude des cycles de codes à n lettres est assez intéressante à découvrir du moins pour un retraité.
Pour les codes à 3 lettres on a:
1 cycle à 1 code {ZZZ}
1 cycle à 7 codes {MMM,ZZM,ZMM,MZZ,MZM,MMZ,ZMZ}
12 cycles à 183 codes à 3 lettres toutes paires Z,B,D,F,H,J,L,N,P,R,T,V,X
12 cycles à 1281 codes à 3 lettres non toutes paires
[tex]1+7+12*183+12*1281=17576=26^3[/tex]