Bibliothek zum Faktoriesieren von Zahlen

volkard

Bengo schrieb:

Ok das Problem ist folgendes:
Man nimmt eine Zahl, bildet ihre Primzahlfaktorzerlegung. Und schreibt sie sich konventionell auf. Zum Beispiel 12 = 2^23.
Erst die kleinen Primzahlen dann die grooßen.
Bei 2^23 lässt man nun die Zeichen weg und erhält 223.
Und das macht man so lang bis man zu einer Primzahl gelangt.
Die frage ist nun, ob jede Zahl zu einer Primzahl wird, oder ob es Zahlen gibt die das nicht tun.

Ok.
google mal nach: gnu factor source
Benutzt afair pollard's rho und war als ich's letzte mal reinschaute ein guter Kompromiss zwischen Schnell und Einfach.

Pollard Rho ist ziemlich langsam und funktioniert nur gut bei kleinen Primfaktoren. ECM ist da schon um einiges flexibler.

Bengo schrieb:

Klingt sehr interessant, ich glaube nämlich, dass die Antwort nein ist.

Wieso glaubst du das?

Bengo schrieb:

Wenn du dich anmelden würdest, würde ich gerne mit dir Kontakt aufnehmen

Mach ich heute Abend oder morgen.

Columbo

T.K. schrieb:

Pollard Rho ist ziemlich langsam und funktioniert nur gut bei kleinen Primfaktoren. ECM ist da schon um einiges flexibler.

<a href= schrieb:

Wikipedia">Practically speaking, ECM is considered a special purpose factoring algorithm as it is most suitable for finding small factors. Currently, it is still the best algorithm for divisors not greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time is dominated by the size of the smallest factor p rather than by the size of the number n to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general purpose techniques.

T.K. schrieb:

Bengo schrieb:

Klingt sehr interessant, ich glaube nämlich, dass die Antwort nein ist.

Wieso glaubst du das?

Eigentlich interessiert nicht, was irgendjemand glaubt oder nicht (solange er dafür nicht hinreichend Belege hat). Zeig uns doch mal deine Beweisskizze.

Arcoth schrieb:

T.K. schrieb:

Pollard Rho ist ziemlich langsam und funktioniert nur gut bei kleinen Primfaktoren. ECM ist da schon um einiges flexibler.

<a href= schrieb:

Wikipedia">Practically speaking, ECM is considered a special purpose factoring algorithm as it is most suitable for finding small factors. Currently, it is still the best algorithm for divisors not greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time is dominated by the size of the smallest factor p rather than by the size of the number n to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general purpose techniques.

Was meinst du mit dem ?

Arcoth schrieb:

T.K. schrieb:

Bengo schrieb:

Klingt sehr interessant, ich glaube nämlich, dass die Antwort nein ist.

Wieso glaubst du das?

Eigentlich interessiert nicht, was irgendjemand glaubt oder nicht (solange er dafür nicht hinreichend Belege hat). Zeig uns doch mal deine Beweisskizze.

Meinst du mich?

Columbo

T.K. schrieb:

Arcoth schrieb:

T.K. schrieb:

Pollard Rho ist ziemlich langsam und funktioniert nur gut bei kleinen Primfaktoren. ECM ist da schon um einiges flexibler.

<a href= schrieb:

Wikipedia">Practically speaking, ECM is considered a special purpose factoring algorithm as it is most suitable for finding small factors. Currently, it is still the best algorithm for divisors not greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time is dominated by the size of the smallest factor p rather than by the size of the number n to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general purpose techniques.

Was meinst du mit dem ?

Ich hab' das mit dem "langsam" überlesen. Ich dachte du implizierst dass ECM nur in dem Sinne flexibler ist, dass es nicht nur für kleine Faktoren gut funktioniert (welchem das Zitat widerspricht).

Arcoth schrieb:

Zeig uns doch mal deine Beweisskizze.

Meinst du mich?

Natürlich. Du sagst Ja, aber diese Antwort ist nicht offensichtlich.

Arcoth schrieb:

Arcoth schrieb:

Zeig uns doch mal deine Beweisskizze.

Meinst du mich?

