Mersenne-Primzahlen

SeppJ

Dein anderer Thread hat auch ganz hilfreiche Antworten, unter anderem, dass deine Erkenntnis hier ziemlich trivial ist

Leider kann ich die Threads mit meinen Moderationsmitteln nicht mit vertretbarem Aufwand zusammen führen, daher dieser plumpe Link und die Mitteilung, dass das Problem quasi gelöst ist.

Erhard Henkes

Ja, danke. Endziffer 1 oder 7 hilft leider nicht weiter bei der Diskrimierung.

Ich denke noch über den Divisions-Precheck mit Primzahlen von 7 ... n vor dem Lucas-Lehmer-Test nach. Kann man hier durch mathematische Überlegungen das optimale n in Abhängigkeit der zu prüfenden Mersennezahl 2^p - 1 finden?

Bengo

SeppJ schrieb:

Das folgt, wenn ich mich recht entsinne, aus dem Satz von Euler, kann aber bestimmt auch elementarer gezeigt werden.

Die Aussage glaub ich dir, aber sehe nicht ganz wie das mit Satz von Euler gehen soll?
Du meinst doch den Euler-Fermat oder?
Da kannst ja mehr oder weniger nur kongruenzen zu 1 rausbekommen, und die ist invariant unter multiplikation.

Aber man kann deine Folgerung damit zeigen: nämlich, dass jede vierte Potenz wieder 4 ist, da a^4 \equiv 1 \mod 9

Erhard Henkes

Kurzer Zwischenstand:

- Endziffertest ist sinnlos, weil immer 1 oder 7, wenn p eine Primzahl ist.
- Division durch alle unteren Primzahlen ist zu aufwändig im Verhältnis zum Nutzen
- Division durch 2*k*p+1 mit k = 1 ... k_kmax (ich nehme momentan 600) ist fokussierter, abhängig von p und führt zu Streichungen, die in Summe zeitsparend sind (etwa ein Drittel).
Details und Programm: https://www.c-plusplus.net/forum/333983-10

Bengo

Dein erster Link hier enthält folgendes:

If n=3 (mod 4) is a prime, then 2n+1 divides M_n iff 2n+1 is prime.

Das bedeutet du kannst vorher prüfen, ob dein n=3 (mod 4) und 2n+1 auch prim ist, dann ist die Zahl zusammengesetzt.

Erhard Henkes

@Bengo: Danke für den Hinweis! Die verbesserte Suche wird wieder wichtig, wenn ich die Bestimmung zeitlich im Griff habe.

Das Problem besteht nun mehr in der schieren Größe der Zahlen. Die p-2 Schleifendurchläufe für die Multiplikation ist inzwischen für den klassischen LL Test, zumindest so wie das aktuell durchführe, prohibitiv. Ich kann schon nicht mehr mit einer Cray des Jahres 1996 mithalten. Die Prechecks muss ich schon abschalten, um überhaupt in vernünftiger Zeit den LL zu starten.
https://www.c-plusplus.net/forum/p2464051#2464051

Zwei Wege: 1) schnellste Klasse großer Zahlen für diesen Bereich von 2 ^ mehrere Millionen. Welche ist das?
2) beschleunigte Ganzzahl-Multiplikation https://de.wikipedia.org/wiki/Schönhage-Strassen-Algorithmus (dort die verbesserten versionen)

Richtig?

Erhard Henkes

If n=3 (mod 4) is a prime, then ... .

@Bengo: Nur zur Sicherheit, kannst Du mir das am Beispiel M(11) = 23 * 89 exemplarisch erklären?

2n+1 = 2*11+1 = 23 <== Primzahl, soweit ist der hintere Teil klar.

n=3 (mod 4) <== was muss ich da genau mit p=11 machen?

11%4 = 3 <== ist das damit gemeint? was genau soll ich dann noch auf Primzahl testen? Ich setze nur p ein, die eine Primzahl sind (Primzahl Precheck), und 3 ist klar eine Primzahl.

Habe ich es richtig verstanden, dass ich einfach testen muss, wenn p%4==3, ob isPrime(2*p+1) und dann noch m%(2*p+1) == 0, wenn das erfüllt ist, dann keine mersenne prime? kann ich m%(2*p+1) == 0 sogar einsparen?

Ich habe es ausprobiert, sortiert noch einiges aus, vor allem bevor ich überhaupt M(p) berechnen und handlen muss:

bool precheck_mod4_is_3_and_2p_plus_1_isPrime (vector<bool>& primes, uint64_t p)
{
	return ( (p % 4 == 3) && (primes[2 * p + 1]));
}

Resultat: http://pastebin.com/GzAthiQu

Bengo

Also du willst $2^n-1$ auf Primzahl prüfen. n ist eine Primzahl.
Wenn n \equiv 3 \mod 4 also

n%4 == 3

, und $2n + 1$ auch eine Primzahl ist, dann ist $2^n-1$ zusammengesetzt, und du weißt sogar, dass $2n + 1$ ein Teiler ist.

Bei 11 steht also schon vorher fest, dass die Mersenne Zahl zusammengesetzt ist.
Denn 11 \equiv 3 \mod 4 und 23 ist prim.

Erhard Henkes

OK, dann habe ich das wohl richtig umgesetzt. Danke für den Tipp!

Übrigens ist dieser precheck im unteren Bereich p<10000 noch nicht von Vorteil:
vorher: p: 9689 time: 3226 s, jetzt mit diesem Precheck: p: 9689 time: 3403 s
vorher: p: 9941 time: 10907 s , jetzt p: 9941 time: 11748 s (Zeiten noch mit BigUnsigned)

Das sieht fast so aus, als sollte man diesen Precheck erst bei höheren p einführen.

Hier schlägt er zu und erspart ausufernde Analysen:

>>> p = 756011 p_mod4_is_3_and_2p_plus_1_isPrime! <<<
>>> p = 852011 p_mod4_is_3_and_2p_plus_1_isPrime! <<<

Ich habe mir mal die Methoden bei GIMPS angeschaut: http://www.mersenne.org/various/math.php#trial_factoring

Erhard Henkes

Der Flaschenhals bleibt allerdings der Lucas-Lehmer-Test mit seinen p-1 Multiplikationen und Mod-Divisionen. Ich double-checke gerade Mersenne-Zahlen im Rahmen von GIMPS, also mit Prime95, um ein Gefühl zu erhalten für den Geschwindigkeitsbereich, den man ungefähr erreichen sollte. Der LL-Test benötigt auf meinem Rechner im Bereich von p = 38 bis 39 * 10^6 volle 7 Tage pro Zahl pro Thread. Das ist wirklich abschreckend. Man könnte untersuchen, ob es gewisse Abfolgen von Resten gibt im LL, die sicher zu einem Endergebnis ungleich 0 führen, so dass man früher abbrechen könnte und nicht p-1 Schleifen durchlaufen muss. Kennt ihr solche Überlegungen / Arbeiten? Wenn nein, wie könnte man so etwas sinnvoll angehen?
Angenommen, ich speichere die Zahlenfolgen der Reste ab dem Zeitpunkt, an dem der Term (s*s-2) größer als m wird, und man kennt das Endergebnis (Mersenne-Primes sind sicher bekannt bis 37156667.
Wie könnte man diese Abfolgen der Reste sinnvoll analysieren, um ein Abbruchmuster zu finden? Gibt es hier ein Vorbild? In der Gen-Analyse werden doch sicher solche Vergleiche angestellt.

EDIT: Habe mir bisher die s%p (war so die erste idee, muss irgendwas mit p zu schaffen haben) in der Schleife angeschaut und verschiedenes getestet, aber noch keine sichere Zuordnung zu prim/nicht prim gefunden. Ist schon irgenwie nutzlos, dass man Millionen von s bestimmt, die keinerlei Bedeutung haben. Nur das letzte s nach p-1 Durchläufen zählt.