Modulare Gleichung lösen

Neue Frage »

Eldar Auf diesen Beitrag antworten »
Modulare Gleichung lösen
Meine Frage:
Wie löse ich die modulare Gleichung nach x?
Zum Beipiel ist für .

Meine Ideen:
Es geht wahrscheinlich in Richtung diskreter Logarithmus.
HAL 9000 Auf diesen Beitrag antworten »

Zunächst substitutiere und löse die lineare Kongruenz .

Das ist Standardwissen: Lösbar ist diese Kongruenz für , und eindeutig ist diese Lösung genau dann, wenn erfüllt ist.

In deinem Beispiel ist das wegen der Fall, die Kongruenz hat die eindeutige Lösung .

Nach Rücksubstitution ist somit zu lösen. Wegen hat Element 2 offenbar Ordnung 8 modulo 255. Zusammen mit bekommt man somit als Lösung , d.h. nicht nur ist Lösung, sondern auch .

P.S.: Mit dem "diskreten Logarithmus" ist das so eine Sache: Den gibt es so richtig nur für eine zyklische Gruppen, d.h., mit existentem Erzeuger (primitven Element). Nun ist aber die multiplikative Gruppe wegen nicht zyklisch, daher kann man auf diese Weise allenfalls die Einzelkongruenzen für einzeln mit diskreten Logarithmen lösen und dann die Ergebnisse via Chinesischem Restsatz wieder zusammenführen.
Eldar Auf diesen Beitrag antworten »

Vielen Dank, das war wirklich sehr hilfreich. Kann ich einen allgemeinen Weg zeigen, dass folgende Teilbarkeit in diesem Zusammenhang gegeben ist:

Nehmen wir eine Binärzahl der Länge mit Einsen, etwa , und , das durch binäres Rotieren erreichbare Minimum ist und das Maximum ist . Die Linksrotationsdistanz ist die erforderliche Anzahl der Linksrotationen vom Minimum zum Maximum, hier im Beispiel , da wir durch nur drei Linksrotationen () des Minimums das Maximum erhalten. Soweit so gut zum Hintergrund.

Meine Hoffnung ist, eine mehr oder weniger handhabbare Formel für die Rotationsdistanz zu finden ?

Denn bekanntermaßen gilt und passend zu unserem Beispiel .

Ich kann mir sehr gut vorstellen, dass das so einfach nicht geht. Kann man denn zumindest eine Bedingung aufstellen, die beide Zahlen und erfüllen müssen, damit die Teilbarkeit gegeben ist: , wie in unserem Beispiel ?
Eldar Auf diesen Beitrag antworten »

Es scheint, ich müsste nachweisen, dass eine Lösung in Form ganzer Zahlen und für folgende diophantische Gleichung existiert:



In unserem Beispiel ist eine Lösung:
URL Auf diesen Beitrag antworten »

Mir ist jetzt nicht klar, was du eigentlich zeigen willst. verwirrt
Ist A eine Binärzahl der Länge L und wendet man darauf die r-fache Linksrotation an, dann bekommt man die Zahl B für die gilt.
Das kann man anhand der Summendarstellung nachrechnen. Man muss sich also keine Gedanken über die Lösbarkeit obiger Kongruenz machen. Zumindest verstehe ich deinen letzten Beitrag so, als würdest du das tun.

Oder willst du bei bekanntem A und B das r bestimmen? So verstehe ich deinen vorletzten Beitrag.
Eldar Auf diesen Beitrag antworten »

Vielen Dank für den Hinweis! Korrekt - ich würde sehr gern für zwei gegebene (binär dargestellte) Zahlen und der Länge und mit einem Hamming-Gewicht (also beide Zahlen haben Einsen) folgendes untersuchen:

Sei die r-fache Linksrotation von , was müssen erfüllen, damit die Teilbarkeit gilt: .

Es scheint so, dass diese Teilbarkeit stets gegeben ist, wenn die durch Rotation minimal mögliche Binärzahl (etwa 91 für L=8, N=5) und die maximal mögliche Binärzahl (gem. Beispiel 218) ist. Angenommen das stimmt, dass die Teilbarkeit stets gegeben ist, wenn das Minimum und das Maximum (und damit die Rotationsdistanz zwischen Minimum und Maximum) ist, kann man diese Teilbarkeit beweisen? Das wäre absolut klasse.

Meine Idee wäre ein Beweis anhand der diophantischen Gleichung, für die es eine Lösung (zwei natürliche Zahlen a und b) geben muss:
beziehungsweise:


Der Hintergrund sind periodische Sequenzen. In unserem Beispiel ist es die Sequenz:

die sich durch folgende Funktion ergibt:


Vielen Dank noch mal für die Hilfe. Ich weiß nicht so recht, wie ich den Teilbarkeitsnachweis angehen kann.
 
 
Eldar Auf diesen Beitrag antworten »

Kurzer Nachtrag zur Sequenz : Ein Glied dieser Folge können wir mittels der Funktion berechnen, wobei die in der binären Zahl mit Eins belegten Positionen sind (Indizierung ist Null-basiert). Nun können wir das kleinste Glied, die wie folgt berechnen:
. Hierbei ist . Analog berechnen wir das größte Glied via .
Aber das Ganze nur zum Hintergrund, zur Motivation des Ganzen.
URL Auf diesen Beitrag antworten »

Für den einfachsten Fall L=2, N=1 liefert dein f die Collatz-Folge. Deswegen bin ich skeptisch, dass deine allgemeinen Überlegungen Brauchbares liefern werden.

Unter den gemachten Voraussetzungen an hängt die Gültigkeit von überhaupt nicht mehr vom Aussehen von ab. Von daher scheint es die falsche Frage zu sein, welche Voraussetzungen erfüllen müssen.

Wie auch immer, diese Teilbarkeit kann nie gelten, wenn L und das Produkt Nr gerade sind. So viel zu deiner Vermutung mit maximaler und minimaler Binärzahl.
Tatsächlich muss gelten, damit ist.
Eldar Auf diesen Beitrag antworten »

Vielen Dank!

Mir geht es nur darum zu schauen, wie man derartige Teilbarkeiten untersuchen kann.
Wahrscheinlich ist eine (von mehreren) Voraussetzung für diese Teilbarkeit. Wenn sich diese Teilbarkeit nicht nachweisen lässt, dann ist das auch eine Erkenntnis.
URL Auf diesen Beitrag antworten »

ist gleichbedeutend damit, dass , d.h. und sind zueinander invers.
Wenn also fest ist, dann kannst du entweder oder aus den invertierbaren Elementen (Eulersche Phi-Funktion) wählen, und dann gibt es genau ein passendes oder , so dass .

Wenn du also zwei Binärzahlen der Länge hast und wissen willst, ob dafür gilt, bestimmst du . Ist ist die Sache erledigt. Anderfalls bestimmst du das eindeutige mit und schaust dann, ob durch r-fache Linksrotation aus entsteht.
Eldar Auf diesen Beitrag antworten »

genial - besten Dank! Das probiere ich aus und versuche es irgendwie allgemein zu formulieren.
Neue Frage »
Antworten »



Verwandte Themen

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