Modulo-Berechnung - Gleichungssystem - wie lösen?

Neue Frage »

ModuloMelusine Auf diesen Beitrag antworten »
Modulo-Berechnung - Gleichungssystem - wie lösen?
Meine Frage:
Hallo,

in einer Mathe-Klausur, die ich vor zwei Tagen geschrieben habe, gab es folgende Aufgabe:

Eine monoalphabetische, monographische Chiffrierung eines deutschen Textes, der nur aus den Großbuchstaben V = { A, B, ... , Z } besteht, funktioniere wie folgt:
Den Buchstaben aus V seien wie üblich die Zahlen { 0, 1, ... , 25 } zugeordnet, damit man mit ihnen "rechnen" kann. Die Verschlüsselung eines Klartextbuchstaben x erfolgt über die Formel
f(x) = (ax + b) mod 26
mit ganzen Zahlen a, b Element aus { 0, 1, ... 25 }.

Der Buchstabe E wird in den Buchstaben C überführt, der Buchstabe I in den Buchstaben M.

Welche Werte haben a und b? Achtung, die Lösung ist nicht eindeutig, Sie sollen alle Lösungen finden.

Meine Ideen:
Nachdem ich die Buchstaben zugeordnet hatte, ergaben sich folgende Gleichungen:

6a + b =(kongruent) 4 (mod 26)
9a + b =(kongruent) 12 (mod 26)

Die Lösung für 6a + b ist also eine Zahl aus der selben Resteklasse wie 4, also 30, 56, 82, ...
Die Lösung für 9a + b ist dementsprechend eine Zahl aus der selben Resteklasse wie 12, also 12, 38, 64, ...

Ich habe in der Klausur diverse Zahlen für a und b durchprobiert, aber bin in der kurzen Zeit zu keiner Lösung gekommen. Abends hatte ich dann Muße und Excel und habe damit verschiedene Kombinationen durchprobiert. Schließlich bin ich auf die Lösung gekommen: a = 24, b = 16 bzw. a = 11 und b = 16.

Ein Kommilitone, den ich gefragt habe, wie er das gelöst hat, meint, er hätte es auch nur über Probieren lösen können.

Aber es muss doch irgendeinen Weg geben, das auszurechnen?

Ich bin bei dieser ganzen Modulo-Rechnerei nicht so fit. Immer wenn ich denke, dass ich es kapiert habe, flutscht es mir wieder davon. Aber ich träume nun schon die 2. Nacht von dieser Aufgabe und möchte unbedingt wissen, wie man das löst.

Kann mir jemand weiterhelfen? Das wäre so klasse!

Vielen, vielen Dank!
ModuloMelusine Auf diesen Beitrag antworten »

Ich wollte gerade mein Posting nochmal editieren, aber es ist leider nicht mehr möglich.

Ich habe mir nochmal die Zahlen angeguckt und festgestellt, dass ich mich "verrechnet" habe bzw. beim Ausprobieren vertan habe.

Eine mögliche Lösung ist:
a = 20, b = 14.

Denn dann gilt:
6 * 20 + 14 = 134
134 : 26 = 5 Rest 4

Und
9 * 20 + 14 = 194
194 : 26 = 7 Rest 12

Ich gucke die Zahlen an und versuche, irgendeine Gesetzmäßigkeit zu erkennen ...
mYthos Auf diesen Beitrag antworten »

Man kann das Modulo-Gleichungssystem genauso bearbeiten wie ein herkömmliches lGS.
Also




________________________________
(1) von (2) subtr.



Daraus folgt , bei t = 2 gibt's eine ganzzahlige Lösung (3a = 60)





Nun aus (1) b berechnen, von der sich ergebendenden negativen Zahl die Restklasse mod 26 bestimmen und fertig.

mY+
ModuloMelusine Auf diesen Beitrag antworten »

Ich antworte mir mal selber.

Ich habe jetzt durch einen Link zu einem anderen Strang, der unten eingeblendet wurde, herausgefunden, dass ich ganz einfach addieren und subtrahieren kann.

Ich kann also meine erste Gleichung nach b umformen:




Dann kann ich b in meiner zweiten Gleichung ersetzen:




Aber wie komme ich denn jetzt weiter?

Jetzt hilft doch eigentlich nur noch ausprobieren, oder?

8 ist in der selben Restklasse wie 34, 60, 86, 112, 138, 164, 190, 216, ...

Was davon sind Vielfache von 3? Da kommen z.B. 60 und 138 in Frage.
3 * a = 60
a = 20

3 * a = 138
a = 46 -> kommt nicht in Frage, da a nicht größer als 25 sein darf.


Wenn ich nun a habe, kann ich das wieder in meine Formel von oben einsetzen:





Da ich nun weiß, dass b zwischen 0 und 25 liegen muss, muss ich einfach weitere Zahlen der Restklasse bestimmen, also -116, -90, -64, -38, -12, 14, 40, ...

Da b zwischen 0 und 25 liegen muss, ergibt sich also b=14.

Wenn ich a in die 2. Gleichung einsetze, ergibt sich:




