Bibliothek zum Faktoriesieren von Zahlen

Bengo

Gibt es eine ausreichend dokumentierte Biliothek zum Faktorisieren von Integern?
So dass ich am Ende an die Primzahlfaktorzerlegung komme?
Ich hab es mit msieve probiert, aber irgentwie finde ich die API dafür nicht.
Hat das von euch schon mal wer gemacht?
Und wie zu welcher Zahl kann man die Primzahlfaktorzerlegung in etwa bestimmen?

volkard

Welcher Zahlenbereich wird denn benötigt?

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.