linearer Kongruenzgenerator "rückwärts" rechnen?

Neue Frage »

simstar Auf diesen Beitrag antworten »
linearer Kongruenzgenerator "rückwärts" rechnen?
Meine Frage:
ich muss im Rahmen der Vorlesung "Simulation" mit linearen Kongruenzgeneratoren rechnen können... soweit kein Problem. Jetzt ist meine Frage, ob und vorallem wie ich "rückwärts" von einer Zahlenreihe auf die Werte für den Generator komme?

x(n+1) = (a*x(n)+c) mod m

Die Werte für x(n) und x(n+1) sind also gegeben und ich muss a, c, m ermitteln...
Bis jetzt bin ich jedes mal durch "ausprobieren" auf dir richtige Lösung gekommen. Allerdings war mir m bereits bekannt. Gibt es einen Algorithmus dazu?

bin froh um jede Hilfe!!!
Vielen Dank.

Meine Ideen:
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von simstar
Die Werte für x(n) und x(n+1) sind also gegeben und ich muss a, c, m ermitteln

Nur zwei Werte gegeben zur Ermittlung von drei Unbekannten, wie soll das eindeutig gehen? Sind nicht doch noch mehr Werte gegeben, wenigstens noch x(n+2) ? verwirrt
simstar Auf diesen Beitrag antworten »

also ich habe auch x(n+2) usw.
es ist die ganze "zahlenreihe" die der linearer Kongruenzgenerator normalerweise erzeugt gegeben.
jetzt soll ich rückwärts die parameter des LKG ermitteln...

ich habe schon versucht dieverse gleichungssysteme aufzustellen. mir macht der/das/die modulo allerdings probleme.

vll kennt ja jemand einen kniff oder einen algorithmus um das zu lösen?!

vielen dank schonmal.
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von simstar
also ich habe auch x(n+2) usw.

Und warum sagst du das nicht gleich, und formulierst stattdessen "gegeben x(n) und x(n+1)" ? unglücklich

Jedenfalls ist nun



,

durch Differenzbildung folgt




und daraus dann

,

d.h. ist ein Teiler von für alle , insbesondere also auch ein Teiler von



wobei eine beliebige Indexmenge durchläuft. Außerdem ist natürlich auch noch größer als alle . Aus den beiden Infos zusammen kriegt man hoffentlich heraus. Hat man einmal , dann kriegt man über (*) o.ä. auch heraus, und ist anschließend eh kein Problem mehr.
Mystic Auf diesen Beitrag antworten »

So einfallsreich der von René beschrieben Weg zur Bestimmung eines möglichen m auch sein mag, ich glaube nicht, dass es in der Intention des Aufgabenstellers lag, auch noch das m zu bestimmen, sondern dass m einfach fix vorgegeben ist, auch wenn das der Threadersteller irgendwie nicht mitbekommen hat... So ist z.B.



(oder eine andere Potenz von 2) eine sehr häufige Wahl, da damit auf Computern der entsprechenden Wortlänge eine Reduktion mod m sehr rasch möglich ist...
René Gruber Auf diesen Beitrag antworten »

In der Praxis, ja. Aber wer weiß, was sich der Prof so einfallen lässt. Big Laugh
 
 
Neue Frage »
Antworten »



Verwandte Themen

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