Nun suche ich wieder weitere Zahlen aus der Restklasse:
- 168, - 142, -116, -90, -64, -38, -12, 14, 40, ...

Hier ergibt sich dieselbe Lösung, nämlich b = 14.


Nun probiere ich a = 20 und b = 14 mit meinen beiden Gleichungen aus:

1. Gleichung


ist korrekt

2. Gleichung


ist ebenfalls korrekt

Nun bin ich noch ein bisschen verwirrt, weil der Professor ja geschrieben hat, dass die Lösung nicht eindeutig sei. Ich habe aber nur eine mögliche Zahlenkombination herausbekommen und bezweifle, dass es weitere Lösungen gibt.

Aber immerhin kann ich jetzt nachts wieder schlafen, weil ich jetzt herausgekriegt habe, wie man das hätte lösen können. Wenn man sich den Lösungsweg vorher überlegt hätte, dann hätte man das wohl durchaus in 10 Minuten schaffen können ...
ModuloMelusine Auf diesen Beitrag antworten »

Hallo mYthos,

vielen Dank für deine Antwort! Freude

Jetzt habe ich es verstanden.

Ich habe erst noch über diesen Teil nachgedacht:

Zitat:
Original von mYthos
Daraus folgt , bei t = 2 gibt's eine ganzzahlige Lösung (3a = 60)


Aber es ist ja klar, dass sich hier wieder eine lineare Gleichung ergeben muss:

,

also um die Summe aus einem beliebig großen Vielfachen von 26 und dem Rest 8.

Trotzdem kommt man doch hier nur mit "Raten" weiter, oder sehe ich das falsch? Ist ja eine Gleichung mit 2 Unbekannten.

Naja, die Klausur ist eh vorbei, aber jetzt kann ich endlich wieder nachts schlafen, ohne von dieser blöden Aufgabe zu träumen ...

Viele Grüße
ModuloMelusine
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von ModuloMelusine
Der Buchstabe E wird in den Buchstaben C überführt, der Buchstabe I in den Buchstaben M.

[...]

Nachdem ich die Buchstaben zugeordnet hatte, ergaben sich folgende Gleichungen:

6a + b =(kongruent) 4 (mod 26)
9a + b =(kongruent) 12 (mod 26)

Ich stelle schon mal dein Gleichungssystem in Frage: Die vier in den Informationen beteiligten Buchstaben werden gemäß deines Systems kodiert als

E = 4
C = 2
I = 8
M = 12

Also sollte das System doch



lauten, nicht wahr? Und hier gibt es in der Tat zwei Lösungen, zumindest für :

und
 
 
ModuloMelusine2 Auf diesen Beitrag antworten »

Guten Morgen René,

ich bin mir wegen der Buchstaben nicht mehr sicher, da ich den Aufgabenzettel mit abgeben musste. Ich weiß nur noch die Gleichungen. Eventuell ist mir gestern abend beim Aufschreiben der Buchstaben etwas durcheinandergeraten.

Ich habe jetzt nochmal beim Professor nachgefragt, ob er mir nochmal die richtigen Buchstaben nennen kann. Wenn ich sie weiß, trage ich sie hier nach.

Entschuldigung!

Viele Grüße
ModuloMelusine
René Gruber Auf diesen Beitrag antworten »

Zumindest steht dein Gleichungssystem im Widerspruch zu der Aussage, dass es mehrere Lösungen haben soll, wie oben bereits festgestellt wurde.
ModuloMelusine Auf diesen Beitrag antworten »

Ich habe jetzt vom Prof die Antwort, dass sich die zwei folgenden Gleichungen ergeben sollten:



Damit ergeben sich tatsächlich zwei Lösungen, nämlich diese hier:

und .

Buchstaben: G wurde zu E und I wurde zu M.
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von ModuloMelusine
Buchstaben: G wurde zu E und I wurde zu M.

G wurde zu C !!! Ansonsten müsste ja die erste Gleichung lauten.

Du machst aber ganz schön viele Konzentrationsfehler bei diesem einfachen Zuordnungsproblem, ziemlich verheerend. unglücklich
ModuloMelusine Auf diesen Beitrag antworten »

Zitat:
Original von René Gruber

Du machst aber ganz schön viele Konzentrationsfehler bei diesem einfachen Zuordnungsproblem, ziemlich verheerend. unglücklich


Entschuldigung, dass da nochmal ein Fehler war. Es liegt an dem Latex-Code, den hatte ich einfach nur von oben kopiert und dann eine Zahl drin geändert. Ich hatte nicht gesehen, dass noch eine zweite Zahl geändert werden musste. Ich wollte ja auch nur noch die richtigen Buchstaben ergänzen.

So sollte es jetzt aber hoffentlich richtig sein:

6 a + b =(kongruent) 4 (mod 26)
und
8 a + b =(kongruent) 12 (mod 26)

(G wurde zu E und I wurde zu M)

Nochmal in Latex:


Damit ergeben sich tatsächlich zwei Lösungen, nämlich diese hier:

und .
Neue Frage »
Antworten »



Verwandte Themen

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