Mersenne-Prüfer

Ist Mp selbst prim, heißt sie Mersenne-Primzahl — Zahlen, die seit Jahrhunderten Rekordsuchen angetrieben haben, von Marin Mersennes frühen Listen bis zu modernen verteilten Projekten. Nicht jeder Exponent liefert eine Primzahl: ist p zusammengesetzt, ist Mp zusammengesetzt, und selbst bei vielen primen Exponenten faktorisiert die Mersenne-Zahl (zum Beispiel 2^11 − 1 = 2047 = 23 × 89). Dieses Werkzeug nimmt einen ganzzahligen Exponenten p mindestens zwei, liefert den vollen Dezimalwert von 2^p − 1 als Zeichenkette und entscheidet, ob dieser Wert prim ist, mit dem deterministischen Lucas-Lehmer-Test wenn p eine ungerade Primzahl ist.

Was Mersenne-Zahlen sind und wie Lucas-Lehmer entscheidet

Eine Mersenne-Zahl wird durch einen einzigen Exponenten definiert: Mp ist zwei hoch p, minus eins. Die ersten Werte sind vertraute Klassenkonstanten — M2 ist drei, M3 sieben, M5 einunddreißig, M7 einhundertsiebenundzwanzig — während größere Exponenten ganze Zahlen mit Tausenden Dezimalziffern erzeugen. Eine Mersenne-Primzahl ist einfach eine Mersenne-Zahl die prim ist.

Eine klassische notwendige Bedingung ist, dass der Exponent p selbst prim ist: faktorisiert sich p als ab mit a und b größer als eins, dann teilt 2^a − 1 die Zahl 2^{ab} − 1, sodass Mp nicht prim sein kann. Diese notwendige Bedingung ist nicht hinreichend. Für p gleich elf, das prim ist, ist M11 zweitausendsiebenundvierzig und faktorisiert sich als dreiundzwanzig mal neunundachtzig.

Der Lucas-Lehmer-Test klärt die Frage vollständig für ungerade Primexponenten. Starten Sie mit s null gleich vier; für jeden der nächsten p minus zwei Schritte ersetzen Sie s durch s im Quadrat minus zwei, reduziert modulo Mp. Die Mersenne-Zahl ist prim genau dann, wenn der Endrest null ist.

Für den Sonderfall p gleich zwei ist die Zahl drei per Inspektion prim und braucht die iterative Folge nicht. Diese Fähigkeit implementiert diese exakte Pipeline mit BigInt-Arithmetik: sie approximiert nie, ruft nie einen Primheitsdienst und hängt nie von Wanduhrzeit oder Zufallsbits ab. Sie erhalten für dasselbe p immer denselben Booleschen Wert.

Wo Mersenne-Prüfungen in der Praxis vorkommen

Wettbewerbsprogrammierer und Olympiade-Coaches nutzen kleine Mersenne-Prüfungen als Aufwärmen vor schwierigeren modularen Arithmetikproblemen und brauchen ein deterministisches Orakel von dem Studierende nicht versehentlich von einer Tabellenformel abweichen können. Krypto- und Systemingenieure prüfen manchmal Lehrdemos oder historische Tabellen bekannter Mersenne-Primzahlen ohne kryptographische Stärke aus einer einzigen modularen Folge zu behaupten. Wenn Sie später Zwillingspaare, π(n) oder Faktorisierung einer allgemeinen zusammengesetzten Zahl brauchen, behandeln Sie diese als getrennte Suchintentionen statt diese Mersenne-fokussierte Seite zu überladen.

Mersenne-Zahlen bleiben die richtige Seite wenn die Frage lautet was 2^p − 1 ergibt und ob Lucas-Lehmer (oder die Regel für zusammengesetzte Exponenten) es als Mersenne-Primzahl zertifiziert.