Wofür sind Primzahlen gut … und anderes Zeug

Wie üblich gilt, wenn jemand etwas nicht versteht Fragen! Fangen wir mal mit dem einfachen Teil an:

Bei https://www.mersenne.org/primes/ finden wir:

Die 52te (Vorläufige Numme) Mersenne Primzahl ist 2^136279841 -1 und hat 41.024.320 stellen. Man kann sie (Achtung direkter Donwload) hier https://www.mersenne.org/primes/digits/M136279841.zip
herunterladen.

38.335.677 perfect136279841.zip # Original aus dem Download
83.689.614 p136279841.txt # Originaldatei
82.869.127 p136279841.unix.txt. # cr/lf -> lf (aka unix Format)
36.450.268 p136279841.txt.bz2 # Ergebnis von bzip2 -9 p136279841.txt

Das beantwortet einige der Fragen vov @*******dtWe schonmal ganz gut:
> Kann an die 80M Primzahl eigentlich zippen
Klar, weil sei nur aus den Ziffern 0-9 und cr/lf bestehen lässt sich die Datei
loker auf unter die Hälfte de Größe eindampfen. das normale Zip und
bzip2 suchen auch nach Wiederholungen und in 80MByte finden sich bestimmt einige.

> Gibt es sich wiederholende Ziffernblöcke?
Muss es wohl geben

> Sind die Ziffern gleichverteilt?
DAS ist eine Frage die wirklich schwierig ist, ich hoffe ich finde dazu später noch mehr.

Nach etwas mehr Nachdenken fällt auf. Warum muss man die Datei eigentlich komprimieren?
Wenn man die Zahl haben will mus man doch nur "2^136279841 -1" ausrechnen.

Mal den "Taschenrecher" hier am Mac fragen,

Das geht besser: mal schauen https://github.com/lcn2/calc/blob/master/README.md

calc 2^136279841 -1 # läuft noch ... ich melde mich wieder wenn das fertig ist ...

OOps gleich den ersten Fehler entdeckt,

ich habe die "perfekte" Zahl heruntergeladen (Muss ich das auch erklären ) nicht die eigentliche Primzahl, also nochmal
stat -f "%Z %N" M136279841.zip m136279841.txt
19.178.338 M136279841.zip # Original aus dem Download
41.844.808 m136279841.txt # Originaldatei
41.024.321 m136279841.stripped # alle cr/lf entfernt
18.225.764 m136279841.txt.bz2 # Ergebnis von bzip2 -9 m136279841.txt

Das oben gesagte gilt auch für das Original

der calc Befehl läuft noch immer, Geduld du haben musst!

bc https://www.gnu.org/software/bc/ ist schneller!

time bc -e "2^136279841-1" > calc.bc.out
bc -e "2^136279841-1" > calc.bc.out 305.42s user 5.73s system 99% cpu 5:11.26 total

nach Anpassung des Ausgabeformats:
diff m136279841.stripped calc.bc.out # Kein output, also identisch.

ls -l /usr/bin/bc
... 350.352 Oct 22 09:49 /usr/bin/bc # also < 400k

Die "effektivste" Darstellung ist dann die Neuberechnung (wenn man nicht calc verwendet )

Habe calc nach 1:41:34.20 gekillt - hätte nicht gedacht das das so ein Unterschied ist,

Die Wikipedia ist schon aktualisiert und hat "unsere" Primzahl schon:
https://de.wikipedia.org/wiki/Primzahl#Gr%C3%B6%C3%9Fte_bekannte_Primzahl

@*****_00 die Seite beantwortet evtl. einige deine Fragen,
aber das zu lesen is harter Stoff, sogar für mich .

Ich versuche mal die Salamitaktik und schneide mal Scheiben von Thema ab.

Aber bitte gebt mir Rückmeldungen ob das überhaupt jemanden interessiert...

Na gut, dank etwas Motiviation gehts weiter:

Eine der interessantestesn Arten in der Mathematik etwas zu beweisen ist der "Beweis durch Widerspruch". Angenommen ein Aussage A ist wahr und man kann daraus folgern, das A nicht gültig ist, kann A nicht wahr sein. Also gilt das Gegenteil von A.

