staging.inyokaproject.org

Moin,

Falls das im falschen Unterforum ist bitte verschieben.

Meine Frage ist zu msieve, wenn ich es starte Faktorisiert es nur kleinere Zahlen sowie grosse viele Primfaktoren werden gar nicht ausgegeben, ich nutze es ohne cuda(rein auf der cpu)

Wenn zb eine grössere Zahl zum ausrechnen übergeben wird, dödeld die cpu nur auf 8% rum, selbst wenn ich mit nice die priorität und Tasksel die cpu threads erhöhe ändert sich nichts.

Ich verwende msieve zusammen mit der gmp Library gmp-6.3.0(für big Number)

kompiliert mit make x_86_64 ECM=1 # 64bit/Elyptische Kurven

Auch wenn ich den Algorithmus ändere zb auf Pollard-Rho ändert sich auch nichts, ein Beispiel:

sudo nice -n -10 taskset -c 0-7 ./msieve -v 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000111111111111111111111111111111111111111
[sudo] Passwort für heidi: 


Msieve v. 1.46
Sat Oct 26 13:10:39 2024
random seeds: 88624404 425e780d
factoring 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000111111111111111111111111111111111111111 (201 digits)
searching for 15-digit factors
P+1 stage 2 factor found
commencing quadratic sieve (167-digit input)
using multiplier of 1
using 64kb Opteron sieve core
sieve interval: 200 blocks of size 65536
processing polynomials in batches of 1
using a sieve bound of 42921959 (1299207 primes)
using large prime bound of 4294967295 (31 bits)
using double large prime bound of 218437776016143360 (51-58 bits)
using trial factoring cutoff of 58 bits
polynomial 'A' values have 17 factors

sieving in progress (press Ctrl-C to pause)

Während es läuft ist die cpu gerade mal auf 5%

Ausserdem liefert es auch sehr oft falsche Ergebnisse:

 ./msieve -v -t 8 -ECM -e 5000 1000000


Msieve v. 1.46
Sat Oct 26 13:12:55 2024
random seeds: 3b3fd1f2 4106bd7f
factoring 1000000 (7 digits)
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
elapsed time 00:00:00

Was am meisten stört ist, das selbst bei Zahlen mit 250 Digits es meisst nur die kleinen Primfaktoren ausgibt, und ein grosser zum Multiplizieren.

Nutzt das noch jemand?

Das ist ziemlich wirr... was ist den jetzt konkret die Frage bzw. das Problem? Das msieve falsch / unvollständig rechnet oder die Performance? Wenn eine Mathe-Anwendung (offensichtlich) falsch rechnet, ist der Programmcode wohl irgendwie falsch bzw. Schrott.

Außerdem würde ein Link zu msieve helfen sowie ein Beschreibung, was du vorhast. Dann könnte man ggf. auch alternative Programme vorschlagen.

Gruß, noisefloor

Und was soll an 1000000=2^6*5^6 falsch sein? Das Ausgabeformat ist vllt etwas unglücklich ☺

Gib doch bitte mal eine konkrete Eingabe, dann was du erwartest, dann was stattdessen kommt. Jede natürliche Zahl > 1 hat eine eindeutige Primfaktorzerlegung. Wenn die aus mehreren kleinen und einem großen Faktor besteht, dann ist es halt so ☺

--ks

ubuntu--anfaenger schrieb:

Was am meisten stört ist, das selbst bei Zahlen mit 250 Digits es meisst nur die kleinen Primfaktoren ausgibt, und ein grosser zum Multiplizieren.

Hast du spaßeshalber mal die FAQ auf https://github.com/radii/msieve gelesen? Erste Antwort:

On a fast modern CPU, a 110-digit factorization takes nearly 120 hours for Msieve, and the time increases steeply beyond that.

Die von dir erwähnten 250-stelligen Dezimalzahlen willst du nicht faktorisieren, weder mit msieve noch mit was anderem, außer du hast ein paar Trillionen Jahre Zeit.

Falls ich dich falsch verstanden habe, bitte stell deine Frage klarer.

--ks

Kreuzschnabel scshrieb:

Hast du spaßeshalber mal die FAQ auf https://github.com/radii/msieve gelesen? Erste Antwort:

Die von dir erwähnten 250-stelligen Dezimalzahlen willst du nicht faktorisieren, weder mit msieve noch mit was anderem, außer du hast ein paar Trillionen Jahre Zeit.

Ja das ist alles soweit klar, sonst würde ja keine Verschlüsselung mehr funktionieren.

Falls ich dich falsch verstanden habe, bitte stell deine Frage klarer.

Ich hab genau 2 Probleme(es sind keine Programm Probleme sondern eher Verständnis Probleme von mir):

1. Ich bin davon Ausgegangen, das das Programm nach jedem möglichen PrimFaktor sucht, mir ist auch klar das bei grossen Zahlen das Unmöglich wird.

Welches Programm sucht nach allen kombinationen?

zb: 100816275300000000000 = 10040730789×10040730843 kann man in diese 2Primfaktoren zerlegen. Das Programm sucht da gar nicht nach.

2. Das Programm ist Hoch Optimiert, die 250digits ist das max. mir ist klar das es trillionen von Jahren dauern würde, was ich aber nicht verstehe, warum rechnet meine cpu das nur mit 6% Prozessor Leistung?

zb:

Hallo,

Ich bin davon Ausgegangen, das das Programm nach jedem möglichen PrimFaktor sucht, mir ist auch klar das bei grossen Zahlen das Unmöglich wird.

Das ist aber falsch. Für jede natürliche Zahl > 1 gibt es nur eine Primfaktorzerlegung.

warum rechnet meine cpu das nur mit 6% Prozessor Leistung?

6% der Gesamtleistung der CPU oder 6% eines Kerns? Grundsätzlich legt das Betriebssystem fest, welche Prozesse wie viel CPU Zeit auf welchem Kern bekommen. Wie du ja selber im Ausgangspost gesagt hast, kann man das bis zu einem gewissen Grade via nice beeinflussen. Mit taskset kann man manuell festlegen, auf welche Kern ein Programm läuft. Was grundsätzlich erst mal keine Beschleunigung per se bringt.

zb: 100816275300000000000 = 10040730789×10040730843 kann man in diese 2Primfaktoren zerlegen. Das Programm sucht da gar nicht nach.

Also mit der Primefaktorzerlegung von sympy ist die Primfaktorzerlegung von 100816275300000000000 ziemlich anders:

1
2
3
4
5
6

>>> from sympy import primefactors
>>> n = 100816275300000000000
>>> res = primefactors(n)
>>> res
[2, 3, 5, 13, 25850327]
>>>

wie auch immer du darauf kommst... beide Zahlen, die du als Primfaktor nennst, sind keine Primzahlen, sondern z.B. durch 3 teilbar:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

>>> from sympy import isprime
>>> isprime(10040730789)
False
>>> isprime(10040730843)
False
>>> 10040730843/3
3346910281.0
>>> 10040730789/3
3346910263.0
>>>

Gruß, noisefloor

qalc bestätigt das:

qalc "factor(100816275300000000000)"
100816275300000000000 = 2^11 × 3 × 5^11 × 13 × 25850327

Hab mir gerade mal R angesehen, das kann mit mehreren Threads Faktorisieren:

library(gmp)
library(RcppBigIntAlgos)

> rsa79 <- as.bigz("7293469445285646172092483905177589838606665884410340391954917800303813280275279")
> quadraticSieve(rsa79, showStats = TRUE, nThreads = 16)

Summary Statistics for Factoring:
    7293469445285646172092483905177589838606665884410340391954917800303813280275279

|      MPQS Time     | Complete | Polynomials |   Smooths  |  Partials  |
|--------------------|----------|-------------|------------|------------|
|    1m 18s 683ms    |   100%   |    91221    |    5651    |    7096    |

|  Mat Algebra Time  |    Mat Dimension   |
|--------------------|--------------------|
|      13s 547ms     |    12623 x 12747   |

|     Total Time     |
|--------------------|
|    1m 32s 891ms    |

Big Integer ('bigz') object of length 2:
[1] 848184382919488993608481009313734808977 
[2] 8598919753958678882400042972133646037727

