Primfaktorzerlegung |
14.11.2008, 20:38 | Felix1 | Auf diesen Beitrag antworten » | ||||||
Primfaktorzerlegung ich habe dieses Forum auf der Suche für eine Lösung einer Aufgabe mit einer Primfaktorzerlegung entdeckt. Ich kann zwar Primfaktoren ermitteln, aber diese Zahl übersteigt bei weitem mein Berechnungsvermögen. Ich hoffe ich bekomme einen Ansatz, wie ich diese Zahl zerlegen kann. Am liebsten wäre mir natürlich eine Softwareempfehlung, die mir die Arbeit abnimmt. Die Zerlegung brauche ich um Koordinaten für einen Geocache zu ermitteln. Die Zahl (56 Stellen) 24376190084160225830282987324250699966741390106607383133 Felix |
||||||||
14.11.2008, 21:01 | kiste | Auf diesen Beitrag antworten » | ||||||
4935929110827149324961049739*4938521104504949308801118647 berechnet mit Maxima |
||||||||
14.11.2008, 21:13 | Felix1 | Auf diesen Beitrag antworten » | ||||||
Hallo kiste, herzlichen Dank für die rasche Antwort. Werde dir auch noch kurz eine email senden, für was ich das genau benötige. Grüße und Danke felix |
||||||||
14.11.2008, 22:05 | AD | Auf diesen Beitrag antworten » | ||||||
@kiste Mal interessehalber, da ich "Maxima" bisher nicht kenne: Wie lange hat diese Faktorisierung gedauert? |
||||||||
21.09.2009, 14:41 | Ivan33 | Auf diesen Beitrag antworten » | ||||||
@Arthur Dent Ich kenne Maxima auch nicht. Aber ich kann dir sagen, wie lange es bei mir gedauert hat.
http://www.alpertron.com.ar/ECM.HTM ECM ist die beste Methode um große Zahlen in Faktoren zu zerlegen. Mein Prozessor hat 2,93 GHz und ist ca. 3 Jahre alt. |
||||||||
21.09.2009, 17:23 | Manus | Auf diesen Beitrag antworten » | ||||||
Maple 12 benötigt bei mir ca 12 Sekunden. 4GB Ram, Ein 2x3,0 GHZ Dualcore (Maple war allerdings nicht das einzige Programm was lief und Maple hat - soweit ich weiß - keine Dualcore-Unterstützung) |
||||||||
Anzeige | ||||||||
|
||||||||
21.09.2009, 18:05 | Ivan33 | Auf diesen Beitrag antworten » | ||||||
Mein Rekord wurde gebrochen.
Insgesamt also 16,4 Sekunden. Schneller geht's bei meinem PC wirklich nicht. Er ist auch ein bisschen abgenutzt, wegen den vielen Rechenoperationen, o. Ä. Ich mache schließlich bei factorDB mit und da habe ich es mit ganz großen Faktoren zu tun. Desweiteren lasse ich meinen PC an, wenn es nicht nötig ist. Aber eigentlich läuft mein PC mit normaler Geschwindigkeit. Ich hatte einige Stunden Prime95 am Laufen und mein PC ist nicht abgestürzt. Vielleicht liegt es nicht am PC sondern am Programm. Vielleicht läuft Maple 12 schneller als Programme mit Java. Für Wolfram|Alpha ist die Zahl zu groß. Mich würde es mal interessieren, wie lange die Faktorzerlegung bei euch mit diesem Programm dauert: http://www.alpertron.com.ar/ECM.HTM |
||||||||
21.09.2009, 22:47 | Abakus | Auf diesen Beitrag antworten » | ||||||
Das sieht ja nach einen äußerst interessanten Programm aus, hier mal die gesamte Ausgabe:
Grüße Abakus |
||||||||
22.09.2009, 09:06 | Mystic | Auf diesen Beitrag antworten » | ||||||
Wäre interessant, wie lange das Programm mit der ECM für die Faktorisierung benötigt... Ich bin hier leider nicht auf meinem eigenen Computer um das testen zu können. Kann das mal jemand machen, indem er einfach das Kästchen "Automatic switch to SiQS" ausklickt? |
||||||||
22.09.2009, 12:34 | Ivan33 | Auf diesen Beitrag antworten » | ||||||
Klar!
Der 1. Faktor wurde bei der 366. Kurve entdeckt. Der 2. ergab sich dann durch die Division. |
||||||||
22.09.2009, 13:23 | Mystic | Auf diesen Beitrag antworten » | ||||||
Ah, danke... Aber eigentlich wollte ich dir damit nur drastisch vor Augen führen, dass du weiter oben einen Unsinn geschrieben hast, nämlich
und dich zu einem Widerruf zwingen, was mir aber offenbar nicht gelungen ist... |
||||||||
22.09.2009, 17:54 | Ivan33 | Auf diesen Beitrag antworten » | ||||||
Ach so... Naja, dass ich Unsinn geschrieben habe, habe ich seit dem trotzdem gewusst. Dann habe ich ECM (Faktorzerlegung) mit ECPP (Primzahltest) verwechselt.
Quelle: Weisstein, Eric W. "Elliptic Curve Primality Proving." Von MathWorld http://mathworld.wolfram.com/EllipticCur...ityProving.html Ach ja: Wenn du eine sehr große nullfreie Zahl eingibst (genauer gesagt eine 100-stellige, dessen erster Faktor 40 Stellen enthält), wird SIQS im Programm nicht eingesetzt. Liegt es vielleicht daran, dass SIQS für große Zahlen nicht geeignet ist? Wenn ja, dann ist ECM soweit ich weiß die schnellste Faktorzerlegungsmethode für große Zahlen (EDIT: Das habe ich ja bereits geschrieben! Dann hatte ich also vielleicht doch recht!). Zumindest schneller als die Pollard-rho- und Pollard-p-1-Faktorzerlegungsmethode (laut MathWorld). |
||||||||
22.09.2009, 18:57 | Mystic | Auf diesen Beitrag antworten » | ||||||
Ich hätte ja auch nichts dagegen gehabt, wenn du geschrieben hättest, dass ECM oft die beste Methode um große Zahlen in Faktoren zu zerlegen. Ihre Laufzeit hängt halt im Unterschied zum SIQS stark davon ab, wie groß der kleinste Primfaktor p der zu faktorisierenden Zahl ist. Sie ist vor allem dann sehr effizient, wenn dieser für die Pollard'sche rho-Methode bereits zu groß aber für das Quadratische Sieb bzw. das Zahlkörpersieb noch zu klein ist. Diese Lücke füllt sie perfekt aus. Außerdem spielt auch "Glück" so komisch es klingen mag, bei der ECM eine enorme Rolle, das beginnt etwa bei einem p mit mehr als 40 Stellen. (Siehe dazu etwa http://www.loria.fr/~zimmerma/records/p67 für den derzeitigen Rekord mit 67 Stellen, ein enormer "Glückstreffer"!) Für die wirklich harten Faktorisierungsprobleme, wie sie z.B. bei RSA-Moduln n auftreten, kann man die ECM allerdings vergessen und übrigens auch SIQS, da kommt dann nur mehr das Zahlkörpersieb in Frage, siehe z.B. http://www.loria.fr/~zimmerma/records/rsa200 Zusammenfassend hat also ECM durchaus seine Meriten, aber dass sie, wie von dir nochmals behauptet, die "schnellste Faktorzerlegungsmethode für große Zahlen" sei, kann in dieser Form und ohne Einschränkungen sicher nicht aufrechterhalten werden... Gerade das Beispiel, um das es in diesem Thread geht, zeigt das ja sehr deutlich... |
||||||||
22.09.2009, 23:20 | kiste | Auf diesen Beitrag antworten » | ||||||
Späte Antwort aber immerhin Waren knapp 3min also nicht wirklich schnell |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|