Die alten Griechen, genauer gesagt Euklid von Alexandria, https://de.wikipedia.org/wiki/Satz_des_Euklid haben das schon bewiesen, wenn auch nicht so elegant wie man das heute in der Mathematik macht.

Deswegen wird der Beweis gerne schon früh in der Schule gelehrt:

Angenommen, es gäbe nur endlich viele Primzahlen, etwa p1 , … , pr. Die Zahl (p1 * p2 * ⋯ * pr + 1) kann aber durch keine der Zahlen p1 , … , pr geteilt werden -> d.h es gibt unendlich viel Primzahlen.

Beispiel: Angenommen nur 2, 3 und 5 sind Primzahlen. Mit Euklids Methode ergibt sich

2 ⋅ 3 ⋅ 5 + 1 = 31 und 31 ist auch eine Primzahl.

Das Konzept von "unendlich" kannten die Griechen nicht und auch in der heutigen Mathematik muss man aufpassen was genau dieses "unendlich" denn ist.

Apropos Programmieraufgaben. Ein anderer alter Griche, Eratosthenes hat sich eine Methode ausgedacht
mit der man Primzahlen aus den normalen Zaheln aussieben kann https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
Damit kommt man "Monsterprimzahlen" wie oben schon längts nicht mehr bei.
Dafür wird es immer wieder gerne in Mathematik und Informatik benutzt um mal einen Algorithmus "richtig" zum implementieren. Ich habs wohl mindestens 2 mal gemacht. Die Mustlerlösung gibt es inzwischen hier: https://github.com/kimwalisch/primesieve/blob/master/README.md

Das ist dann schon ein Stresstest für eine Computer, der CPU und Speicher optimal ausnutzt. Aber immer nur bis maximal 2^64. Mehr geht mit aktuellen Computern (mit diesem Algorithmus) nicht...

primesieve --cpu-info
XXXXXXXXX
Logical CPU cores: 10
L1 cache size: 64 KiB
L2 cache size: 4096 KiB
L1 cache sharing: 1 thread
L2 cache sharing: 2 threads

% primesieve -S
Started CPU stress testing using 10 threads.
The expected memory usage is: 10 threads * 3.30 MiB = 33.00 MiB.
The stress test keeps on running until either a miscalculation occurs
(due to a hardware issue) or the timeout of 24h expires.
You may cancel the stress test at any time using Ctrl+C.

[Nov 20 11:05] Thread 9, 23.29 secs, PrimePi(1e13+ 0e11, 1e13+ 1e11) = 3340141707 OK

Achtung auf Laptops: das saugt euren Akku ruckzuck leer…
Euren Desktop Rechner könnt ihr dann als Heizug benutzen

@****ggi UND hat du mal gefragt?

Ich bin @*****_00 Noch eine Antwort schuldig zu "Wofür sind Primzahlen gut, ausser für Verschlüsselung?"

ALSO, Kryptographie / Verschlüsselung https://de.wikipedia.org/wiki/Kryptographie
behandelt das bearbeiten von Daten (also Bilder, Texten, was auch immer),
So dass sie nur für bestimmte Empfänger lesbar sind. Eine einfache Variante verwendet
symetriche Schlüssel. Mti +/- demselben Schlüssel kann man etwas ver- und entschlüsseln.

Asymetrische Verschlüssung ist komplizierter, aber auch sicherer:
https://de.wikipedia.org/wiki/Kryptographie#Asymmetrische_Kryptosysteme_(Public-Key-Kryptographie)

Der Trick besteht darin, dass es eine "Falltürfunktion" F(x) -> y gibt.
Die eine Richtung geht relativ einfache die Andere ^F(y) -> x ist viel viel viel Schwieriger zu berechnen.

z.B. F lässt sich in 10s berechen aber ^F benötigt 100 Jahre (oder so)

Hat das was mit Primnzahlen zu tun? bis hierher nicht. -> https://de.wikipedia.org/wiki/Einwegfunktion

Aber Die Primfaktozerlgeung eine großen (richtig Grpßen) Zahl die aus zwei (richtig Grpßen)
Primzahlen p und q besteht ist so eine Funktion.

Und damit sind bei RSA angekommen https://de.wikipedia.org/wiki/RSA-Kryptosystem.

Wenn das reicht würde ich den Thread hiermit beenden.

Wer mehr wissen will bitte