Satz von Carmichael

Der Satz v​on Carmichael (nach Robert Daniel Carmichael, 1910) i​st eine zahlentheoretische Aussage über e​ine spezielle Klasse v​on einfach z​u programmierenden Zufallszahlengeneratoren u​nd liefert Kriterien, d​ie dabei helfen, Generatoren v​on möglichst g​uter Qualität z​u wählen.

Aussage des Satzes

Sei eine natürliche Zahl ${\displaystyle m}$ vorgegeben (der sog. Modul). Zu jeder ganzen Zahl ${\displaystyle a}$ als Faktor und jeder ganzen Zahl ${\displaystyle y_{0}}$ im Bereich von 0 bis ${\displaystyle m\!-\!1}$ (einschließlich) als Startwert (oder Saat) kann man den multiplikativen Kongruenzgenerator ${\displaystyle y_{i+1}\equiv (ay_{i})\ {\bmod {\ }}m}$ definieren. Die Kombination von ${\displaystyle a}$ und ${\displaystyle y_{0}}$ führt zumindest dann zu einer maximalen Periodenlänge ${\displaystyle \lambda (m)}$ unter den multiplikativen Kongruenzgeneratoren mit demselben Modul ${\displaystyle m}$ , wenn

1. ${\displaystyle y_{0}}$ zu ${\displaystyle m}$ teilerfremd ist, d. h. ${\displaystyle \mathrm {ggT} (y_{0},m)=1}$ , und
2. ${\displaystyle a}$ »primitives Element« modulo ${\displaystyle m}$ ist.

(Dabei sei eine Zahl ${\displaystyle a}$ als primitives Element modulo ${\displaystyle m}$ bezeichnet, wenn der kleinste positive Exponent ${\displaystyle e}$ , für den ${\displaystyle a^{e}\equiv 1{\pmod {m}}}$ gilt, maximal ist. Ist darüber hinaus die prime Restklassengruppe ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}$ zyklisch, dann gibt es Primitivwurzeln modulo ${\displaystyle m}$ , und ein »primitives Element« ist eine Primitivwurzel.)
Die Funktion ${\displaystyle \lambda (m)}$ wird Carmichael-Funktion genannt. Formeln zu ihrer Berechnung und weitere Eigenschaften finden sich im dortigen Artikel.

Beispiele

• Zum Modul ${\displaystyle m=10}$ sind demnach 1, 3, 7 und 9 geeignete Startwerte ${\displaystyle y_{0}}$ , während 3 und 7 geeignete Faktoren ${\displaystyle a}$ sind. In der Tat liefert etwa ${\displaystyle a=3}$ , ${\displaystyle y_{0}=9}$ die Folge ${\displaystyle 9,7,1,3,9,7,1,3,\ldots }$ mit der Periodenlänge vier – mehr ist im Fall ${\displaystyle m=10}$ nicht möglich.
• Zu ${\displaystyle m=64}$ sind etwa ${\displaystyle a=5}$ und ${\displaystyle y_{0}=11}$ geeignete Werte. Die erzeugte Folge ${\displaystyle 11,55,19,31,27,7,35,47,43,23,51,63,59,39,3,15,11,\ldots }$ 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 ${\displaystyle m=10}$ , ${\displaystyle a=3}$ , ${\displaystyle y_{0}=2}$ die Folge ${\displaystyle 2,6,8,4,2,6,8,4,\ldots }$ der Periodenlänge vier, obwohl ${\displaystyle y_{0}}$ nicht teilerfremd zu ${\displaystyle m}$ ist.
• In der computertechnischen Anwendung ist ${\displaystyle m}$ meist eine nicht zu kleine Zweierpotenz; dann ist ${\displaystyle a}$ primitiv genau dann, wenn ${\displaystyle a\equiv 3{\pmod {8}}}$ oder ${\displaystyle a\equiv 5{\pmod {8}}}$ gilt. Und es gilt für alle Potenzen mit geradem Exponenten ${\displaystyle a^{e}\equiv 1{\pmod {8}}}$ .

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.