Mersenne'sche Primzahlen

Computer: Software & Programmierung Programmierung allgemein
#1

Mersenne 40 ist entdeckt: 2^20996011-1 ist prim :smile:

Was mich in dem Zusammenhang interessieren würde,
wie geht man bei derartig großen Zahlen vor, um zu zeigen, daß sie
prim sind?

Weiters: Mathematica 4.2 benötigte auf meinem
iXeon 2.4 GHz weniger als 100 sec. zum Berechnen aller Stellen
dieser Primzahl;

mein eigenes Programm, welches mit allen Schikanen optimiert
(Assembler, u. a.) ist, benötigt dafür aber beinahe 100 min., mein
Algorithmus:

Umrechnung der Dualzahl (lauter 1en) durch permanentes
Dividieren durch 1 0000 0000, so lange bis die Zahl nur noch Rest
liefert, sprich kleiner als 100000000 ist; damit erhalte ich 8stellige
Blöcke im Dezimalsystem, welche ich einfach ausgeben kann;

Ist der Algorithmus schlecht?

Wo liegt das Problem, daß mein Program derart lange braucht?
(auf einem Athlon XP 2400 benötigt es noch länger)

Wer kennt einen pfeilschnellen Algorithmus?

Oder hat Mathematica gar Tabellen und rechnet gar nicht?

Weiß da jemand mehr?

Gruß,
Walter

#2

Hi.

Mersenne 40 ist entdeckt: 2^20996011-1 ist prim :smile:

Schön für dich.

Was mich in dem Zusammenhang interessieren würde,
wie geht man bei derartig großen Zahlen vor, um zu zeigen, daß
sie
prim sind?

google Beweis prim algorithmus
führte mich ua auf die wikipedia, die das Thema Primzahlen anscheinend ganz gut beschreibt: http://de.wikipedia.org/wiki/Primzahl

Weiters: Mathematica 4.2 benötigte auf meinem
iXeon 2.4 GHz weniger als 100 sec. zum Berechnen aller Stellen
dieser Primzahl;
mein eigenes Programm, welches mit allen Schikanen optimiert
(Assembler, u. a.) ist, benötigt dafür aber beinahe 100 min.,
… bla …
Wo liegt das Problem, daß mein Program derart lange braucht?
(auf einem Athlon XP 2400 benötigt es noch länger)
Wer kennt einen pfeilschnellen Algorithmus?

Um das ganze abzukürzen: Primzahlen finden ist genauso Volkssport wie:

  • Stellen von PI errechnen
  • Das Travelling Salesman Problem
  • Der beste, einzigartigste (und tollste) Verschlüsselungsalgorithmus der Welt
  • Großrechnerwettrüsten

Wie wärs mit „google Primzahlen Algorithmus“ oder vielleicht „google algorithm prime number“ oder was ähnlich offensichtliches - Du solltest ein paar Seiten zu dem Thema finden.

Oder hat Mathematica gar Tabellen und rechnet gar nicht?

Nebenbei gesagt: Die Geschwindigkeit der Algorithmen von Mathematica ist das, was das Geld ausmacht, wenn man das kauft. Da sitzen einige Mathematiker dahinter, die vielleicht vorher auch in Google geschaut haben, bevor Sie dann bei Wer-Weiss-Was gefragt haben :wink:

Weiß da jemand mehr?

google mfG,

J.P.Jarolim

Ein schönes 2^20996011-1 euch allen.

#3

Hallo,
für diese Primzahlen gibt es ein Verfahren („Lucas-Lehmer Test“), daß simpler ist, als herkömmliche Primzahltests.

Gruss
Enno

#4

Hi,

Simple ist gut, die T(k)'s werden doch mindestens so groß wie M(n); bei sehr sehr großem M(n) kann man lange T(k+1) machen, bis das Modulo zum Tragen kommt;

Gruß,
Walter

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#5

Hallo,
simpel im Sinne, daß nur in Abhängigkeit des Exponenten von M(n) viele T(k) berechnet werden müssen und das „mod M(n)“ im Dualsystem eine einfache Operation ist. Für M(n)=2^p-1 sind für alle T(k) und deren Berechnung max. p Bits und p-1 Schritte notwendig.

Gruss
Enno