maximale Periodenlänge eines linearen Kongruenzgenerators

17.12.2012, 19:22

deppensido

maximale Periodenlänge eines linearen Kongruenzgenerators

hallo,

bei der Aufgabe im Anhang, soll man ermitteln, ob die Periodenlänge maximal ist.

Meine Lösung bisher:

Meine Antwort lautet nein. Dazu hab ich einen Satz aus der Vorlesung benutzt,
der sagt, dass die Periodenlänge genau dann = m ist, wenn

(i) ggt(b,m) = 1, (ii) p | (a-1) für alle p Prim und p | m, (iii) $\begin{eqnarray*} \phi \end{eqnarray*}$ | (a-1) => $\begin{eqnarray*} \phi \end{eqnarray*}$ | m.

Für die dritte Bedingung habe ich keine Besondere Bedingung für die $\begin{eqnarray*} \phi \end{eqnarray*}$ ,
womit ich $\begin{eqnarray*} \phi = (a-1) * 2 \end{eqnarray*}$ gesetzt habe und dann gilt ja: $\begin{eqnarray*} \phi / m = 0.628 \end{eqnarray*}$

womit $\begin{eqnarray*} \phi \end{eqnarray*}$ nicht m teilt. Damit wäre die dritte Bedingung des Satzes nicht erfüllt und die Periodenlänge nicht maximal.

Ist das so richtig? Ich bin mir nicht sicher, ob ich den oben genannten Satz richtig abgeschrieben habe. Falls $\begin{eqnarray*} \phi \end{eqnarray*}$ z.B. Prim sein muss, dann stimmt das ja nicht mehr.

Grüße

17.12.2012, 23:06

deppensido

Auf diesen Beitrag antworten »

ich habe jetzt nochmal die Bedingung aus Wikipedia geprüft
http://de.wikipedia.org/wiki/Linearer_Ko...iodenl.C3.A4nge
und komme jetzt doch da drauf, dass die Periodenlänge maximal ist.

Welche Antwort ist denn richtig? Jetzt bin ich verwirrt.

Grüße

18.12.2012, 15:12

HAL 9000

Auf diesen Beitrag antworten »

Betrachten wir einfach $\begin{eqnarray*} m=16,a=13,b=1 \end{eqnarray*}$ , dann erfüllt dieser Generator deine Bedingung (iii) nicht (betrachte $\begin{eqnarray*} \phi=3 \end{eqnarray*}$ ), dennoch wird bei Startwert 0 die Folge

0
1
14
7
12
13
10
3
8
9
6
15
4
5
2
11
0

erzeugt, also mit voller Periode 16. Ich hab keine Ahnung, ob die in der Wikipedia angegebenen Kriterien richtig sind - aber deine sind, wie das Beispiel zeigt, auf jeden Fall falsch, zumindest (iii).

18.12.2012, 15:30

deppensido

Auf diesen Beitrag antworten »

erstmal danke für die Antwort.
Ich habe nochmal etwas recherchiert und auch in anderen Quellen, die Bedingungen aus Wikipedia gefunden unter anderem auch von einer anderen Hochschule.
Ich gehe daher mal davon aus, dass ich den Satz zumindest Bedingung (iii) nicht richtig abgeschrieben habe (das ist manchmal kaum lesbar). Ich hab wahrscheinlich das $\begin{eqnarray*} \phi \end{eqnarray*}$ mit einer 4 verwechselt. Dann würde der Satz ja das gleiche Aussagen, wie in Wikipedia steht.

Also dann wäre (iii) 4 | (a-1) => 4 | m.

Um dies jetzt zu zeigen und doch auf eine volle Periode als Antwort zu kommen,

habe ich (a-1) / 4 und 4 / m konkret ausgerechnet. Gibts vielleicht eine einfachere Möglichkeit, wie ich diese Bedingung prüfen kann? In der Klausur kann ich ja keinen Computer benutzen...

Grüße

18.12.2012, 15:33

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von deppensido
Also dann wäre (iii) 4 | (a-1) => 4 | m.

Nein, die in der Wikipedia stehende dritte Bedingung lautet gerade umgekehrt, d.h.

4 | m => 4 | (a-1)

Zitat:

Original von deppensido
Gibts vielleicht eine einfachere Möglichkeit, wie ich diese Bedingung prüfen kann? In der Klausur kann ich ja keinen Computer benutzen...

Es ist doch keine Hürde, bei einem so einfachen Modul wie $\begin{eqnarray*} m=10^{10} = 2^{10}\cdot 5^{10} \end{eqnarray*}$ die Bedingungen zu prüfen:

"ggT(b,m)=1" heißt dann nur, dass b weder durch 2 noch durch 5 teilbar sein darf. Also ungerade und keine 5 am Ende.

"p|m => p|(a-1)" ist hier nur für p=2 und p=5 relevant und bedeutet am Ende, dass (a-1) durch 10 teilbar sein muss, d.h., a muss auf Dezimalziffer 1 enden.

"4|m ==> 4|(a-1)" bedeutet zusätzlich zum vorigen, dass die vorletzte Ziffer von a gerade sein muss.

Alle drei Bedingungen sind schnell überprüft, ohne dass man sich nun totgerechnet hat.

18.12.2012, 15:41

deppensido

Auf diesen Beitrag antworten »

(i) und (ii) hab ich analog zu deinem vorherigen Kommentar und für (iii) hab ich gerade gefunden, dass eine Zahl durch 4 teilbar ist, wenn die letzten beiden Ziffern durch 4 teilbar sind, womit ich das begründet habe.

Ich denke, die Aufgabe ist damit gelöst. Hauptproblem war somit wirklich, dass ich in der Vorlesung nicht richtig abgeschrieben habe.

Ansonsten, danke für die Hilfe!

Grüße

Neue Frage »

Antworten »

maximale Periodenlänge eines linearen Kongruenzgenerators

Verwandte Themen