Max hat einen Ausflug nach Kalkutta gemacht. Ein bisschen Nachtleben, ein Bier, Musik, das braucht er manchmal. So hat er in einer Disco Lila kennengelernt. Sie ist ein bisschen jünger als er, hilft tagsüber in der Firma ihres Vaters und mag ebenso Musik.
Max Hi, Lila, was machst Du sonst so, außer im Geschäft zu helfen?
Lila Max, Du glaubst es nicht, ich programmiere gern und liebe Zahlen. Doch im Augenblick ist mein PC total belegt. Ich nehme am GIMPS-Projekt teil. Vielleicht finde ich die nächste größte Primzahl.
Max Wie geht das?
Lila Was Primzahlen sind, das weißt Du?
Max Klar!
Elementarer Primzahltest
Lila Die sind sehr wichtig. Wir in Indien lieben Zahlen und Primzahlen über Alles. Normalerweise gehst Du eine Zahl nach der anderen durch und testest sie auf ihre Teilbarkeit durch alle Primzahlen. Das geht so: Wenn x eine Zahl ist, dann testest Du, ob
diese Zahl teilen.
Max I know.
Lila Das braucht aber entschieden zu lange. Man hat schon viele Primzahlen gefunden, aber bei den großen Primzahlen versagt das Verfahren, jedenfalls mit normalen PCs. Es gibt sehr viele Primzahlen, man konnte ihre Verteilung gut abschätzen, ja, kommst Du nicht aus Deutschland? Gauß hat das als erster gemacht.
Primzahlverteilung
Max Gauß, yes, I know him.
Lila Haha. Jedenfalls hat Gauß zuerst abgeschätzt, dass die Anzahl der Primzahlen die kleiner als die Zahl x sind, für sehr große x ungefähr wie die Funktion
verläuft. Inzwischen gibt es genauere Schätzungen, nämlich, dass sich wie die Eulerian logarithmic integral function verhält. It's a crackjaw! Die Li-Funktion geht so:
Max Hm, hast Du mal ein Bild?
Lila Okay, hier, ich hab mein Handy dabei, hier sind die beiden Näherungen für die Li-Funktion passt sehr genau und überdeckt Ich habe logarithmische Skalen genommen, weil die Werte so groß werden.
Max O, Mann, die Kurven wachsen ja mächtig. So viele Primzahlen gibt es?
Mersenne-Zahlen
Lila Yes! Leider führt dieses Suchen nicht zum Erfolg. Doch dann hat Mersenne herausgefunden, dass man einige Primzahlen konstruieren kann: Einige der Zweierpotenzen minus 1 sind Primzahlen. Du nimmst eine Primzahl p, berechnest die Zweierpotenz 2p minus 1, diese Zahl heißt Mersenne-Zahl and it has a nice notation:
Max Hey! Mach doch mal ein Beispiel!
Lila Die kleinsten Zahlen dieser Art sind
Doch nicht alle diese Zahlen sind Primzahlen. 63 ist keine Primzahl, sie ist durch 3 teilbar. Alle von den Mersenne-Zahlen, die prim sind, heißen Mersenne primes.
Max Gehst Du dann alle p durch und testest, ob Mp Primzahl ist?
Lucas-Lehmer-Test
Lila Nein, das dauert auch zu lange. Da gibt es den Lucas-Lehmer-Test, der geht einfacher. Zunächst musst Du mit einer Primzahl p starten. Du berechnest
und außerdem eine rekursive Folge.
Max Rekursive Folgen kenne ich, voll aufwendig zu berechnen!
Lila Kennst Du auch Restklassen?
Max Klar, die braucht man fürs RSA-Verfahren!
Lila Hey! Das hört sich gut an. Dann zeige ich Dir das, Du kannst das bestimmt verstehen: Also, dann geht es weiter mit
Max Gut.
Dann berechnest Du für Deine Primzahl p und Deine Mersenne-Zahl Mp jetzt
und immer so weiter
bis S(p-1) – für das p, mit dem Du gestartest bist.
Max Okay.
Lila Wenn S(p-1) durch Mp teilbar ist, oder bei der Division durch Mp den Rest 0 lässt:
dann ist Mp eine Mersenne-Primzahl.
Max Okay, hast Du schon eine gefunden?
Lila Ich habe das Programm von GIMPS getestet, die letzte gefundene Mesenne-Primzahl M77.232.917 habe ich bestätigt, da habe ich im Januar angefangen zu testen und im Sommer war mein PC damit durch. Jetzt teste ich die erste Zahl, die ich von GIMPS bekommen habe. Drück mir mal die Daumen!
Max Mach' ich.
Lila Wenn meine Primzahl keine Mersenne-Primzahl liefert, melde ich das Ergebnis auch. Mein Test ist nicht umsonst. Ich finde es einfach toll, wie der Rechner rechnet und rechnet und am Ende was Sinnvolles rauskommt.
Max Gut, könnte ich auch mitmachen? Zeigst Du’s mir mal?
Lila Klar, heute Abend ist erst mal Musik angesagt.
***
Übungsaufgabe
Prüfe mit dem Lucas-Lehmer-Test, ob M7 prim ist.
Lösung
M7 ist prim.
Anmerkung
Am 21. Dezember 2018 wurde die nächste Mersenne Primzahl im GIMPS-Projket von Patrick Laroche entdeckt: 282 589 933 - 1.