Mersenneprimzahlen finden (Teilertest)

Neue Frage »

reinkie Auf diesen Beitrag antworten »
Mersenneprimzahlen finden (Teilertest)
Auf der amerikanischen Internetseite www.mersenne.org wird ein realisiertes verteiltes Computernetz beschrieben, an dem sich jedermann beteiligen kann. Ich habe auf meiner Internetseite www.euroware.de ebenso (eine veraltete 32-Bitversion) verschiedene Verfahren rund um die Primzahlen zum kostenlosen Download gestellt. Läuft aber noch unter Windows 10.
Es geht darum, möglichst große Primzahlen mit der Bildungsregel 2^p – 1 (Mersenne-Primzahlen) zu finden. Diese werden in der Kryptologie benötigt und es gibt auch meines Wissens Preisgelder bei sehr großen Exemplaren.
Der Lucas-Lehmer-Test ist momentan das effizienteste Verfahren, um zu zeigen Prim oder Nicht-Prim. Für die großen gesuchten Exemplare und bei einem sehr schnellen Rechner dauert er aber mehrere Monate pro Test.
Eine andere Möglichkeit, ist es, einen Teiler zu finden. Diese potenziellen Teiler haben immer die Form: (2ip + 1).
P ist dabei immer eine Primzahl. Wenn p teilbar wäre, kann 2^p – 1 keine Primzahl sein. Ist bekannt und bewiesen. Siehe Internet.
Laut Wikipedia gibt es derzeit 51 Mersenne-Primzahlen. Die höchste für: p = 82.589.933
Es gilt die Formel: (2ip+1) * (2kp+1) = 2np+1 = 2^p – 1 (aber nur dann, wenn die Mersennezahl zusammengesetzt ist (also nicht Prim)
Es geht darum, weitere Aussagen (z.B.: mögliche mod-Reste) über die möglichen Variablen i und k zu finden. Zum Beispiel: k mod 4 = 0
Unbekannte Variablen sind „nur“ i und k (beides natürliche Zahlen). Es handelt sich also „nur“ um 2 Gleichungen mit 2 Unbekannten. n ist für jedes p errechenbar.
(2ip+1) * (2kp+1) = 2np+1
(2ip+1) * (2kp+1) = 2^p – 1
Allerdings ist die Lösung irgendwie Diophantisch…
Hinweise für diejenigen, die sich noch nicht damit beschäftigt haben:
MP7 = Dual(1111111) = 127 (Primzahl, also gelten die Formeln oben nicht!) = Keine Lösung
MP11 = Dual(11111111111) = 2047 = 23 * 89 (Nicht Prim, Lösung vorhanden i=1 und k=4
Dual bestehen die Mersennezahlen also immer aus einer Kette von 1en
HAL 9000 Auf diesen Beitrag antworten »

GIMPS existiert ja schon eine gefühlte Ewigkeit. Aber schön, wenn es mal jemand für die nachwachsende Generation in Erinnerung ruft. Augenzwinkern

Ich hätte erwartet, dass es mittlerweile die Prime95-Suchsoftware auch in Varianten für die massiv parallelen Recheneinheiten (mit mehreren Hundert Kernen) der diversen Pixelmonster-GPUs gibt, aber auf https://www.mersenne.org/download gibt es nach wie vor nur ein paar spärliche Hinweise auf "Some Mersenne-related software" in diesem Bereich GPU Computing. Denn nur mit der Haupt-CPU mit ihren paar Kernen (selbst wenn man einen stattlichen PC mit 16 Kernen sein eigen nennt) ist heute da kaum noch ein Blumentopf zu gewinnen - du hast ja selbst die mehrmonatige Rechenzeit für nur einen Test erwähnt. Immerhin habe ich für die Energieverschwendung in dem Bereich noch mehr Verständnis als für diese unsäglichen Bitcoin-Rechenfarmen.
Elvis Auf diesen Beitrag antworten »

Von www.mersenne.org kann man sehr schön lernen, was Mersenne-Primzahlen sind, wie sie mit vollkomenen Zahlen zusammenhängen und wie der Lucas-Lehmer-Test funktioniert.
Zweifellos ist es löblich, sich an der Suche nach großen Primzahlen zu beteiligen, es kostet aber leider Strom und damit Geld, wenn der PC ein Jahr lang Tag und Nacht rechnet - und dann bekommt man kein Lob für Sparsamkeiit von der lieben Gattin, die zwar weiß, was eine Primzahl ist, aber selten so große Primzahlen braucht.
Ich wüßte gern, ob es unendlich viele Mersenne-Primzahlen und damit unendlich viele vollkommene Zahlen gibt, aber in der Richtung sind mir keine Fortschritte bekannt - ich will nicht unendlich lange auf eine Antwort warten.
reinkie Auf diesen Beitrag antworten »

Es gilt die Formel: (2ip+1) * (2kp+1) = 2np+1 = 2^p – 1 (aber nur dann, wenn die Mersennezahl zusammengesetzt ist (also nicht Prim)
Es geht darum, weitere Aussagen (z.B.: mögliche mod-Reste) über die möglichen Variablen i und k zu finden. Zum Beispiel: k mod 4 = 0
Unbekannte Variablen sind „nur“ i und k (beides natürliche Zahlen). Es handelt sich also „nur“ um 2 Gleichungen mit 2 Unbekannten. n ist für jedes p errechenbar.
(2ip+1) * (2kp+1) = 2np+1
(2ip+1) * (2kp+1) = 2^p – 1
Allerdings ist die Lösung irgendwie Diophantisch…

Dies war das eigentliche Problem!

Ich suche nach weiteren Aussagen über die möglichen i, k
k mod 4 = 0
Daraus resultiert eine neue Formel: (2ip+1) * (8kp+1) = 2^p – 1 (Dies ist so richtig! Und viele Lösungen für k scheiden aus. (75%))
reinkie Auf diesen Beitrag antworten »

Wenn sich jemand für die Aufgabenstellung oder ganz allgemein für Primzahlen interessiert, dem empfehle ich die Seite www.kiebart.de
Die beiden letzten Punkte "Primzahlen" und "Der Kiebartkamm" zeigen schöne Beispiele, wie man schneller als mit dem Sieb des Eratosthenes "kleine" Primzahlen (<4.000.000.000) findet und vor allen Dingen platzsparend in einem Array unterbringen kann und
wie man zu sehr großen Mersennezahlen schnell eventuelle Teiler findet. (per Software)
z.B.: 432.074.849.836.367 teilt 2^1.214.505.343 - 1

Zur Speicherung der Primzahlen bis 4.000.000.000 werden (4.000.000.000 / 30) Bytes benötigt
also ca. 133 MB, was für moderne Programmiersprachen keinerlei Probleme bereitet, diese im Arbeitsspeicher zur Verfügung zu stellen. Anmerkung: Bei diesem Verfahren können die 3 ersten Primzahlen 2, 3, 5 allerdings NICHT gespeichert werden.

Der Kiebartkamm braucht zur Berechnung und Speicherung dieser Zahlen auf meinem Rechner (neu<500€) AMD FX-8370E Eight-Core Processor 3.30 GHz
mit (leider) 32-Bit-Programmierung unter Windows 64 ca. 13,5 Sekunden

Die Erklärung, wie der Kiebartkamm und das Speichern funktioniert, findet ihr ausführlich auf meiner Seite. (siehe oben) Zum Copyright-freien Nachbauen bestimmt.

Oder die Beschreibung meiner Software KK.EXE: http://www.euroware.de/primzahlen/version1/index.htm

Wie die einzelnen Algorithmen funktionieren und welche Mathematik dahinter steht, erkläre ich euch gerne hier. Bitte fragen.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von reinkie
"Der Kiebartkamm" zeigen schöne Beispiele, wie man schneller als mit dem Sieb des Eratosthenes "kleine" Primzahlen (<4.000.000.000) findet und vor allen Dingen platzsparend in einem Array unterbringen kann

Tja, du warst 17 Jahre im Matheboard-Dornröschenschlaf und hast so einiges verpasst: In dem nun auch schon 14 Jahre alten Thread wurde bereits mit solchen Eratosthenes-ähnlichen Sieben die Primzahlen bis 500 Milliarden in Berechnungen einbezogen.
 
 
Elvis Auf diesen Beitrag antworten »

Die vorläufige Mersenne-Primzahl M51* hat 24.862.048 Dezimalziffern, da sind wir im Bereich richtig großer Primzahlen, die noch nie ein Mensch zuvor gesehen hat. Mit Sieben oder Kämmen erreicht man solche Größenordnungen nicht, auch Lucas-Lehmer hat bisher noch nicht alle Kandidaten für Mersenne-Primzahlen über M48 (17.425.170 Dezimalziffern) getestet. Wir geben uns nicht mit Kleinigkeiten zufrieden, erst die Unendlichkeit wird unseren Ansprüchen einigermaßen gerecht: soyez réalistes, demandez l'impossible.
reinkie Auf diesen Beitrag antworten »

Hallo Elvis,
da hast du natürlich recht, dass mit sieben und kämmen, solche Bereiche nicht nach Primzahlen durchsucht werden können.
10.132.981.782.005.969 teilt 2^1.040.516.423-1
6.243.098.839 teilt 2^1.040.516.473-1
210.184.340.879 teilt 2^1.040.516.539-1
393.315.271.399 teilt 2^1.040.516.591-1
6.243.099.943 teilt 2^1.040.516.657-1
884.439.180.551 teilt 2^1.040.516.683-1
5.524.662.995.451.367 teilt 2^1.040.516.707-1
8.324.133.737 teilt 2^1.040.516.717-1
8.324.133.977 teilt 2^1.040.516.747-1
117.212.135.472.569 teilt 2^1.040.516.791-1
2.446.546.362.665.521 teilt 2^1.040.516.809-1
2.081.033.807 teilt 2^1.040.516.903-1
260.129.239.751 teilt 2^1.040.516.959-1
21.093.360.644.273 teilt 2^1.040.517.001-1
8.290.839.926.113 teilt 2^1.040.517.059-1
22.891.375.343 teilt 2^1.040.517.061-1
4.370.171.706.601 teilt 2^1.040.517.073-1
159.713.130.058.967 teilt 2^1.040.517.089-1
2.081.034.239 teilt 2^1.040.517.119-1
9.691.376.893.439 teilt 2^1.040.517.167-1
10.405.172.111 teilt 2^1.040.517.211-1
2.081.034.479 teilt 2^1.040.517.239-1
27.444.682.748.617 teilt 2^1.040.517.241-1
441.770.340.959.609 teilt 2^1.040.517.281-1
474.475.912.969 teilt 2^1.040.517.353-1
391.234.543.529 teilt 2^1.040.517.403-1
49.944.836.497 teilt 2^1.040.517.427-1
8.324.139.977 teilt 2^1.040.517.497-1
2.078.304.855.851.713 teilt 2^1.040.517.587-1
16.648.282.193 teilt 2^1.040.517.637-1
5.985.057.586.073 teilt 2^1.040.517.661-1

Diese Ausgabe meiner Software wurde in etwa 10 Sekunden berechnet. Es geht darum Teiler von Mersennezahlen zu finden. Ich habe bewusst einen Bereich gewählt, den GIMPS noch nicht untersucht hat.
Hier geht es um Mersennezahlen mit durchschnittlich 313.226.951 Dezimalstellen.
Den Kamm brauche ich nur beim Start der Software, um einen Grundvorrat an Primzahlen zu haben für die Schleife zum Hochzählen der Potenzen auf der rechten Seite der obigen Ausgabe.
Mit GIMPS wurden solche Zahlen noch nicht untersucht!
Also z.B.; 2.078.304.855.851.713 teilt 2^1.040.517.587 - 1
Sowohl der gefundene Teiler 2.078.304.855.851.713
als auch die 2er Potenz 1.040.517.587 sind Primzahlen.

Klar, dass ich einen Primzahlenblock gespeichert habe. Der Kiebartkamm braucht ja 6,8 Sek. für die Primzahlen bis 2.000.000.000 immer 6,8 Sekunden. Das Einlesen des Blocks einen Bruchteil von einer Sekunde.

Aber wichtig, in dieser Matheaufgabe geht es nicht! um den Kiebartkamm, sondern um das Suchen von Mersenneteilern, also Teiler, die Mersennezahlen mit einer Primzahl als Potenz, teilen.

Klar, dass die gefundenen Teiler in eine Datenbank eingetragen werden. Diese Mersennezahlen sind ja nicht Prim und brauchen nicht mehr untersucht werden.

Ich habe 2 JPGs in Dateianhänge eingefügt. Hoffentlich hat das geklappt.
Elvis Auf diesen Beitrag antworten »

Ich würde mich sehr mit dir und für dich freuen, wenn du mit deinem Verfahren in diesen gigantischen Bereichen eine Mersenne-Primzahl finden würdest. Zeit seines Lebens keine Mersenne-Primzahl finden kann jeder.
reinkie Auf diesen Beitrag antworten »

Hallo Elvis,
mir geht es in erster nicht darum, die nächste Mersenneprimzahl zu finden, sondern in dieser Matheaufgabe Mersenneprimzahlkandidaten auszukegeln. So ähnlich wie eine Art Sieb oder Kamm!

Der Screen-Shot mit den gefundenen Teilern hat beim Ablauf ca. 10 - 20 Sekunden gebraucht. Das ist für mich mittlerweile sehr langsam.

ich wiederhole nochmal die eigentliche Aufgabe:

Es gilt die Formel: (2ip+1) * (2kp+1) = 2np+1 = 2^p – 1 (aber nur dann, wenn die Mersennezahl zusammengesetzt ist (also nicht Prim)
Es geht darum, weitere Aussagen (z.B.: mögliche mod-Reste) über die möglichen Variablen i und k zu finden. Zum Beispiel: k mod 4 = 0
Unbekannte Variablen sind „nur“ i und k (beides natürliche Zahlen). Es handelt sich also „nur“ um 2 Gleichungen mit 2 Unbekannten. n ist für jedes p errechenbar.
(2ip+1) * (2kp+1) = 2np+1
(2ip+1) * (2kp+1) = 2^p – 1
Allerdings ist die Lösung irgendwie Diophantisch…

Dies war das eigentliche Problem!

Ich suche nach weiteren Aussagen über die möglichen i, k
k mod 4 = 0
Daraus resultiert eine neue Formel: (2ip+1) * (8kp+1) = 2^p – 1 (Dies ist so richtig! Und viele Lösungen für k scheiden aus. (75%))
Neue Frage »
Antworten »



Verwandte Themen