mit nThreads = 1 verlängert sich der Zeitaufwand entsprechend:

|     Total Time     |
|--------------------|
|    10m 18s 562ms   |

Wobei ich das Paket zusätzlich installiert habe: https://cran.r-project.org/web/packages/RcppBigIntAlgos/index.html. Beispiele und Erklärungen: https://cran.r-project.org/web/packages/RcppBigIntAlgos/readme/README.html

Hier bezogen: https://cran.r-project.org/bin/linux/ubuntu/

noisefloor schrieb:

wie auch immer du darauf kommst... beide Zahlen, die du als Primfaktor nennst, sind keine Primzahlen

Da hast Du natürlich, Recht das macht die Verwirrung nur noch grösser, mein Fehler sorry, ich hab das Programm zur generierung der Primzahlen einfach falsch geschrieben, ich habe die Datentypen long int verwendet, was dazu führt das es die falsch verarbeitet muss mir das mit gdb mal genauer anschauen, Jetzt habe ich die Datentypen auf long long geändert, jetzt gibt es die Primzahlen wieder richtig aus(mit einer Internettabelle abgeglichen)

Ich nehme jetzt zb ähnliche die aber echte Primzahlen sind:100816275700000000000 = 10040730827×10040730841

bei msieve kommt das raus:

heidi@heidi-tty:~/Schreibtisch/mbuild/msieve$ sudo nice -n -10 taskset -c 0-7 ./msieve -v 100816275700000000000
[sudo] Passwort für heidi: 


Msieve v. 1.46
Sun Oct 27 15:42:19 2024
random seeds: 4a4acc58 51cf9261
factoring 100816275700000000000 (21 digits)
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 2
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 5
p1 factor: 7
p2 factor: 29
p3 factor: 149
p5 factor: 33331
elapsed time 00:00:00
heidi@heidi-tty:~/Schreibtisch/mbuild/msieve$ 

Das ist aber falsch. Für jede natürliche Zahl > 1 gibt es nur eine Primfaktorzerlegung.

Hm.. 100816275700000000000 = 10040730827×10040730841 der linke Wert ist eine Natürliche Zahl, und Rechts sind die 2 Primfaktoren, msieve gibt diese Möglichkeit nicht aus.

6% der Gesamtleistung der CPU oder 6% eines Kerns?

8 kerne die Gesammtleistung der cpu(top)

verdooft schrieb:

Hab mir gerade mal R angesehen, das kann mit mehreren Threads Faktorisieren:

Danke für den Tipp das schaue ich mir auch später mal an, ich bin kein Hacker oder sowas, ich hab nicht vor die rsa mit 2048bits von N auf p*q zu schliessen

Das Ziel war das alle Faktorisierungsmöglichkeiten(Brutforcen alle Faktoren ausgegeben werden)

Hallo,

das ist ja auch das richtige Ergebnis - deins ist (wieder) falsch. Wieder mit sympy:

1
2
3
4
5

>>> n = 100816275700000000000
>>> res = primefactors(n)
>>> res
[2, 5, 7, 29, 149, 33331]
>>>

100816275700000000000 = 10040730827×10040730841 der linke Wert ist eine Natürliche Zahl, und Rechts sind die 2 Primfaktoren, msieve gibt diese Möglichkeit nicht aus.

Wo kommt denn das Gleichheitszeichen her? Die Rechnung ist falsch:

1
2
3
4
5

>>> 10040730827*10040730841
100816275680838335507
>>> >>> primefactors(100816275680838335507)
[10040730827, 10040730841]
>>>

Mal abgesehen davon, dass eine natürlich Zahl, die auf Null (0) endet, auf jeden Fall durch 2 teilbar ist. Schon alleine deshalb ist doch offensichtlich, dass 100816275700000000000 = 10040730827×10040730841 nicht stimmen kann bzw. nicht die richtige Primfaktorzerlegung sein kann.

Könnte es vielleicht sein, dass du gar keine Probleme mit msieve hast, sondern eher mit deinem eigenen, wie auch immer geartetem Programm, das einfach falsch rechnet?

Gruß, noisefloor

noisefloor schrieb:

Mal abgesehen davon, dass eine natürlich Zahl, die auf Null (0) endet, auf jeden Fall durch 2 teilbar ist.

