July 26, 2021

Ist diese Zahl eine Primzahl? Dafür gibt es ein Spiel.

Der griechische Mathematiker Euklid hat wahrscheinlich um 300 v. Chr. bewiesen, dass es unendlich viele Primzahlen gibt. Aber es war der britische Mathematiker Christian Lawson-Perfect, der in jüngerer Zeit das Computerspiel „Is this prime?“ entwickelt hat.

Das vor fünf Jahren gestartete Spiel übertraf am 16. Juli drei Millionen Versuche – oder genauer gesagt, es erreichte 2.999.999 –, nachdem ein Hacker-News-Post einen Anstieg von etwa 100.000 Versuchen generiert hatte.

Ziel des Spiels ist es, in 60 Sekunden so viele Zahlen wie möglich in „prime“ oder „not prime“ zu sortieren (wie Lawson-Perfect es ursprünglich in The Aperiodical beschrieben hat, einem Mathematik-Blog, dessen Gründer und Herausgeber er ist).

Eine Primzahl ist eine ganze Zahl mit genau zwei Teilern, 1 und sich selbst.

„Es ist sehr einfach, aber ärgerlich schwierig“, sagt Lawson-Perfect, der in der E-Learning-Einheit der School of Mathematics and Statistics der Newcastle University arbeitet. Er hat das Spiel in seiner Freizeit entwickelt, aber es hat sich im Job als nützlich erwiesen: Lawson-Perfect schreibt E-Assessment-Software (Systeme, die das Lernen auswerten). „Das System, das ich erstelle, ist so konzipiert, dass es zufällig eine mathematische Frage generiert und eine Antwort vom Schüler nimmt, die es automatisch markiert und Feedback gibt“, sagt er. „Man könnte das Primes-Spiel als eine Art Bewertung betrachten“ – er hat es bei Informationsveranstaltungen in Schulen verwendet.

Er machte das Spiel mit Tastaturkürzeln etwas einfacher – die Tasten y und n klicken auf die entsprechenden Ja-Nein-Schaltflächen auf dem Bildschirm –, um die Mausbewegungszeit zu sparen.

Probieren Sie es aus:

Algorithmen zur Primzahlprüfung

