Kongruenz

Neue Frage »

Tobias Auf diesen Beitrag antworten »
Kongruenz
Hallo,

gibt es eine Möglichkeit, die folgende Kongruenz zu vereinfachen? Gesucht sind die Lösungen für x. c und a sind positive Konstanten.



Solange c*x kleiner als 2^32 ist, sind die Lösungen über die Primfaktorzerlegung von a herleitbar. Im Fall, dass c große Konstante ist hab ich Probleme, denn dann muss c*x vorher modulo 2^32 reduziert werden.
papahuhn Auf diesen Beitrag antworten »

Deine Schreibweise ist mir nicht ganz klar. Gehts um modulo 2^32 oder modulo a?
Tobias Auf diesen Beitrag antworten »

Das erste modulo ist eine Reduktion (d.h. das Ergebnis ist der Rest der Division durch 2^32). Das zweite Modulo besagt, welche Kongruenzrelation gemeint ist.

Ich kann es auch so schreiben:



und



Oder noch besser:

papahuhn Auf diesen Beitrag antworten »

Aha, Informatiker-Notation. smile
Also, ich habe keine Lösung, aber ich bewundere das Problem. Big Laugh
Tobias Auf diesen Beitrag antworten »

Wie sähe denn eine adäquate Mathematiker-Notation aus? verwirrt
papahuhn Auf diesen Beitrag antworten »

Die Mathematiker-Notation lässt einem mehr Spielraum. Es ist , aber du brauchst .

Chinesischer Restsatz hilft auch nicht weiter, glaube ich. Aber ich bin da nicht wirklich drin bewandert, wie du weißt.

Ist das eigentlich ein theoretisches oder praktisches Problem (mit konkreten Konstanten)? Es würde ja reichen, vorher zu reduzieren, und die Reduktion mal zu nehmen.
 
 
Tobias Auf diesen Beitrag antworten »

Das Problem ergibt sich daraus, dass man auf einer 32Bit CPU sehr häufig nur die unteren 32Bit des Multiplikationsergebnisses weiterverwendet und die Überläufe nicht berücksichtigt.

Das allgemeine Problem lautet:

Für welche x ist a ein Teiler von c*x bei gegebenen a und c.

Auf einer CPU wird es durch den Überlauf komplizierter:

Für welche x ist a ein Teiler der unteren 32Bit von a*x.
Neue Frage »
Antworten »



Verwandte Themen

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