Primfaktorzerlegung großer Zahlen?
Habt ihr irgendwelche Tipps: Wie man schneller an die Primfaktorzerlegung von größeren zahlen rank kommt.
Bsp:
21746
9 Antworten
So!
http://www.wolframalpha.com/input/?i=factorize(21746)
Problematisch ist immer, wenn man den Befehl nicht zur Hand hat:
factorize(21746)
Es gibt verschiedene Arten von Zahlen, die mit unterschiedlichen Verfahren
( https://de.wikipedia.org/wiki/Faktorisierungsverfahren )
unterschiedlich schnell zerlegbar sind:
a) zuerst werden die kleinen Faktoren bis etwas über 1 Mio.per Modulo Funktion (Divisionsrest von bekannten Primzahlen) herausgefiltert
21746 mod 2 =0
mod 83 =0
mod 131=0 -> womit man schnell die 3 Faktoren gefunden hat.
b) dann kann man bei größeren Faktoren nach Carmichael-ähnliche Zahlen suchen, die bis 600 Stellen und Faktoren bis über 270 Stellen in wenigen Sekunden zu finden sind:
: http://www.lamprechts.de/gerd/php/Carmichael-Zahl-Faktorisierer.php
Dort sieht man noch 3 weitere, wobei die RSA-Zahlen die schwersten von allen sind. Da gibt es welche mit weniger als 270 Stellen, die bis heute nicht in ihre 2 Faktoren zerlegt wurden!
Fermat & Mersenne lese: https://de.wikipedia.org/wiki/Fermat-Zahl
https://de.wikipedia.org/wiki/Mersenne-Zahl
(letzterer am schnellsten -> deshalb dort die Weltrekorde von zig Mio. Stellen. )
c) lieferten Tests in absehbarer Zeit keine Ergebnisse, kann man mit PRP-Primzahltests bis 5000 Stellen relativ schnell sagen, ob es zu 99,9999999999% eine Primzahl ist.
Liegt immer noch keine schnelle Lösung vor, kommt man zum:
d) schnellsten und kompliziertesten Verfahren für große Faktoren:
https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization
was man online hier findet: https://www.alpertron.com.ar/ECM.HTM
Hätte man 600stellige Carmichael-ähnliche Zahlen mit 2 Faktoren über 270 Stellen gleich hiermit versucht, könnte es über 6 Stunden dauern -> da ist der Carmichael-Faktorisierer schneller (wenige Sekunden).
reicht für heute.
Wenn es Dich wirklich interessiert, kannst Du ja noch genauer nachfragen
(habe einige Rekorde ...)
Wenn du einen großen Aufwand bei der Primfaktorzerlegung verspürst, machst du erste Bekanntschaft mit der aktuellen Basis fast aller aktueller Verschlüsselungsmethoden. Diese basieren nämlich darauf, dass die Primfaktorzerlegung "aufwendig" ist.
Aber zu deiner Zahl. Ich würde wiefolgt vorgehen:
- Gerade Zahl: Primfaktor 2: 2 x 10873
- Bei 10873 greifen keine Teilbarkeitsregeln bis 10.
- alle Primzahlen durchprobiert bis 83: 2 x 83 x 131
- Bei 131 greifen keine Teilbarkeitsregeln bis 10.
- alle Primzahlen durchprobiert bis 131:
2 x 83 x 131 ist also die Lösung. Das ist nicht befriedigend auf der einen Seite. Auf der anderen Seite solltest du froh sein, dass jedesmal, wenn du "https" in der Adressleiste deines Browsers, deine Daten nur verschlüsselt auf Basis extrem großer Primzahlen übertragen werden.
Hallo,
die schnelle Zerlegung von großen Primzahlen ist ein Problem in der Mathemtik, für das es bisher keine gute Lösungen existieren.
Algorithmen sind entweder langsam oder nicht perfekt genau.
Deine Zahl zählt hierbei aber nicht wirklich als "große" Zahl.
Bei einer 5-stelligen Zahl ist eine Primfaktorzerlegung teilweise im Kopf, sicher mit Stift und Papier und in Sekunden mit Wolfram Alpha machbar:
http://www.wolframalpha.com/input/?i=is+21746+prime
- Suche der Primzahllücken mit n!+m für die gewünschte Lückenbreite
- Faktorisierung zwischen den Lücken
Mit der Verinselung von Primzahlfeldern kann man im Bereich der großen Zahlen Zeit einsparen. Allerdings hat man diese Zeit zuvor mit einem Multiplikations- und Additionsverfahren schon geleistet. Der zweite Untersucher profitiert allerdings von dieser Kartografie des Ozeans der Zahlen.