Gleichungssysteme mod N |
31.10.2009, 12:13 | Fletcher | Auf diesen Beitrag antworten » | ||
Gleichungssysteme mod N 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 |
||||
01.11.2009, 09:28 | 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. |
||||
01.11.2009, 10:19 | 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! )... |
||||
01.11.2009, 21:50 | Fletcher | Auf diesen Beitrag antworten » | ||
Danke, aber da wird ja gar nicht der Vektor a_5, a_6 berücksichtigt oder?? Gruß |
||||
01.11.2009, 22:47 | Mystic | Auf diesen Beitrag antworten » | ||
Omg, warum wohl habe ich diese seltsamen Differenzen unten gebildet, doch nicht zum Spaß... Dein Vektor fällt durch diesen "Trick" heraus und muss erst später, wenn man die Matrix A schon kennt, bestimmt werden... |
||||
02.11.2009, 08:21 | Fletcher | Auf diesen Beitrag antworten » | ||
Oh, das war mein Fehler! Danke |
||||
Anzeige | ||||
|
||||
02.11.2009, 19:12 | 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. |
||||
02.11.2009, 23:28 | Mystic | Auf diesen Beitrag antworten » | ||
Hm, die Lösung ist jedenfalls Wie kann man sich nach all meinen Vorgaben überhaupt noch verrechnen? 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?! |
||||
03.11.2009, 09:27 | 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? |
||||
03.11.2009, 10:28 | Mystic | Auf diesen Beitrag antworten » | ||
Ich kann dir natürlich gar nichts erklären, denn im Gegensatz zu mir hast du ja deinen Lösungsweg nicht im Detail beschrieben... 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... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|