Vektoriteration mittels Matrixmultiplikation

10/09/2010 - 20:42 von Hans-Werner | Report spam
Bei meiner Beschàftigung mit dem Thema Kryptographie bin ich auf
folgendes Problem gestossen:

Gegeben ist ein Vektor der Lànge n mit ganzzahligen Werten von 1 bis n
z.B.: Vektor = [1 2 3 4] (Matlab Schreibweise)
Dieser wird mit einer quadratischen Matrix, mit ebenfalls ganzzahligen
Werten im Bereich von 1 bis n, multipliziert z.B.: Matrix = [1 3 2 4;
4 3 2 1; 1 1 1 3; 3 1 2 4]
Die Multiplikation erfolgt Modulo n.
Das Ergebnis ist wiederum ein Vektor der Lànge n.
NeuerVektor = mod(Vektor * Matrix,4)+1;
Plus 1 damit das Ergebnis wieder im Bereich 1..n liegt.
Vektor = NeuerVektor;
Der neue Vektor wird zum alten Vektor und das "Spiel" wiederholt sich.
Im genannten Fall ergeben sich laut Matlab nacheinander folgende
Vektoren:
[1 2 3 4],[1 1 2 4], [4 1 3 4],[4 3 2 3],[4 3 3 2],[2 3 2 1],[4 3 3 2],
[2 3 2 1]
Aus [2 3 2 1] wird [4 3 3 2] und vice versa.
Es ergibt sich eine Folge der Lànge 7 und eine Folge der Lànge 2.
Es wàren aber 4**4 = 256 unterschiedliche Vektoren möglich; also eine
Folge der Lànge 256.
Kann ich auf diese Weise alle Vektoren von [1 1 1 1] bis [4 4 4 4]
also z.B. [4 3 4 1] erzeugen ?
Wenn ja, unter welchen Bedingungen bezüglich z.B. Determinante,
Subdeterminanten etc. ?
Bestehen besondere Anforderungen an den Startvektor bzw. die Matrix um
eine möglichst grosse Anzahl unterschiedlicher Vektoren zu erzeugen ?

Obige Formulierung ist sicher nicht mathematisch korrekt, aber ich
hoffe das ich mich verstàndlich ausgedrückt habe.
 

Lesen sie die antworten

#1 Gottfried Helms
10/09/2010 - 23:42 | Warnen spam
Am 10.09.2010 20:42 schrieb Hans-Werner:
Kann ich auf diese Weise alle Vektoren von [1 1 1 1] bis [4 4 4 4]
also z.B. [4 3 4 1] erzeugen ?
Wenn ja, unter welchen Bedingungen bezüglich z.B. Determinante,
Subdeterminanten etc. ?


(Kurze Anmerkung zuvor: es empfiehlt sich, alles in echten Residuen
darzustellen, also die Reste immer von 0..n-1 gelten zu lassen.)

Eine h-fach wiederholte Multiplikation deines Vektors A mit der Matrix M
kannst du auch als einfache Multiplikation von A mit M^h verstehen.
Wenn Du dir die Potenzen von M^h (mod n), für h=0..n ansiehst, wirst du
sehr wahrscheinlich eine kürzere Periode p als n finden (p<n).
Logischerweise ist dann auch die Anzahl der Resultate A * M^h (mod n)
auf p unterschiedliche Resultate begrenzt.

Der am einfachsten diskutierbare Fall ist, wenn M diagonalisierbar ist,
also wenn
M = W * D * W^-1
wobei D diagonal ist. Dann ist die Anzahl möglicher Varianten von M (mod n)
durch die Anzahl der Varianten von D (mod n) gegeben, und das ist dann
einfach die Frage des kgV der Periodenlàngen für jeden einzelnen der
Diagonaleintràge von D. Also maximal n, denn

n*<irgendein Residuum mod n> = 0 (mod n)

Aber das kgV der Periodenlàngen kann leicht auch kleiner werden, wenn
die Diagonaleintràge echte Teiler von n sind und alle einen Teiler t
von n gemeinsam haben. (Also n, t=6, alle d0..d11 teilen 6)

Bestehen besondere Anforderungen an den Startvektor bzw. die Matrix um
eine möglichst grosse Anzahl unterschiedlicher Vektoren zu erzeugen ?



Daraus ergeben sich schon mal ein paar Anforderungen.
Nun muß es nicht sein, daß M diagonalisierbar ist. Man kann also
die Diskussion der Anforderungen hier weiter verbreitern...

Gruß -

Gottfried

Ähnliche fragen