Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

III_20_titel_primzahlen

Lila und die Mersenne-Zahlen

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

2,\; 3,\; 5,\; 7,\; 11,\;\dots\;,\;\sqrt{x}

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 \pi(x), die kleiner als die Zahl x sind, für sehr große x ungefähr wie die Funktion

u(x)\;=\;\frac{x}{\ln x}

verläuft. Inzwischen gibt es genauere Schätzungen, nämlich, dass sich \pi(x) wie die Eulerian logarithmic integral function verhält. It's a crackjaw! Die Li-Funktion geht so:

Li(x)\;=\;\int_2^x \frac{\mathrm{dt}}{\ln t}

Max Hm, hast Du mal ein Bild?

Lila Okay, hier, ich hab mein Handy dabei, hier sind die beiden Näherungen für \pi(x), die Li-Funktion passt sehr genau und überdeckt \pi(x). Ich habe logarithmische Skalen genommen, weil die Werte so groß werden.

 

III_20_primzahlen_07
Asymptotische Abschätzung der Primzahlverteilung \pi(x) durch Li und u.


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:

M_p\;=\;2^p\;-\;1

Max Hey! Mach doch mal ein Beispiel!

Lila Die kleinsten Zahlen dieser Art sind

1,\;3,\;7,\;15,\;31,\;63,\;\dots

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

M_p\;=\;2^p\;-\;1

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

S(1)\;=\;4.

Max Gut.

Dann berechnest Du für Deine Primzahl p und Deine Mersenne-Zahl Mp  jetzt

S(2)\;=\;(S(1))^2\;-\;2\;=\;14\;\mathrm{mod}\; M_p

und immer so weiter

S(k+1)\;=\;(S(k))^2\;-\;2\;\mathrm{mod}\; M_p

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:

S(p-1)\;\equiv\;0\; \mathrm{mod}\; M_p,

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

M_7\;=\;127

S(1)\;=\;4\;\mathrm{mod}\; 127

S(2)\;=\;14\;\mathrm{mod}\; 127

S(3)\;=\;194\;\equiv\;67\;\mathrm{mod}\; 127

S(4)\;=\;4487\;\equiv\;42\;\mathrm{mod}\; 127

S(5)\;=\;1762\;\equiv\;111\;\mathrm{mod}\; 127

S(6)\;=\;12319\;=\;97 \cdot 127\;\equiv\;0\; \mathrm{mod} \;127

M7 ist prim.