Primzahlen haben einen praktischen Nutzen beim Rechnen – beispielsweise bei fehlerkorrigierenden Codes und bei der Verschlüsselung. Aber während die Primfaktorzerlegung schwierig ist (daher ihr Wert für die Verschlüsselung), ist die Primzahlprüfung einfacher, wenn auch schwierig. Der mit der Fields-Medaille ausgezeichnete deutsche Mathematiker Alexander Grothendieck verwechselte berüchtigterweise 57 mit Primzahl (die „Grothendieck-Primzahl“). Als Lawson-Perfect Daten aus dem Spiel analysierte, stellte er fest, dass verschiedene Zahlen eine gewisse „Grothendieckyness“ aufwiesen. Die Zahl, die am häufigsten mit einer Primzahl verwechselt wurde, war 51, gefolgt von 57, 87, 91, 119 und 133 – Lawson-Perfects Erzfeind (er entwickelte auch einen praktischen Dienst zur Überprüfung der Primzahl: https://isthisprime.com/2).

Der minimalistischste Algorithmus zum Prüfen der Primzahl einer Zahl ist die Probedivision – dividiere die Zahl durch jede Zahl bis zur Quadratwurzel (das Produkt zweier Zahlen größer als die Quadratwurzel wäre größer als die fragliche Zahl).

Diese naive Methode ist jedoch nicht sehr effizient, und auch einige andere Techniken wurden im Laufe der Jahrhunderte nicht entwickelt – wie der deutsche Mathematiker Carl Friedrich Gauß 1801 feststellte, dass sie „selbst für den unermüdlichsten Taschenrechner unerträgliche Arbeit erfordern“.

Der für das Spiel kodierte Algorithmus von Lawson-Perfect heißt Miller-Rabin-Primalitätstest (der auf einer sehr effizienten, aber nicht eisernen Methode aus dem 17. Jahrhundert aufbaut, dem „kleinen Theorem von Fermat“). Der Miller-Rabin-Test funktioniert überraschend gut. Was Lawson-Perfect betrifft, ist es „im Grunde genommen Magie“ – „Ich verstehe nicht wirklich, wie es funktioniert, aber ich bin zuversichtlich, dass ich es könnte, wenn ich die Zeit aufwenden würde, es genauer zu betrachten“, sagt er.

Da der Test Zufall verwendet, liefert er ein wahrscheinlichkeitstheoretisches Ergebnis. Was bedeutet, dass manchmal der Test liegt. „Es besteht die Möglichkeit, einen Betrüger aufzudecken, eine zusammengesetzte Zahl, die versucht, als Primzahl durchzugehen“, sagt Carl Pomerance, Mathematiker am Dartmouth College und Mitautor des Buches Primzahlen: Eine rechnerische Perspektive. Die Wahrscheinlichkeit, dass ein Betrüger den cleveren Prüfmechanismus des Algorithmus durchbricht, ist jedoch vielleicht eins zu einer Billion, sodass der Test „ziemlich sicher“ ist.

Aber was clevere Algorithmen zur Primzahlprüfung angeht, ist der Miller-Rabin-Test „die Spitze des Eisbergs“, sagt Pomerance. Vor 19 Jahren kündigten drei Informatiker – Manindra Agrawal, Neeraj Kayal und Nitin Saxena, alle vom Indian Institute of Technology Kanpur – den AKS-Primalitätstest (wieder aufbauend auf Fermats Methode) an, der schließlich einen Test zum eindeutigen Nachweis lieferte dass eine Zahl eine Primzahl ist, ohne Randomisierung und (zumindest theoretisch) mit beeindruckender Geschwindigkeit. Leider bedeutet schnell in der Theorie nicht immer schnell im wirklichen Leben, daher ist der AKS-Test für praktische Zwecke nicht nützlich.

Der inoffizielle Weltrekord

Aber die Praktikabilität ist nicht immer der Punkt. Gelegentlich erhält Lawson-Perfect E-Mails von Leuten, die ihre Highscores im Spiel teilen möchten. Vor kurzem hat ein Spieler 60 Primzahlen in 60 Sekunden gemeldet, aber der Rekord ist wahrscheinlicher 127. (Lawson-Perfect verfolgt keine Highscores; er weiß, dass es einige Betrüger gibt, mit computergestützten Versuchen, die Spitzen in den Daten erzeugen.)

Die Punktzahl 127 wurde von Ravi Fernando erreicht, einem Mathematik-Studenten an der University of California, Berkeley, der das Ergebnis im Juli 2020 veröffentlichte. Es ist immer noch seine persönliche Bestleistung und seiner Meinung nach der „inoffizielle Weltrekord“.

Seit letztem Sommer hat Fernando das Spiel nicht viel mit den Standardeinstellungen gespielt, aber er hat es mit benutzerdefinierten Einstellungen versucht, für größere Zahlen ausgewählt und längere Zeitlimits zugelassen – er erzielte 240 mit einem Fünf-Minuten-Limit. „Was viel Rätselraten erforderte, weil die Zahlen in den hohen vierstelligen Bereich gelangten und ich mir immer nur Primzahlen bis zu den niedrigen 3.000ern auswendig gelernt habe“, sagt er. “Ich nehme an, einige würden argumentieren, dass selbst das übertrieben ist.”

Fernandos Forschung befasst sich mit der algebraischen Geometrie, die bis zu einem gewissen Grad Primzahlen beinhaltet. Aber, sagt er, „meine Forschung hat mehr damit zu tun, warum ich mit dem Spiel aufgehört habe, als warum ich angefangen habe“ (er begann 2014 mit seiner Promotion). Außerdem rechnet er damit, dass 127 sehr schwer zu schlagen wären. Und, sagt er, “es fühlt sich einfach richtig an, bei einem Primzahlen-Rekord anzuhalten.”