… und eine Zahl, die mit 11 Nullen endet, durch 10^11 teilbar ist, also 2^11 und 5^11 als Primfaktoren haben muss.

Spaßeshalber nochmal mit maxima:

Maxima 5.46.0 https://maxima.sourceforge.io
using Lisp GNU Common Lisp (GCL) GCL 2.6.14 git tag Version_2_6_15pre3
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) factor(100816275700000000000);
                             11  11
(%o1)                       2   5   7 29 149 33331
(%i2) 

Könnte es vielleicht sein, dass du gar keine Probleme mit msieve hast, sondern eher mit deinem eigenen, wie auch immer geartetem Programm, das einfach falsch rechnet?

100816275700000000000 ist offensichtlich eine auf zehn signifikante Stellen gerundete Version von
100816275680838335507. (untereinander geschrieben wird es klar)

Da ist also eindeutig ein fetter Käfer in der Zahlenerzeugung.

--ks

noisefloor schrieb:

das ist ja auch das richtige Ergebnis - deins ist (wieder) falsch.

Nee wir reden anneinander vorbei dein Ergebnis: 2*5*7*29*149*33331 = 10081627570 das ist Ungleich der Ausgangszahl: 100816275700000000000 das ist Natürlich keine Primzahl, muss es ja auch nicht, nur p*q müssen Primzahlen sein N nicht!

Mein Ergebnis ist: 1,008162757×10²⁰(gnome-calc) das kann nicht falsch sein, msieve verwendet nur warscheinlich einen anderen Algorithmus, die Faktorisierung ist ja richtig, nämlich mit deiner genau Identisch. Der einzige Unterschied ist das dein Programm jeden Faktor nur 1x aufschreibt.

Wo kommt denn das Gleichheitszeichen her? Die Rechnung ist falsch:

Verstehe ich auch wieder nicht, wenn p und q Primzahlen sind, N muss keine Primzahl sein:

Ganz einfaches Beispiel: n = p * q

143 = 11 * 13 #Wobei 143 keine Primzahl ist aber 11, 13 Primzahlen sind.

Mal abgesehen davon, dass eine natürlich Zahl, die auf Null (0) endet, auf jeden Fall durch 2 teilbar ist.

Ja klar, ich habe auch nie etwas anderes Behauptet, wenn n eine Primzahl wäre, dann könnte man die logischerweise nicht Faktorisieren ☺

Könnte es vielleicht sein, dass du gar keine Probleme mit msieve hast,

Nochmals ich habe im Eingangspost geschrieben das msieve ausser das es nicht die verfügbaren Hardware Resourcen ausnutzt, kein Problem hat, ich bin auf der Suche nach einem Programm, das eine Natürliche Zahl(keine Primzahl oder mersenne Primzahl) faktorisieren kann,

Ich schaue mir mal das von verdooft an, das geht eher in der Richtung glaube ich.

Wobei R eher wie mit Kanonen auf Spatzen schießen ist. Würds aber für große Zahlen trotzdem z.B. qalc vorziehen. Beispiel:

time qalc -s "exp 0" "factor(1008162753000000000008876113)"
Faktorisieren (zum Abbrechen drücken Sie die Eingabetaste)................................
1008162753000000000008876113 = 1087 × 438785761 × 2113725458503759

real    0m7,362s
user    0m7,145s
sys     0m0,044s

-s "exp 0" brauchts, damit 2113725458503759 nicht mit 2,113725459E15 dargestellt wird. 2. Durchgang nur 4 Sekunden.

vs. R

> a <- as.bigz("1008162753000000000008876113")
> quadraticSieve(a, showStats = TRUE, nThreads = 16)

Summary Statistics for Factoring:
    927472633854645814175599



|     Total Time     |
|--------------------|
|         1ms        |

Big Integer ('bigz') object of length 3:
[1] 1087             438785761        2113725458503759

qalc 4-7 Sekunden, R nur eine Millisekunde.

Sind aber wohl auch komplett verschiedene Verfahren.

ubuntu--anfaenger schrieb:

