Schneller Algorithmus zur Primfaktorzerlegung?
Angenommen, es gibt natürliche Zahlen mit jeweils mehreren unterschiedlichen Zerlegungen, dann auch wieder eine kleinste, genannt n. Dies kann keine Primzahl sein und zwei Zerlegungen von n können keinen gemeinsamen Primfaktor p enthalten, da dann auch n / p zwei verschiedene Zerlegungen hätte und kleiner als n wäre, im Widerspruch zur Annahme, dass n minimal ist. Es gilt also etwa n = p * a= q * b, wobei p und q Primzahlen sind, und es gilt p ungleich q, a ungleich b. Das abschließende Argument ist das Lemma von Euklid: Teilt eine Primzahl ein Produkt, so auch einen der Faktoren. Da n durch p teilbar ist, muss einer der Faktoren der anderen Zerlegung durch p teilbar sein und das ist b, denn q ist prim. Also taucht ein beliebiger Primfaktor stets in beiden Zerlegungen auf und damit sind sie identisch.
6 Antworten
Mit deinem Argument beweist du, dass es zu jeder Zahl eine eindeutige Primfaktorzerlegung gibt, das ist soweit mal richtig.
Daraus folgerst du (in einem Kommentar), dass es einen Algorithmus gibt, der ihn berechnet. Diese Folgerung ist jedoch falsch. Es ist nicht ganz einfach das zu sehen, es ist ein Beweis aus der theoretischen Informatik. Ein Beispiel ist die Berechnung der Kolmogorov-Komplexität (http://de.wikipedia.org/wiki/Kolmogorow-Komplexit%C3%A4t). Jede Zahl hat eine eindeutige solche Komplexität, jedoch kann man sie nicht mt einem Algorithmus finden.
Bei dir klappt es aber, es gibt Algorithmen, die die Primfaktorzerlegung berechnen. Diese sind aber alle langsam. Langsam bedeutet, dass wenn du eine Primzahl nimmt, die doppelt so viele Stellen hat, dann dauert die Berechnung (schlimmstenfalls) exp(2) mal so lange. Es ist nicht bewiesen, dass dies so sein muss, es ist das grösste offene Problem in der theoretischen Informatik, ob es einen schnellen Algorithmus gibt, der Primfaktoren zerlegt (suche mal unter P=NP, wenn du einen schnellen Algorithmus hast, dann beweist du automatisch dieses Problem).
Wieso ist es ein Problem, dass die Primfaktorzerlegung so lange geht?
Das kannst du relativ gut selber ausprobieren. Berechne mal von grossen Zahlen die Quardatzahl (x^2), dies ist ein schneller Algorithmus (quadratische Laufzeit). Berechnest du hingegen x!, so hast du ein Problem mit ähnlicher Geschwindigkeit wie die Primfaktorzerlegung (exponentielle Laufzeit).
Probiers mal aus mit "kleinen" (1514) und "grossen" Zahlen (13462457)
Was ist denn deine Frage? Wenn ich dich richtig verstehe, versuchst du gerade zu beweisen, dass die Primfaktorzerlegung einer Zahl eindeutig ist. Wie willst du bitte daraus eine Primfaktorzerlegung gewinnen??? Du hast ja nur gezeigt, dass sie eindeutig ist, aber das hilft dir doch bei der Bestimmung der Zerlegung nicht weiter. Oder was ist genau dein Ziel?
Eine klare Frage würde helfen, dir klare Antworten zu geben!
Zu deiner Frage (der darunter stehende Text ist keine Frage), die auch einen kryptographischen Hintergrund hat, sieh dir mal http://de.wikipedia.org/wiki/Faktorisierungsverfahren an. In Kürze: Es gibt keine wirklich effizienten Faktorisierungsverfahren.
Lt. Wikipedia: Die besten bekannten Algorithmen sind das 1981 von Carl Pomerance erfundene Quadratische Sieb, das um 1990 von mehreren Mathematikern (u.a. John M. Pollard, Arjen Lenstra, Hendrik Lenstra Jr., Mark S. Manasse, Carl Pomerance) gemeinsam entwickelte Zahlkörpersieb und die Methode der Elliptischen Kurven, die 1987 von Hendrik W. Lenstra, Jr. vorgestellt wurde.
Weiter viel Spaß....
Was bitte ist eine Zerlegung? Wieso ist diese eindeutig? Wer sagt, p und q seien Primzahlen?
2 hoch 128 z.B. lässt sich zerlegen in Beispielsweise 8 * 2 hoch 125 genauso wie 64 * 2 hoch 122.Wende deine Regeln drauf an.
Damit beweist du keinesfalls, dass es einen "schnellen" Algorithmus nur Primfaktorzerlegung gibt.