Bibliothek zum Faktoriesieren von Zahlen

Bengo

So groß wie möglich.
Geht um eine mathematische Frage und ich suche ein Gegenbeispiel. Deshalb wäre groß schon schön.
Hab es jetzt mal mit GMP-ECM probiert, aber ich bekomme solche Fehlermeldungen:
/home/benjamin/Downloads/ecm-6.4.4/mul_fft.c:955: Nicht definierter Verweis auf \_\_gmpn\_add\_n' //usr/local/lib/libecm.a(libecm\_la-mul\_fft.o): In Funktion__gmpn_add':

Klingt für mich, als ob die static library nicht richtig compiliert worden wäre.

Ok denke nun ich bin zu doof, das interface richtig zu verwenden.

Was genau ist ecm_params struct (*)[1]?

In der Header Datei steht folgendes:

typedef __ecm_param_struct ecm_params[1];

int ecm_factor (mpz_t, mpz_t, double, ecm_params);
void ecm_init (ecm_params);
void ecm_clear (ecm_params);

vorher wird noch __ecm_param_struct als struktur definiert. Soll das ganze verbergen, dass ich in wirklichkeit mit zeigern arbeite aber ich so tun soll, als ob nicht. Wenn ja, ist das üblich? Mir kommt es verdammt unvorteilhaft vor.

SeppJ

Bengo schrieb:

Geht um eine mathematische Frage und ich suche ein Gegenbeispiel. Deshalb wäre groß schon schön.

Wie wäre es damit, stattdessen danach zu fragen?

"Schön groß" und "so groß wie möglich" sind nämlich ziemlich doofe Größenangaben. Ich kann mir nämlich ganz schön große Zahlen vorstellen.

Bengo

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.

Am schnellsten ist das Quadratische Sieb (MPQS) und für größere Zahlen das Zahlkörpersieb (NFS). Das MPQS habe ich einmal programmiert, bei Interesse kann ich mich hier im Forum einmal registrieren und du schreibst mir eine E-Mail.

Bengo schrieb:

Die frage ist nun, ob jede Zahl zu einer Primzahl wird,

Ja.

Bengo

Klingt sehr interessant, ich glaube nämlich, dass die Antwort nein ist.
Wenn du dich anmelden würdest, würde ich gerne mit dir Kontakt aufnehmen

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?