Grosse Primzahlen

As of October 2013, the largest known prime number is 2^57885161 − 1,[1] a number with 17,425,170 digits.

Wie kann man Primzahlen mit 17 Millionen Ziffern überhaupt überprüfen?
Das kann man doch gar nicht mit 100% Wahrscheinlichkeit bestätigen, wie beweist man so etwas?
Beziehungsweise, wie kann man mit solch grossen Zahlen überhaupt rechnen?
Braucht man dafür nicht ein 4194304 Bit Computer?

Iix schrieb:Braucht man dafür nicht ein 4194304 Bit Computer?

Nein. Java z. B. kennt eine "BigInteger"-Klasse, die den Wert "zerlegt" speichert. Wie genau, kann jemand anders als ich hier nachlesen*:

http://docs.oracle.com/javase/1.4.2/docs/api/java/math/BigInteger.html (Archiv-Version vom 20.07.2013)

...arbitrary-precision integers. (Ganze Zahlen beliebiger Genauigkeit, würd ich sagen)

Beim schnellen Überfliegen des Eingangstextes fiel mir auf, dass die Klasse sogar genau zur Primalitäts-Prüfung(korrekt übersetzt?) und Primzahlensuche schon fertige Methoden anbietet. Ist ja eine relativ häufige Mathe-Funktionalität. Ich kenne nur Java, verwette aber diverse unappetitliche/nützliche Körperteile, dass C++, die .NET-Sprachen usw. ähnliche Einrichtungen besitzen. Wenn Java das ganze nicht eh aus C++ - Bibliotheken abgekupfert hat. :D


*Falls es da nicht steht: Wenn man ein JDK installiert hat, findet sich der Quellcode aller JDK-Klassen im Installationsverzeichnis(oder vielleicht in [Installationsverzeichnis]\bin) in der Datei "src.zip".

@Iix

Iix schrieb:As of October 2013, the largest known prime number is 2^57885161 − 1,[1] a number with 17,425,170 digits.

Wie kann man Primzahlen mit 17 Millionen Ziffern überhaupt überprüfen?
Das kann man doch gar nicht mit 100% Wahrscheinlichkeit bestätigen, wie beweist man so etwas?
Beziehungsweise, wie kann man mit solch grossen Zahlen überhaupt rechnen?
Braucht man dafür nicht ein 4194304 Bit Computer?

p=2^57885161−1 ist eine sog. Wikipedia: Mersenne-Primzahl - das sind Zahlen der Form 2^n-1. Für diese Zahlen wiederum existiert ein besonders effizienter Primzahltest, der sog. Wikipedia: Lucas-Lehmer-Test , mit dem man relativ schnell testen kann, ob diese Zahlen prim sind. Der Lucas-Lehmer-Test ist auch nicht schwierig zu coden, man braucht halt nur einen richtig guten Hochleistungsrechner und viel, viel Zeit...

Wieso rechnet man überhaupt mit so großen Zahlen? o.o
Übersteigt meine geistige Kapazitäten ..

@janine86
für die Wüssenhaft

@janine86
Große Primzahlen begegnen uns nicht unbedingt immer sichtbar im täglichen Leben,
aber indirekt umgeben sie uns immer:
Die Primzahlen sind in der modernen Technik nicht mehr weg zu denken. Durch die Primfaktorzerlegung kann man nicht nur feststellen ob es sich bei einer Zahl um eine Primzahl handelt, sie erweist auch der Kryptographie große Dienste. Onlinebanking, Kreditkarten und hochgesicherte Server werden heute auf Basis dieses Algorithmus verschlüsselt. Sogar militärische Abwehrsysteme arbeiten mit dieser Art Sicherheitsverschlüsslung. (Quelle (Archiv-Version vom 07.09.2013))

@janine86

janine86 schrieb:Wieso rechnet man überhaupt mit so großen Zahlen? o.o

Weil wir's können :-)
Hat was von Sport, wer schafft als erstes die 100 Meter in unter 9,5 Sekunden.

Grundsätzlich sind aber Primzahlen auch praktisch wichtig für Verschlüsselungen. Wenn jemand eine schnelle Methode finden würde um Zahlen in ihre Primfaktoren zu zerlegen wäre alle aktuellen Verschlüsselungsmethoden wertlos.