Nee wir reden anneinander vorbei dein Ergebnis: 2*5*7*29*149*33331 = 10081627570 das ist Ungleich der Ausgangszahl: 100816275700000000000

Da fehlen die Potenzen. Das Ergebnix von noisefloor gibt nur die unterschiedlichen Primfaktoren aus, ohne Potenzen. Ich hab dir die vollständige Zerlegung gegeben. verdooft auch.

Mein Ergebnis ist: 1,008162757×10²⁰(gnome-calc) das kann nicht falsch sein,

Nicht falsch, aber ungenau. Wie ich vermutet hatte. Kann es sein, dass dir nicht klar ist, dass bei Gleitkommazahlen die Mantisse gerundet ist? Das ist ja der Witz der Verkürzung. Wenn die Mantisse exakt wäre, könnte man auf den Exponenten verzichten und gleich das Komma 20 Stellen nach rechts rücken.

Du kannst eine Angabe wie „Die Vakuumlichtgeschwindigkeit beträgt 3*10^8 m/s“ nicht stur in 300000000 m/s umrechnen. Das 10^8 gibt die Größenordnung an, keinen exakten Faktor. Der exakte Wert ist 299792458 m/s. In den meisten Fällen ist 3 aber genau genug.

Und das exakte Produkt von 10040730827 und 10040730841 ist 100816275680838335507. Isso. Deine Zahl mit 20 Nullen ist ein auf zehn signifikante Stellen gerundeter Wert. Aber nicht der exakte. Deshalb funktioniert dessen Faktorisierung nicht.

gnome-calc ist eine Taschenrechner-App. Kaum ein Taschenrechner rechnet auf 30 Stellen genau. Das wird im Alltag etwa eines Ingenieurs nirgends gebraucht. Man gibt acht oder zehn exakte Stellen an und lässt dann nur noch Nullen folgen – ob das jetzt ein Milliardstel mehr oder weniger ist, macht im Alltag nichts aus. Beim Faktorisieren natürlich schon ☺ Daher setzt du einfach ein ungeeignetes Tool zum Multiplizieren ein.

143 = 11 * 13 #Wobei 143 keine Primzahl ist aber 11, 13 Primzahlen sind.

Logisch. Das Produkt zweier Primzahlen kann niemals prim sein. Fundamentalsatz der Arithmetik.

--ks

verdooft schrieb:

Wobei R eher wie mit Kanonen auf Spatzen schießen ist. Würds aber für große Zahlen trotzdem z.B. qalc vorziehen.

Ich habs mir echt bisher noch nicht angeschaut, mache das Morgen in Ruhe, die Potenteste Methode für grosse Zahlen ist die Pollard Rho Methode.

Für kleinere Zahlen ist die NFS Methode schneller.

Kreuzschnabel schrieb:

Da fehlen die Potenzen. Das Ergebnix von noisefloor gibt nur die unterschiedlichen Primfaktoren aus, ohne Potenzen.

Aber ja, das schrieb ich doch, mit den Potenzen ist das Ergebnis identisch zu meinem.☺

Ich glaube, du willst es nicht kapieren.

Also nochmal langsam:

Deine Multiplikation 10040730827·10040730841 = 100816275700000000000 ist ungenau (und das Gleichheitszeichen falsch).

10040730827·10040730841 ist 100816275680838335507, nicht 100816275700000000000.

Deshalb funktioniert auch deine Faktorisierung nicht, weil das natürlich eine andere Zahl mit anderen Primfaktoren ist.

Die Ungenauigkeit kommt daher, dass du von gnome-calc ein auf 30 Stellen exaktes Ergebnis erwartest. Tatsächlich rechnet die App aber nur auf zehn Stellen genau und füllt dann die restliche Zahl mit Nullen auf – beziehungsweise stellt eine Zehnerpotenz als Faktor dahinter, das kommt aufs selbe raus.

Tipp fürs Leben: Die letzte Stelle eines Produkts ist immer gleich der letzten Stelle des Produkts der letzten Ziffern der Faktoren. Also muss eine Zahl, die mit 7 aufhört, multipliziert mit einer anderen Zahl, die mit 1 aufhört, ein Ergebnis geben, das mit 7 aufhört, denn 7·1=7.

--ks