Willkommen in Manus Zeitforum
InformationenAnmelden Registrieren

Erweiterte Suche

Die größte bislang bekannte Primzahl

Thema erstellt von Skeptika 
Beiträge: 254, Mitglied seit 10 Jahren
Neulich las ich in den Nachrichten, dass die bislang größte Primzahl mit über 22 Mio Stellen gefunden wurde (kann sie hier leider nicht in voller Länge wiedergeben, höchstens die Kurzform: 274207281 -1). Ein Computer hat dafür etwa einen Monat gerechnet und da überkamen mich spontan mehrere Gedanken:

1. Wie sieht wohl so ein Algorithmus dafür aus? Hier geht es ja um Zahlen, für den es in keiner Programmiersprache einen Variablentyp gibt. Maximal Strings wären in der Lage, sehr viele einzelne Stellen aufzunehmen, aber das würde ja bedeuten, dass man eine lange Zahl dann Ziffer für Ziffer durchrechnet und da fehlt mir irgendwie das mathematische Verständnis dafür.

2. Wenn so eine Zahl gefunden wurde, dann muss irgend jemand das Ergebnis überprüfen. Wie kann man eine Zahl mit 22 Mio Ziffern prüfen, ob sie prim (und vielleicht sogar noch eine Mersenne-Primzahl) ist?

3. Würde man diese Zahl mit über 22 Millionen und 300 Tausend Stellen ausdrucken und jede Ziffer wäre nur 1 mm breit, so brauchte man einen Papierstreifen von über 22 Km Länge. Abgesehen davon, dass es die menschliche Neugier und die Sehnsucht nach immer größeren Superlativen befriedigen hilft - wozu braucht man so große Primzahlen?

Hier geht es zu einem Artikel, in welchem auch der Hinweis steht, dass man richtig viel Geld für das Auffinden einer Primzahl mit 100 Mio und 1 Mrd Stellen bekommen kann. Hat jemand Lust, mit zu suchen? Das Geld könnten wir uns ja teilen. :smiley32:
Signatur:
978-3842349889
Beitrag zuletzt bearbeitet von Skeptika am 07.10.2022 um 11:09 Uhr.
[Gäste dürfen nur lesen]
avatar
Stueps (Moderator)
Beiträge: 3.503, Mitglied seit 19 Jahren
Hallo Skeptika,

Skeptika schrieb in Beitrag Nr. 2236-1:
Hat jemand Lust, mit zu suchen?

Hier bitte:

Die Zahl 2100000000057-1 ist prim, und dazu noch eine Mersenne-Primzahl.

Hab das eben schriftlich durchgerechnet, es stimmt :lie:.

Primzahlen faszinieren mich, leider kann ich dir jedoch keine deiner Fragen beantworten, nicht einmal ansatzweise. Aber sehr interessantes Thema, welches du da eröffnet hast!

Grüße
Signatur:
Diese Welt gibt es nur, weil es Regeln gibt.
[Gäste dürfen nur lesen]
Beiträge: 254, Mitglied seit 10 Jahren
n² + n + 41 = ergibt (oft) eine Primzahl.

n y=n²+n+41 Primzahl?
0 41 ja
1 43 ja
2 47 ja
3 53 ja
4 61 ja
5 71 ja
6 83 ja
7 97 ja
8 113 ja
9 131 ja
10 151 ja
11 173 ja
12 197 ja
13 223 ja
14 251 ja
15 281 ja
16 313 ja
17 347 ja
18 383 ja
19 421 ja
20 461 ja
21 503 ja
22 547 ja
23 593 ja
24 641 ja
25 691 ja
26 743 ja
27 797 ja
28 853 ja
29 911 ja
30 971 ja
31 1033 ja
32 1097 ja
33 1163 ja
34 1231 ja
35 1301 ja
36 1373 ja
37 1447 ja
38 1523 ja
39 1601 ja
40 1681 nein
41 1763 ja
42 1847 ja
43 1933 ja
44 2021 nein
45 2111 ja
46 2203 ja
47 2297 ja
48 2393 ja
49 2491 nein
50 2591 ja
51 2693 ja
52 2797 ja
53 2903 ja
54 3011 ja
55 3121 ja
56 3233 nein
57 3347 ja
58 3463 ja
59 3581 ja
Signatur:
978-3842349889
[Gäste dürfen nur lesen]
avatar
Beiträge: 1.735, Mitglied seit 17 Jahren
Skeptika schrieb in Beitrag Nr. 2236-1:
Neulich las ich in den Nachrichten, dass die bislang größte Primzahl mit über 22 Mio Stellen gefunden wurde (kann sie hier leider nicht in voller Länge wiedergeben, höchstens die Kurzform: 274207281 -1). Ein Computer hat dafür etwa einen Monat gerechnet und da überkamen mich spontan mehrere Gedanken:

1. Wie sieht wohl so ein Algorithmus dafür aus? Hier geht es ja um Zahlen, für den es in keiner Programmiersprache einen Variablentyp gibt. Maximal Strings wären in der Lage, sehr viele einzelne Stellen aufzunehmen, aber das würde ja bedeuten, dass man eine lange Zahl dann Ziffer für Ziffer durchrechnet und da fehlt mir irgendwie das mathematische Verständnis dafür.

2. Wenn so eine Zahl gefunden wurde, dann muss irgend jemand das Ergebnis überprüfen. Wie kann man eine Zahl mit 22 Mio Ziffern prüfen, ob sie prim (und vielleicht sogar noch eine Mersenne-Primzahl) ist?

Der Standard-Primzahltest ist der von Miller-Rabin.
Der kann in endlicher Zeit final sagen, ob eine Zahl eine Primzahl ist.
Gewöhnlich wird der Kern-Algorithmus nur in Stichproben durchgeführt, weil die Wahrscheinlichkeit einer falschen Qualifizierung mit der Zahl der Tests exponentiell abnimmt.
Die Stichproben-Variante hat die Komplexität (=Rechenaufwand) O(k log3n) bei k Tests und n Stellen.

Für Potenzkonstrukte wie n² + n + 41 oder die von Mersenne 2 n − 1 kann man ggf. effizientere Kriterien beweisen,
z.B. Lucas-Lehmer-Test.

Eine Strategie zum finden großer Prim-Zahlen wäre die Vor-Qualifizierung mit Rabin-Miller nach Wahrscheinlichkeit und dann die Anwendung eines spezifischen Kriteriums.
Signatur:
Ich bin begeistert!
Beitrag zuletzt bearbeitet von Thomas der Große am 12.09.2023 um 20:49 Uhr.
[Gäste dürfen nur lesen]
In diesem Forum dürfen nur Mitglieder schreiben. Hier kannst du dich anmelden
Zum Seitenanfang Nach oben