Natürlich. Du sagst Ja, aber diese Antwort ist nicht offensichtlich.

Ich finde es offensichtlich. Nach der eindeutigen Primfaktorzerlegung gilt $n = \prod\_ip\_i^{n_i}$ . Nach $(\sum\_in\_i) - 1$ Schritten bleibt somit nur noch ein Primfaktor über.

Arcoth schrieb:

T.K. schrieb:

Arcoth schrieb:

T.K. schrieb:

Pollard Rho ist ziemlich langsam und funktioniert nur gut bei kleinen Primfaktoren. ECM ist da schon um einiges flexibler.

<a href= schrieb:

Wikipedia">Practically speaking, ECM is considered a special purpose factoring algorithm as it is most suitable for finding small factors. Currently, it is still the best algorithm for divisors not greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time is dominated by the size of the smallest factor p rather than by the size of the number n to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general purpose techniques.

Was meinst du mit dem ?

Ich hab' das mit dem "langsam" überlesen. Ich dachte du implizierst dass ECM nur in dem Sinne flexibler ist, dass es nicht nur für kleine Faktoren gut funktioniert (welchem das Zitat widerspricht).

Genaueres findet man unter http://matheplanet.com/matheplanet/nuke/html/article.php?sid=1163

Columbo

T.K. schrieb:

Genaueres findet man unter http://matheplanet.com/matheplanet/nuke/html/article.php?sid=1163

Vielen Dank für den Link, der ist gut.

SG1

T.K. schrieb:

Nach der eindeutigen Primfaktorzerlegung gilt $n = \prod\_ip\_i^{n_i}$ .

Ja.

Nach $(\sum\_in\_i) - 1$ Schritten bleibt somit nur noch ein Primfaktor über.

Wieso?

SG1 schrieb:

T.K. schrieb:

Nach der eindeutigen Primfaktorzerlegung gilt $n = \prod\_ip\_i^{n_i}$ .

Ja.

Nach $(\sum\_in\_i) - 1$ Schritten bleibt somit nur noch ein Primfaktor über.

Wieso?

Weil nach jedem Schritt ein Primfaktor abgespalten wird.

Columbo

T.K. schrieb:

Nach $(\sum\_in\_i) - 1$ Schritten bleibt somit nur noch ein Primfaktor über.

Ich glaub du redest von einem anderen Problem. Das kann ich nicht nachvollziehen.
$15 = 3\cdot 5$
$35 = 5\cdot 7$
$57 = 3\cdot 19$
$319 = 11\cdot 29$
1129 ist zwar eine Primzahl, wir haben hier jedoch vier Schritte gebraucht um diese zu erreichen, wo du doch einen garantiert hast. Im Übrigen begreife ich die Logik nicht.

volkard

Arcoth schrieb:

Zeig uns doch mal deine Beweisskizze.

Wir nehmen wirklich große Nicht-Primzahlen an, die schon eine Weile das Spiel gespielt haben, um so groß zu werden.
Die Zahl z habe 1000 Stellen.
Sie kann nur wachsen, wenn ein Teiler t so doof ist, daß len(t)+len(z/t)>len(z).
Also wenn sie einen kleinen Primfaktor hat wie 3, 7 oder 11.
2 kann nicht sein, weil z als letze Ziffern den größten Primfaktor des Vorgängers hat. Darum auch nicht 4, 5, 6 oder 8.
So große Zahlen schrumpfen also wieder.
Und weil sie nicht weiter wachsen können, fallen sie zwangsläufig irgendwann auf eine Primzahl.

Leider hat die Skizze zwei Lücken.
a) Das Wachstum ist nur "so für alle im Duchschnitt" begrenzt, es könnte doch eine Zahl geben, die ganz zufällig jedesmal eine 3 und z/3 ausspuckt und so immer weiter wächst.
b) Es könnte auch einen Zyklus von 17 Zahlen mit weniger als 1000 Stellen geben.

Bengo

T.K. schrieb:

Arcoth schrieb:

Arcoth schrieb:

Zeig uns doch mal deine Beweisskizze.

Meinst du mich?

Natürlich. Du sagst Ja, aber diese Antwort ist nicht offensichtlich.

Ich finde es offensichtlich. Nach der eindeutigen Primfaktorzerlegung gilt $n = \prod\_ip\_i^{n_i}$ . Nach $(\sum\_in\_i) - 1$ Schritten bleibt somit nur noch ein Primfaktor über.

Leider nicht ganz richtig. Es kann passieren, dass eine Zahl in einen Zyklus gerät. Zum Beispiel:
a -> b -> c -> b -> c -> b. Wird nie eine Primzahl.
Ich habe keine Ahnung, wie wahrscheinlich so ein Zyklus ist, aber bei unendlich vielen Zahlen kann es ja durchaus einen geben. Und nach so einem will ich mit meinem Programm suchen. Bisher ohne Erfolg (aber auch ohne schnelle Faktorisierung).

Die andere sehr unwahrscheinliche Möglichkeit ist, dass die Folge unendlich weiter geht, aber nie auf eine Primzahl stößt. Das ist unwahrscheinlich, weil die Zahl maximal etwa 2 Stellen pro Iteration gewinnen kann, die Primzahlen aber deutlich dichter liegen.

Noch eine andere Frage: Wenn ich eine Funktion hätte, die mir einen Faktor einer zahl ausgibt, wie mache ich darauf am besten die Primzahlfaktorzerlegung?

volkard

Bengo schrieb:

Noch eine andere Frage: Wenn ich eine Funktion hätte, die mir einen Faktor einer zahl ausgibt, wie mache ich darauf am besten die Primzahlfaktorzerlegung?

Habs damals rekursiv gemacht.

void spalte(bigint zahl,vector<bigint>& faktoren){
   if(istPrim(zahl))
      faktoren.push_back(zahl);
   else{
      f1=pollard(zahl);
      f2=zahl/f1;
      //fussnote
      spalte(f1,faktoren);
      spalte(f2,faktoren);
   }
}

//fussnote: spalte hat schon eine logarithmisch beschränkte Rekursionstiefe, aber wer Muffensausen hat, kann da gerne ein if(f1<f2)swap(s1,f2); machen und den zweiten spalte-Aufruf durch zahl=f2;goto anfang; ersetzen, dann isser sogar logarithmisch mit der Stellenzahl, wenn ich mich nicht irre.

volkard

Hab ein wenig getestet.
Also die 20 hats schon in sich:
20=2^25
225=3^2*52
3252=2^2*3*271
223271=297699
297699=399233
399233=715623
715623=3*263*907
und so weiter…

volkard schrieb:

Benutzt afair pollard's rho und war als ich's letzte mal reinschaute ein guter Kompromiss zwischen Schnell und Einfach.

Naja, bin mit pollard-rho ruck zuck an die Grenzen meines Rechner gekommen.

Bengo schrieb:

Das ist unwahrscheinlich, weil die Zahl maximal etwa 2 Stellen pro Iteration gewinnen kann, die Primzahlen aber deutlich dichter liegen.

43467514876394875501133442699882620583081205227=
3^2*101*189437*3310762051*6411638533*11891567953317269293->
321011894373310762051641163853311891567953317269293
Vier Stellen gewonnen.

volkard schrieb:

Sie kann nur wachsen, wenn ein Teiler t so doof ist, daß len(t)+len(z/t)>len(z).
Also wenn sie einen kleinen Primfaktor hat wie 3, 7 oder 11.

Das müssen keine kleinen Primfaktoren sein.
101538353409718995449=10007*10009*10037*10039*10061 =>
1000710009100371003910061

Deine Bedingung ist also weder hinreichend noch notwendig.

volkard

Leider gibt es auch Zahlen, die stark verlieren.

1076540344177317317=83^3*1882764638191->
8331882764638191

1121258912099531021=58147^2*331628069
581472331628069

Das liegt an dieser willkürlichen ^q-Regel. Hast du ein konkretes Beispiel mit verschiedenen Primzahlen, das schrumpft?

volkard schrieb:

2 kann nicht sein, weil z als letze Ziffern den größten Primfaktor des Vorgängers hat.

Der kann aber mehrmals auftreten (z.B. 2 mal) und dann ist eine 2 wiederum möglich.