Gleichungssysteme mod N

Neue Frage »

Fletcher Auf diesen Beitrag antworten »
Gleichungssysteme mod N
Guten Tag,

prinizipiell geht es mir um eine Aufgabe aus der Kryptografie, allerdings ist das ganz algebraisch zu lösen. Man hat das Alaphabet A,B,C,...,Z mit den Zahlen 0,1,...,25 identifiziert. Dabei weiß ich jetzt, dass folgende Paare auf andere Paare abgebildet werden:


Meine Abbildung hat die Form:

Ich habe nun ein lineares Gleichungssystem zu lösen, wobei a_1, ... , a_6 gesucht sind. Ich verrechne mich allerdings ständig und habe leider kein Maple hier. Kann mir jemand helfen, diese Kongruenzen zu berechnen? Ich verwende das Gaussverfahren, aber was mache ich wenn negative Zahlen oder Zahlen >26 herauskommen?! Meine Algebra-Kenntnisse sind offen gesagt nicht die besten...

Vielen Dank
Fletcher Auf diesen Beitrag antworten »

Niemand eine Idee?

Was muss man mod 26 beachten beim Lösen eines lineare Gleichungssystems?
Auch wenn ich etwas herausbekomme und dann einsetze stimmen die Ergebnisse nicht. verwirrt
Mystic Auf diesen Beitrag antworten »

Wenn wir die 2 x 2-Matrix kürzer mit A bezeichnen, so gilt offenbar




was dann weiter auf



führt... Daraus solltest mal das A ausrechnen können...

Und denk daran, ganz normal mod 26 rechnen und wenn Brüche auftreten, diese sofort in ganze Zahlen umwandeln, indem du den Zähler mit dem Inversen des Nenners mod 26 multiplizierst (soferne dieses exisitiert, sonst hättest da ein Problem! verwirrt )...
Fletcher Auf diesen Beitrag antworten »

Danke, aber da wird ja gar nicht der Vektor a_5, a_6 berücksichtigt oder??

Gruß
Mystic Auf diesen Beitrag antworten »

Omg, warum wohl habe ich diese seltsamen Differenzen unten gebildet, doch nicht zum Spaß... traurig




Dein Vektor fällt durch diesen "Trick" heraus und muss erst später, wenn man die Matrix A schon kennt, bestimmt werden...
Fletcher Auf diesen Beitrag antworten »

Oh, das war mein Fehler! Danke Freude
 
 
Fletcher Auf diesen Beitrag antworten »

Ich habe das komplette System nun gelöst. Die Matrix A schaut folgendermaßen aus:

, der Vektor berechnet sich zu .

Ich habe diese Abbildung nun mit anderen schon bekannten Paaren getestet und da stimmt es komischerweise nicht immer überein.
Mystic Auf diesen Beitrag antworten »

Hm, die Lösung ist jedenfalls



Wie kann man sich nach all meinen Vorgaben überhaupt noch verrechnen? unglücklich

Bei der Berechnung von A ging es doch wegen



im wesentlichen darum, die Matrix



zu invertieren, wobei die Invertierbarkeit wegen



und ggT(3,26)=1 tatsächlich gegeben ist... Durch Anwendung der üblichen Prozedur, um die inverse Matrix zu erhalten (kurz: vertausche Haupdiagonalelemente, ändere Vorzeichen bei Nebendiagonalelementen und dividiere alle Elemente durch die Determinante) und wegen



erhält man dann



und daher schließlich



Durch Einsetzen von A und einem Punktepaar enthält man dann schließlich die oben angegebene Endformel... An welcher Stelle bist du von diesem logisch vorgegebenen Weg abgewichen?!
Fletcher Auf diesen Beitrag antworten »

Ich habe die Matrix nicht versucht zu invertieren, obwohl mir dieser Weg klar war wollte ich ihn nicht gehen!
Ich habe vielmehr versucht ein Gleichungssystem zu lösen und komme auf die obengenannten Zahlen, welche mir auch von Maple bestätigt wurden. Also

Analog für die anderen beiden Matrixelemente.

Ich habe deinen Weg verstanden und kann ihn nachvollziehen, aber meiner ist doch deshalb nicht falsch. Vielleicht rechne ich umständlicher. Fakt ist, es müsste in beiden Fällen das gleiche Ergebnis herauskommen. Dies ist nicht der Fall!

Kannst du mir erklären weshalb?
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Fletcher
Ich habe die Matrix nicht versucht zu invertieren, obwohl mir dieser Weg klar war wollte ich ihn nicht gehen!
Ich habe vielmehr versucht ein Gleichungssystem zu lösen und komme auf die obengenannten Zahlen, welche mir auch von Maple bestätigt wurden. Also

Analog für die anderen beiden Matrixelemente.

Ich habe deinen Weg verstanden und kann ihn nachvollziehen, aber meiner ist doch deshalb nicht falsch. Vielleicht rechne ich umständlicher. Fakt ist, es müsste in beiden Fällen das gleiche Ergebnis herauskommen. Dies ist nicht der Fall!

Kannst du mir erklären weshalb?


Ich kann dir natürlich gar nichts erklären, denn im Gegensatz zu mir hast du ja deinen Lösungsweg nicht im Detail beschrieben... unglücklich

Eines ist jedenfalls sicher, dein A, nämlich



erfüllt ja nicht einmal deine obigen Kongruenzen



geschweige denn, sonst irgendwas... Davon, dass ich keine Ahnung habe, wo diese Kongruenzen herkommen, rede ich jetzt gar nicht... traurig
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »