Die größte bislang bekannte Primzahl

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: 2^74207281 -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:

Hallo Skeptika,

Skeptika schrieb in Beitrag Nr. 2236-1:

Hat jemand Lust, mit zu suchen?

Hier bitte:

Die Zahl 2^100000000057-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

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

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: 2^74207281 -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 log³n) bei k Tests und n Stellen.

Für Potenzkonstrukte wie n² + n + 41 oder die von Mersenne 2 ⁿ − 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.