this post was submitted on 22 Oct 2024
13 points (100.0% liked)

Mathematik

92 readers
3 users here now

Community für Austausch zum Thema Mathematik.

Wikipedia: "Die Mathematik [...] ist eine Formalwissenschaft, die aus der Untersuchung von geometrischen Figuren und dem Rechnen mit Zahlen entstand. Für Mathematik gibt es keine allgemein anerkannte Definition; heute wird sie üblicherweise als eine Wissenschaft beschrieben, die durch logische Definitionen selbstgeschaffene abstrakte Strukturen mittels der Logik auf ihre Eigenschaften und Muster untersucht."

Verwandte Communities:

Netiquette wird vorausgesetzt. Gepflegt wird ein respektvoller Umgang - ohne Hass, Hetze, Diskriminierung.

Bitte beachtet die Regeln von Feddit.org.

Attribution

Bot-InfoSiehe https://feddit.org/post/1865816

founded 4 months ago
MODERATORS
marv99@feddit.org
13
Zahlentheorie: Es gibt eine neue größte Primzahl (www.spektrum.de)
submitted 3 weeks ago* (last edited 3 weeks ago) by marv99@feddit.org to c/mathematik@feddit.org
9 comments fedilink hide all child comments
 

Alternativer Link @Archive.ph

Das gemeinschaftliche Projekt GIMPS hat die größte bisher bekannte Primzahl hervorgebracht.

2^136279841^ −1

Nach knapp sechs Jahren intensiver Suche wurde am 21. Oktober 2024 die Zahl 2^136279841^ −1 vorgestellt, die mit 41 024 320 Dezimalstellen bislang größte bekannte Primzahl. Damit umfasst sie etwa 16 Millionen Ziffern mehr als der bisherige Rekordhalter [...]

Die neueste Primzahl läutet eine neue Ära ein, wie das GIMPS-Team in einer Pressemitteilung bekannt gibt: »Diese Primzahl beendet die 28-jährige Herrschaft der gewöhnlichen Personal Computer, die diese riesigen Primzahlen finden.« Denn als ehemaliger Nvidia-Mitarbeiter hat Durant Grafikkarten genutzt, um die umfangreichen Berechnungen durchzuführen.

Pressemitteilung: GIMPS Discovers Largest Known Prime Number: 2^136,279,841^ -1

you are viewing a single comment's thread
view the rest of the comments
[–] eunieisthebus@feddit.org 4 points 3 weeks ago

Jein. Das ist so ne Sache. Also wie GIMPS im Detail funktioniert, ist auf ihrer Seite erklärt. Hier etwas allgemeiner. Wenn du nach einer großen Primzahl suchst gehst du so vor:

  1. Wähle eine beliebige / die zu testende Zahl.

  2. Teste einfache Faktorisierungsalgorithmen ob sich ein kleiner Faktor findet. Probedivision ist ineffizient. Da gibt es bessere Algorithmen wie die verschiedene Sieb Algorithmen (quadratisches oder Zahlkörper Sieb etc.)

Wird dir irgendwann langweilig weil du nichts findest, machst du weiter mit.

  1. Führe einen PRP test durch (probable prime test) z.B. Miller-Rabin. Diese wiederholt man solange bis man entweder ein 'nicht prim' erhält oder die Wahrscheinlichkeit dass die Zahl prim ist dir hoch genug ist. Für das Beispiel miller rabin ist die Wahrscheinlichkeit dass eine nicht primzahl als 'wahrscheinlich prim' erkannt wird pro run kleiner 50% (zwei runs also 25% usw.)

In den meisten Anwendungen ist das genug und man ist zufrieden. (Im übrigen auch für den gesamten Kryptographie Kram. Also womöglich hackt sich jemand irgendwo bei dir rein weil dein private rsa key doch nicht nur zwei Primfaktoren hat ;). Wenn es genau sein muss wie auch hier in Gimps kommt:

  1. Ein Exakter Primtest. Probedivision bis zur Quadratwurzel hat exponentielle Laufzeit. Auf dem papier geht das aber praktisch unbrauchbar. Normalerweise suchst du nach einem primtest der speziell für deine Anwendung funktioniert. Im Fall von mersenne Zahlen ist das lukas-lehmer. Der Algorithmus ist auf der Seite erklärt.

Fun fact: während man zwar nicht weiß ob Faktorisierung polynomiell geht, liegt prim testen sicher in P. Es gibt den AKS primzahltest. Nur ist der ein Paradebeispiel warum Komplexitätsklassen praktisch nicht unbedingt sinnvoll sind. Die Konstanten sind so groß, dass er trotzdem 'ewig' brauch.