polynominal

[pixewakb]

Ich habe gerade in der Wikipedia gelesen, dass es keinen effizienten Algorithmus zur Primfaktorzerlegung gibt (Quelle). Jetzt habe ich ein Skript geschrieben, was gefühlt sehr schnell ist und die Faktorisierungsmethode von Fermat nutzt.

Konkrete Frage: Was muss ich mir unter polynominal vorstellen?
Was ich in der WP fand, liest sich sehr kryptisch mit irgendwelchen mir unbekannten Symbolen.


PS Am Quellcode arbeite ich noch selbst, da kann ich im Moment noch keine Verbesserungen gebrauchen (Da weiß ich selbst noch nicht so richtig, was ich wo, wann, wie genau mache und da werde ich mich erst noch orientieren müssen).

[cofi]

Das Stichwort ist Wachstum von Funktionen. Nicht-polynomiell heisst, dass du keine polynomielle (d.h. der Form Σ_i y * x^i) "Kostenfunktion" angeben kannst, die - grob gesagt - die Laufzeit deiner Funktion deckelt (also schneller waechst). Hier geht es weder um eigentliche Geschwindigkeit, noch um "kleine" Zahlen. Zerlege mal eine 1024-bit Zahl und wenn du fertig bist, kannst du dich wieder melden.

[Sirius3]

@pixewakb: polynomial heißt, dass die Anzahl der Rechenoperationen die zum Finden der Lösung benötigt werden in Abhängigkeit der Größe des Problems durch ein Polynom beschrieben werden kann.

Konkret: Sortiere Zahlen in dem Du die erste Zahl mit allen anderen vergleichst, dann die zweite usw.
Bei vier Zahlen: 3+2+1=6 Vergleiche.
Oder bei n Zahlen: n*(n-1)/2 = n²/2-n/2 Vergleiche.
Ein Polynom.

Primzahlentest: Ich teste jede Zahl < Wurzel(N) ob sie N teilt.
Bei einer k-stelligen Zahl, z.B. 2143252356327 ist k=13 brauche ich also ~10^k Divisionen.
Damit ist das Problem exponentiell und nicht mehr polynomial.
Wenn ich irgendein Polynom und irgendeine Exponentialfunktion aufzeichne gibt es immer einen Punkt,
ab dem die Exponentialfunktion größer wird als das Polynom, weshalb exponentielle Probleme
schwieriger sind als Polynomiale.

Also auch wenn Dir Dein Programm schnell vorkommt, teste es mal mit einer größeren Zahl,
so ab 15 Stellen.