Schneller Algorithmus zur Primfaktorzerlegung?

7 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)

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 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!

Was möchtest Du wissen?