Mersenne-Primzahlen Rechner (Lucas-Lehmer, GIMPS)

Lucas-Lehmer-Test für Mersenne-Primzahlen M_p = 2^p - 1, Liste der 51 bekannten Primzahlen, Verbindung zu vollkommenen Zahlen (Euklid-Euler) und GIMPS-Projekt.

Berechnungsparameter
Scegli il tipo di calcolo.
Esponente p di M_p = 2^p - 1. Deve essere primo. Max 31 per calcolo esatto in JS (M_31 = 2^31 - 1 ≈ 2,1·10^9).
Quanti primi di Mersenne noti mostrare (fino a M_51 scoperto nel 2018).
War dieser Rechner nützlich?

Die Mersenne-Primzahlen

Mersenne-Primzahlen sind Primzahlen der Form M_p = 2^p - 1 mit p prim. Benannt nach dem franzoesischen Minimitenmoench Marin Mersenne (1588-1648).

Wichtiger Satz: Ist M_p prim, so muss p prim sein. Beweis: Wenn p = ab mit a, b > 1, dann ist 2^p - 1 = (2^a)^b - 1 durch 2^a - 1 teilbar. Umkehrung falsch: p = 11 prim, aber M_11 = 2047 = 23·89 zusammengesetzt.

Die vier Modi

  1. Lucas-Lehmer-Test: deterministisch für M_p.
  2. Liste der 51 bekannten Primzahlen (2024).
  3. Vollkommene Zahlen via Euklid-Euler.
  4. Eigenschaften von M_p mit Bedingung p prim.

Lucas-Lehmer-Test

s_0 = 4; s_(i+1) = (s_i^2 - 2) mod M_p. M_p ist prim gdw. s_(p-2) ≡ 0 mod M_p. Von Lucas (1878) und Lehmer (1930) entwickelt. Komplexitaet O(p^2 · M(p)).

Satz von Euklid-Euler

N ist eine gerade vollkommene Zahl gdw. N = 2^(p-1) · (2^p - 1) mit M_p Mersenne-Primzahl. Euklid (300 v. Chr.) bewies eine Richtung, Euler (1747) die Umkehrung. Ob ungerade vollkommene Zahlen existieren, ist seit 2000 Jahren offen.

Gerade vollkommene Zahlen

  • M_2 = 3 → 6
  • M_3 = 7 → 28
  • M_5 = 31 → 496
  • M_7 = 127 → 8128
  • M_13 = 8191 → 33 550 336

GIMPS

Great Internet Mersenne Prime Search (seit 1996), von George Woltman geleitetes verteiltes Rechenprojekt. Prime95-Programm mit FFT-optimiertem Lucas-Lehmer. Rekord 2024: M_82589933, 2018 von Patrick Laroche entdeckt, 24 862 048 Dezimalstellen. GIMPS-Preis: 150 000 USD für die erste Primzahl mit mehr als 100 Millionen Stellen.

Anwendungen

  • Mersenne Twister: Zufallsgenerator mit Periode 2^19937 - 1.
  • Krypto-Hardware: vereinfacht modulare Reduktion.
  • CPU-Benchmark: deterministischer Stresstest.
  • Verteiltes Rechnen: GIMPS als Pionier.

Offene Vermutungen

  • Unendlich viele Mersenne-Primzahlen: LPW-Vermutung ~ 2,569 ln N.
  • Ungerade vollkommene Zahlen: Existenz unbekannt.
  • Doppelte Mersenne: unendlich viele Paare (p, q), beide Mersenne-Primzahlen?

Der Lucas-Lehmer-Test und die Jagd nach Rekordprimzahlen

Die grossten bekannten Primzahlen sind fast immer Mersenne-Primzahlen, und der Grund ist ein aussergewohnlich effizienter Algorithmus: der Lucas-Lehmer-Test. Fur einen primen Exponenten p beginnt er mit s gleich 4 und wiederholt p minus zwei mal die Operation quadrieren, zwei abziehen und modulo 2 hoch p minus eins reduzieren; die Zahl ist genau dann prim, wenn der letzte Wert null ist. Dieser Test ist deterministisch, nicht probabilistisch, und die Reduktion modulo einer Mersenne-Zahl ist besonders billig, weil diese Zahl in Binar eine Folge von Einsen ist, was die Rechnungen sehr schnell macht.

Seit 1996 koordiniert das Projekt GIMPS, Abkurzung fur Great Internet Mersenne Prime Search, tausende freiwillige Computer, die diesen Test auf Kandidatenexponenten ausfuhren. Dank dieser gemeinsamen Anstrengung wurden die grossten Primzahlen der Geschichte entdeckt, jede mit Millionen Ziffern, und der aktuelle Rekord ist 2 hoch 82.589.933 minus eins, mit fast 25 Millionen Ziffern. Die Electronic Frontier Foundation bietet Geldpreise fur denjenigen, der Primzahlen mit mehr als hundert Millionen Ziffern findet, eine offene Herausforderung, die die Suche am Leben halt.

Vollkommene Zahlen: eine Brucke uber 2300 Jahre

Die Mersenne-Primzahlen sind mit einem anderen uralten mathematischen Objekt verbunden: den vollkommenen Zahlen, jenen, die der Summe ihrer echten Teiler gleichen, wie 6 = 1 + 2 + 3 oder 28 = 1 + 2 + 4 + 7 + 14. Der Satz von Euklid-Euler stellt eine perfekte Entsprechung zwischen beiden her: jede gerade vollkommene Zahl hat die Form 2 hoch p minus eins mal 2 hoch p minus eins, wobei dieser letzte Faktor eine Mersenne-Primzahl ist. Euklid bewies eine Richtung um 300 v.Chr. und Euler vervollstandigte die Umkehrung zweitausend Jahre spater, 1747.

Das bedeutet, dass jede entdeckte Mersenne-Primzahl automatisch eine neue gerade vollkommene Zahl schenkt, und man kennt nur so viele vollkommene Zahlen wie Mersenne-Primzahlen. Die Griechen schrieben diesen Zahlen bereits eine mystische Aura zu, und Nikomachos ordnete sie mit Ehrfurcht ein. Doch eine vor mehr als zwei Jahrtausenden gestellte Frage bleibt unbeantwortet: niemand hat je eine ungerade vollkommene Zahl gefunden noch bewiesen, dass sie nicht existieren kann. Man weiss, dass sie, falls sie existiert, grosser als 10 hoch 1500 ware, aber das Ratsel bleibt.

Aktualisiert im Juli 2026

Häufig gestellte Fragen

Was sind Mersenne-Primzahlen?

Es sind Primzahlen der Form M_p = 2^p - 1 mit primem p. Sie sind nach Marin Mersenne (1588-1648) benannt, einem franzosischen Monch, der ihre Eigenschaften untersuchte. Die ersten Beispiele sind 3, 7, 31, 127, fur p = 2, 3, 5, 7. Sie sind eng mit den vollkommenen Zahlen und den grossten je entdeckten Primzahlen verbunden.

Warum muss p prim sein, wenn M_p prim ist?

Weil, wenn p zusammengesetzt ware, etwa p = ab mit a, b > 1, dann 2^p - 1 = (2^a)^b - 1 durch 2^a - 1 teilbar und somit zusammengesetzt ware. Also ist p prim eine notwendige Bedingung. Sie ist jedoch nicht hinreichend: fur p = 11 prim ist M_11 = 2047 = 23 x 89 zusammengesetzt.

Was ist der Lucas-Lehmer-Test?

Es ist ein deterministischer und effizienter Test, um zu entscheiden, ob M_p prim ist. Man beginnt mit s_0 = 4 und iteriert s_(i+1) = (s_i^2 - 2) mod M_p p-2 mal: M_p ist genau dann prim, wenn der letzte Wert s_(p-2) null ist. Es ist die Methode, mit der die grossten bekannten Primzahlen entdeckt werden.

Wie viele Mersenne-Primzahlen sind bekannt?

Stand 2024 sind 51 bekannt. Die grosste ist M_51 = 2^82589933 - 1, mit fast 25 Millionen Dezimalstellen, im Dezember 2018 vom GIMPS-Projekt entdeckt. Es ist unbekannt, ob die Mersenne-Primzahlen endlich oder unendlich sind: es ist eine offene Vermutung.

Was ist das GIMPS-Projekt?

Es ist die Great Internet Mersenne Prime Search, ein seit 1996 aktives verteiltes Rechenprojekt, in dem Tausende Freiwillige ihre Computer bereitstellen, um den Lucas-Lehmer-Test auf Kandidatenexponenten auszufuhren. Es hat alle jungsten Rekordprimzahlen entdeckt. Die EFF bietet Geldpreise fur sehr grosse Primzahlen.

Welche Verbindung besteht zu den vollkommenen Zahlen?

Der Satz von Euklid-Euler besagt, dass jede gerade vollkommene Zahl die Form 2^(p-1)(2^p - 1) mit einer Mersenne-Primzahl 2^p - 1 hat. Beispiele: 6, 28, 496, 8128. Jede neue Mersenne-Primzahl erzeugt eine neue gerade vollkommene Zahl. Es ist unbekannt, ob ungerade vollkommene Zahlen existieren.

Warum sind die grossten bekannten Primzahlen Mersenne-Zahlen?

Weil der Lucas-Lehmer-Test aussergewohnlich effizient und die Reduktion modulo 2^p - 1 billig ist: in Binar ist diese Zahl eine Folge von Einsen, was die Rechnungen schnell macht. So lassen sich enorme Exponenten testen, weit uber die Reichweite von Zahlen allgemeiner Form hinaus.

Wozu dienen die Mersenne-Primzahlen?

Dem Zufallszahlengenerator Mersenne Twister mit Periode 2^19937 - 1, der kryptographischen Hardware, wo sie die modulare Reduktion erleichtern, als deterministische Benchmarks zum Testen von CPUs und als Pioniere des verteilten Rechnens mit GIMPS. Sie sind auch ein faszinierendes Prufterrain fur die Zahlentheorie.

Kommentare (0)

Noch keine Kommentare. Sei der Erste!