Primfaktorzerlegung

Neue Frage »

Felix1 Auf diesen Beitrag antworten »
Primfaktorzerlegung
Hallo,
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
kiste Auf diesen Beitrag antworten »

4935929110827149324961049739*4938521104504949308801118647 berechnet mit Maxima
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
AD Auf diesen Beitrag antworten »

@kiste

Mal interessehalber, da ich "Maxima" bisher nicht kenne: Wie lange hat diese Faktorisierung gedauert?
Ivan33 Auf diesen Beitrag antworten »

@Arthur Dent

Ich kenne Maxima auch nicht. Aber ich kann dir sagen, wie lange es bei mir gedauert hat.

Zitat:

Factorization complete in 0d 0h 0m 18s
ECM: 2185028 modular multiplications
Prime checking: 50760 modular multiplications
SIQS: 11601 polynomials sieved
33371 sets of trial divisions
1312 smooth congruences found (1 out of every 588680 values)
15065 partial congruences found (1 out of every 51267 values)
1455 useful partial congruences

Timings:
Primality test of 3 numbers: 0d 0h 0m 0.2s
Factoring 1 number using ECM: 0d 0h 0m 3.7s
Factoring 1 number using SIQS: 0d 0h 0m 14.6s


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.
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)
 
 
Ivan33 Auf diesen Beitrag antworten »

Mein Rekord wurde gebrochen.

Zitat:
Primality test of 3 numbers: 0d 0h 0m 0.0s
Factoring 1 number using ECM: 0d 0h 0m 3.1s
Factoring 1 number using SIQS: 0d 0h 0m 13.3s


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
Abakus Auf diesen Beitrag antworten »

Das sieht ja nach einen äußerst interessanten Programm aus, hier mal die gesamte Ausgabe:

Zitat:
Elliptic Curve Method factorization Written by Dario Alejandro Alpern ([email protected])

24 376190 084160 225830 282987 324250 699966 741390 106607 383133 = 4935 929110 827149 324961 049739 x 4938 521104 504949 308801 118647

Number of divisors: 4

Sum of divisors: 24 376190 084160 225830 282987 334125 150182 073488 740369 551520

Euler's Totient: 24 376190 084160 225830 282987 314376 249751 409291 472845 214748

Moebius: 1

Sum of squares: a^2 + b^2 + c^2
a = 4795 616168 396042 398512 047996
b = 1173 991332 837975 830296 923021
c = 26

Factorization complete in 0d 0h 0m 9s
ECM: 2185028 modular multiplications
Prime checking: 50760 modular multiplications

SIQS:
11601 polynomials sieved
33371 sets of trial divisions
1312 smooth congruences found (1 out of every 588680 values)
15065 partial congruences found (1 out of every 51267 values)
1455 useful partial congruences

Timings:
Primality test of 3 numbers: 0d 0h 0m 0.0s
Factoring 1 number using ECM: 0d 0h 0m 1.7s
Factoring 1 number using SIQS: 0d 0h 0m 7.2s


Grüße Abakus smile
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?
Ivan33 Auf diesen Beitrag antworten »

Klar!

Zitat:
Factorization complete in 0d 0h 25m 25s
ECM: 1042030861 modular multiplications
Prime checking: 50760 modular multiplications

Timings:
Primality test of 3 numbers: 0d 0h 0m 0.2s
Factoring 1 number using ECM: 0d 0h 25m 25.3s


Der 1. Faktor wurde bei der 366. Kurve entdeckt. Der 2. ergab sich dann durch die Division.
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

Zitat:
Original von Ivan33
ECM ist die beste Methode um große Zahlen in Faktoren zu zerlegen.


und dich zu einem Widerruf zwingen, was mir aber offenbar nicht gelungen ist... unglücklich
Ivan33 Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Ah, danke... Aber eigentlich wollte ich dir damit nur drastisch vor Augen führen, dass du weiter oben einen Unsinn geschrieben hast, nämlich

Zitat:
Original von Ivan33
ECM ist die beste Methode um große Zahlen in Faktoren zu zerlegen.


und dich zu einem Widerruf zwingen, was mir aber offenbar nicht gelungen ist... unglücklich


Ach so... Naja, dass ich Unsinn geschrieben habe, habe ich seit dem trotzdem gewusst. Dann habe ich ECM (Faktorzerlegung) mit ECPP (Primzahltest) verwechselt.

Zitat:
ECPP is the fastest known general-purpose primality testing algorithm.

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).
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...
kiste Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
@kiste

Mal interessehalber, da ich "Maxima" bisher nicht kenne: Wie lange hat diese Faktorisierung gedauert?

Späte Antwort aber immerhin Augenzwinkern
Waren knapp 3min also nicht wirklich schnell
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »