Auf diesem Streifzug lernen Sie einige erstaunliche Phänomene im Reich der Primzahlen kennen. Früher war das reine Theorie ohne praktische Anwendungen. Aber im Zeitalter der Computer-Kryptografie (z. B. für die HTTPS-Verschlüsselung bei der Übertragung dieser Webseite vom Server auf Ihren Computer) sind die Primzahlen äußerst praktisch geworden.
1. Ein geheimnisvoller zellulärer Automat
Wir beginnen diesen Streifzug mit einer kleinen Spielerei.
In Zellhausen gibt es eine lange Häuserreihe. Die Bewohnerinnen des mittleren Hauses möchten sich optisch vom Einheitsweiß abheben und haben ihr Haus blau gestrichen. Um ein chaotisches Gesamtbild zu verhindern, hat das Bauamt darauf die folgende Vorschrift erlassen: „Einzelne Hausanstriche sind untersagt. Es dürfen aber alle Häuser gleichzeitig neu gestrichen werden, wobei die Häuser weiß gestrichen werden müssen, deren beide Nachbarhäuser die gleiche Farbe haben, alle andern blau.“
Nach der nächsten Streichaktion sieht die Straße so aus:
Diese Straße ist ein einfaches Beispiel eines zellulären Automaten. Der Automat hat eine Menge von Zellen und eine Übergangsfunktion, die jeder Zelle (hier: die einzelnen Häuser) einen neuen Zustand (hier: weiß oder blau) in Abhängigkeit einer Umgebung (hier: die Zelle selbst und ihre beiden Nachbarn) zuordnet.
Im Beispiel müssen wir für die 2^3 möglichen Werte einer Zelle und ihrer beiden Nachbarn den neuen Wert angeben. Dafür verwenden wir im folgenden Beispiel die Notation aus dem Buch „A New Kind of Science“ von Stephen Wolfram uns schreiben 0 für weiß und 1 für blau.
Jede der acht Regeln kann rechts eine Null oder eins haben. Es gibt also für diese Automaten mit zwei Zellzuständen 2^{2^3} mögliche Regelvarianten. Nicht alle Regeln ergeben so klare Strukturen. Hier ein chaotisches Beispiel, bei dem die Mittelzelle eine statistisch saubere Zufallsfolge durchläuft (Vertikallinie):
Hier sind die Regeln für einen merkwürdigen zellulären Automaten mit 16 Zellzuständen:
Wenn mehrere Regeln passen, wird die erste verwendet. Würde man im Beispiel die letzte Regel an die erste Stelle setzen, gäbe es nach dem 1. Schritt nur noch Nullen.
Testen Sie diesen Automaten und schauen Sie sich die schrägen schwarzen und weißen Linien genau an!
Finden Sie eine Regel, welche Schräglinien weiß sind und welche schwarz?
Die Lösung erfahren Sie in der Fortsetzung
Fortsetzung: Zwei Primzahlexperten am Fuße eines Weltwunders
