imported>Nomen4Omen: /* Bemerkungen */ einfacher

2019-07-05T16:08:48Z

Bemerkungen: einfacher

Neue Seite

Der '''Satz von Carmichael''' (nach [[Robert Daniel Carmichael]], [[1910]]) ist eine zahlentheoretische Aussage über eine spezielle Klasse von einfach zu programmierenden [[Zufallszahlengenerator]]en und liefert Kriterien, die dabei helfen, Generatoren von möglichst guter Qualität zu wählen.

== Aussage des Satzes ==
Sei eine [[natürliche Zahl]] <math>m</math> vorgegeben (der sog. Modul).
Zu jeder [[ganze Zahl|ganzen Zahl]] <math>a</math> als Faktor und jeder ganzen Zahl <math>y_0</math> im Bereich von 0 bis <math>m\!-\!1</math> (einschließlich) als Startwert (oder Saat) kann man den [[multiplikativer Kongruenzgenerator|multiplikativen Kongruenzgenerator]] <math>y_{i+1} \equiv (a y_i)\ \bmod\ m</math> definieren.
Die Kombination von <math>a</math> und <math>y_0</math> führt zumindest dann zu einer maximalen [[Periodizität|Periodenlänge]] <math>\lambda(m)</math> unter den multiplikativen Kongruenzgeneratoren mit demselben Modul <math>m</math>, wenn

#<math>y_0</math> zu <math>m</math> [[teilerfremd]] ist, d. h. <math>\mathrm{ggT}(y_0, m) = 1</math>, und
#<math>a</math> »primitives Element« modulo <math>m</math> ist.
(Dabei sei eine Zahl <math>a</math> als primitives Element modulo <math>m</math> bezeichnet, wenn der kleinste positive Exponent <math>e</math>, für den <math>a^e\equiv 1\pmod m</math> gilt, maximal ist.
Ist darüber hinaus die [[prime Restklassengruppe]] <math>(\mathbb{Z} /m\mathbb{Z})^\times</math> [[zyklische Gruppe|zyklisch]], dann gibt es [[Primitivwurzel]]n modulo <math>m</math>, und ein »primitives Element« ist eine Primitivwurzel.)<br />Die Funktion <math>\lambda(m)</math> wird [[Carmichael-Funktion]] genannt. Formeln zu ihrer Berechnung und weitere Eigenschaften finden sich im dortigen Artikel.

== Beispiele ==
* Zum Modul <math>m=10</math> sind demnach 1, 3, 7 und 9 geeignete Startwerte <math>y_0</math>, während 3 und 7 geeignete Faktoren <math>a</math> sind. In der Tat liefert etwa <math>a=3</math>, <math>y_0=9</math> die Folge <math>9, 7, 1, 3, 9, 7, 1, 3, \ldots</math> mit der Periodenlänge vier – mehr ist im Fall <math>m=10</math> nicht möglich.
* Zu <math>m=64</math> sind etwa <math>a=5</math> und <math>y_0=11</math> geeignete Werte. Die erzeugte Folge <math>11, 55, 19, 31, 27, 7, 35, 47, 43, 23, 51, 63, 59, 39, 3, 15, 11, \ldots</math> hat Periodenlänge 16 und erweckt bereits einen »leichten Eindruck von scheinbar zufälliger Unregelmäßigkeit«.

== Bemerkungen ==
* Die im Satz genannten Kriterien sind hinreichend; das zweite ist auch notwendig, nicht jedoch das erste. Beispielsweise liefert die Wahl <math>m=10</math>, <math>a=3</math>, <math> y_0=2</math> die Folge <math>2, 6, 8, 4, 2, 6, 8, 4, \ldots</math> der Periodenlänge vier, obwohl <math>y_0</math> nicht teilerfremd zu <math>m</math> ist.
* In der computertechnischen Anwendung ist <math>m</math> meist eine nicht zu kleine Zweierpotenz; dann ist <math>a</math> primitiv genau dann, wenn <math>a\equiv 3\pmod 8</math> oder <math>a\equiv 5\pmod 8</math> gilt. Und es gilt für alle Potenzen mit geradem Exponenten <math>a^e \equiv 1\pmod 8</math>.

== Literatur ==

* [[Robert Daniel Carmichael]]. In: ''Bulletin of the American Mathematical Society''. Nr. 16, 1910, S. 232–238.
* [[Donald E. Knuth]]: ''The Art of Computer Programming'', Bd. 2. Addison-Wesley, Reading, Mass. (USA) 1969, ISBN 0-201-03822-6.

[[Kategorie:Satz (Mathematik)|Carmichael]]

[[eo:Teoremo de Carmichael]]

Satz von Carmichael - Versionsgeschichte

imported>Nomen4Omen: /* Bemerkungen */ einfacher