www.wikidata.de-de.nina.az

Satz von Carmichael Der nach Robert Daniel Carmichael 1910 ist eine zahlentheoretische Aussage über eine spezielle Klass

Satz von Carmichael

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

Aussage des Satzes Bearbeiten

Sei eine natürliche Zahl vorgegeben (der sog. Modul). Zu jeder ganzen Zahl als Faktor und jeder ganzen Zahl im Bereich von 0 bis (einschließlich) als Startwert (oder Saat) kann man den multiplikativen Kongruenzgenerator definieren. Die Kombination von und führt zumindest dann zu einer maximalen Periodenlänge unter den multiplikativen Kongruenzgeneratoren mit demselben Modul , wenn

  1. zu teilerfremd ist, d. h. , und
  2. »primitives Element« modulo ist.

(Dabei sei eine Zahl als primitives Element modulo bezeichnet, wenn der kleinste positive Exponent , für den gilt, maximal ist. Ist darüber hinaus die prime Restklassengruppe zyklisch, dann gibt es Primitivwurzeln modulo , und ein »primitives Element« ist eine Primitivwurzel.)
Die Funktion wird Carmichael-Funktion genannt. Formeln zu ihrer Berechnung und weitere Eigenschaften finden sich im dortigen Artikel.

Beispiele Bearbeiten

  • Zum Modul sind demnach 1, 3, 7 und 9 geeignete Startwerte , während 3 und 7 geeignete Faktoren sind. In der Tat liefert etwa , die Folge mit der Periodenlänge vier – mehr ist im Fall nicht möglich.
  • Zu sind etwa und geeignete Werte. Die erzeugte Folge hat Periodenlänge 16 und erweckt bereits einen »leichten Eindruck von scheinbar zufälliger Unregelmäßigkeit«.

Bemerkungen Bearbeiten

  • Die im Satz genannten Kriterien sind hinreichend; das zweite ist auch notwendig, nicht jedoch das erste. Beispielsweise liefert die Wahl , , die Folge der Periodenlänge vier, obwohl nicht teilerfremd zu ist.
  • In der computertechnischen Anwendung ist meist eine nicht zu kleine Zweierpotenz; dann ist primitiv genau dann, wenn oder gilt. Und es gilt für alle Potenzen mit geradem Exponenten .

Literatur Bearbeiten

  • 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Satz von Carmichael nach Robert Daniel Carmichael 1910 ist eine zahlentheoretische Aussage uber eine spezielle Klasse von einfach zu programmierenden Zufallszahlengeneratoren und liefert Kriterien die dabei helfen Generatoren von moglichst guter Qualitat zu wahlen Inhaltsverzeichnis 1 Aussage des Satzes 2 Beispiele 3 Bemerkungen 4 LiteraturAussage des Satzes BearbeitenSei eine naturliche Zahl m displaystyle m nbsp vorgegeben der sog Modul Zu jeder ganzen Zahl a displaystyle a nbsp als Faktor und jeder ganzen Zahl y 0 displaystyle y 0 nbsp im Bereich von 0 bis m 1 displaystyle m 1 nbsp einschliesslich als Startwert oder Saat kann man den multiplikativen Kongruenzgenerator y i 1 a y i mod m displaystyle y i 1 equiv ay i bmod m nbsp definieren Die Kombination von a displaystyle a nbsp und y 0 displaystyle y 0 nbsp fuhrt zumindest dann zu einer maximalen Periodenlange l m displaystyle lambda m nbsp unter den multiplikativen Kongruenzgeneratoren mit demselben Modul m displaystyle m nbsp wenn y 0 displaystyle y 0 nbsp zu m displaystyle m nbsp teilerfremd ist d h g g T y 0 m 1 displaystyle mathrm ggT y 0 m 1 nbsp und a displaystyle a nbsp primitives Element modulo m displaystyle m nbsp ist Dabei sei eine Zahl a displaystyle a nbsp als primitives Element modulo m displaystyle m nbsp bezeichnet wenn der kleinste positive Exponent e displaystyle e nbsp fur den a e 1 mod m displaystyle a e equiv 1 pmod m nbsp gilt maximal ist Ist daruber hinaus die prime Restklassengruppe Z m Z displaystyle mathbb Z m mathbb Z times nbsp zyklisch dann gibt es Primitivwurzeln modulo m displaystyle m nbsp und ein primitives Element ist eine Primitivwurzel Die Funktion l m displaystyle lambda m nbsp wird Carmichael Funktion genannt Formeln zu ihrer Berechnung und weitere Eigenschaften finden sich im dortigen Artikel Beispiele BearbeitenZum Modul m 10 displaystyle m 10 nbsp sind demnach 1 3 7 und 9 geeignete Startwerte y 0 displaystyle y 0 nbsp wahrend 3 und 7 geeignete Faktoren a displaystyle a nbsp sind In der Tat liefert etwa a 3 displaystyle a 3 nbsp y 0 9 displaystyle y 0 9 nbsp die Folge 9 7 1 3 9 7 1 3 displaystyle 9 7 1 3 9 7 1 3 ldots nbsp mit der Periodenlange vier mehr ist im Fall m 10 displaystyle m 10 nbsp nicht moglich Zu m 64 displaystyle m 64 nbsp sind etwa a 5 displaystyle a 5 nbsp und y 0 11 displaystyle y 0 11 nbsp geeignete Werte Die erzeugte Folge 11 55 19 31 27 7 35 47 43 23 51 63 59 39 3 15 11 displaystyle 11 55 19 31 27 7 35 47 43 23 51 63 59 39 3 15 11 ldots nbsp hat Periodenlange 16 und erweckt bereits einen leichten Eindruck von scheinbar zufalliger Unregelmassigkeit Bemerkungen BearbeitenDie im Satz genannten Kriterien sind hinreichend das zweite ist auch notwendig nicht jedoch das erste Beispielsweise liefert die Wahl m 10 displaystyle m 10 nbsp a 3 displaystyle a 3 nbsp y 0 2 displaystyle y 0 2 nbsp die Folge 2 6 8 4 2 6 8 4 displaystyle 2 6 8 4 2 6 8 4 ldots nbsp der Periodenlange vier obwohl y 0 displaystyle y 0 nbsp nicht teilerfremd zu m displaystyle m nbsp ist In der computertechnischen Anwendung ist m displaystyle m nbsp meist eine nicht zu kleine Zweierpotenz dann ist a displaystyle a nbsp primitiv genau dann wenn a 3 mod 8 displaystyle a equiv 3 pmod 8 nbsp oder a 5 mod 8 displaystyle a equiv 5 pmod 8 nbsp gilt Und es gilt fur alle Potenzen mit geradem Exponenten a e 1 mod 8 displaystyle a e equiv 1 pmod 8 nbsp Literatur BearbeitenRobert 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 Abgerufen von https de wikipedia org w index php title Satz von Carmichael amp oldid 190157112