Periodenlänge - Zufallsgeneratoren

Question

Es soll die Periodenlänge folgender zwei Zufallsgeneratoren bestimmt werden:

1) Multiplikativer Kongruenzgenerator mit: 

z_n+1 = az_n mod m

a = 65533 

m = 2³¹ 

ungerade Startwerte z₀

2) Shift-Register-Generator mit:

xi = (x_i−p +xi_−p+q) mod 2

p = 3

q = 1

Startwort x1, x2, x3 = 0, 0, 1

Mein Ansatz:

1) Gegeben ist der folgende Satz: 

Ist m = 2^b, b ≥ 3 und a mod 8 ∈ {3, 5} so gilt für jeden ungeraden Startwert 1 ≤ z₀ ≤ m−1,
dass die erzeugte Folge die (maximal mögliche) Periode 2^b−2 hat.

Nun gilt sowohl m = 2^b mit b =31 ≥ 3 als auch a=65533 mod 8 ∈ {3, 5}. Der Startwert ist ebenfalls ungerade, allerdings weiß ich nicht ob dieser 1 ≤ z₀ ≤ m−1 ist. Würde dies gelten müsste doch die Periodenlänge gleich 2^31-2 = 2²⁹ sein, oder?

2) Hier habe ich durch kurzes austesten herausgefunden, dass hier alle Werte von 1 bis 7 (in Binärform) generiert werden, und es sich dann wiederholt. D.h. die Periodenlänge müsste eig. 7 betragen, oder? Die Frage ist nur, wie ich dass geschickt zeige, dass genau das passiert.

Vielen lieben Dank

Answer 1

1)

Deine Untersuchung ist doch soweit richtig. Warum kannst du wohl davon ausgehen das der Startwert in besagtem Bereich liegt? Du könntest ja auch zunächst den Startwert Modulo m nehmen.

m ist ja auf jeden Fall eine gerade zahl und irgendeine ungerade zahl modulo einer geraden zahl gibt auf jeden fall wieder eine ungerade zahl.

2)

Die Periodenlänge ist wie du sagst 7. So wie du es gemacht hast langt das als nachweis völlig aus.