Die Mathe-Redaktion - 05.12.2019 21:21 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 687 Gäste und 24 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Mathematik » Zahlentheorie » Könnte die Zerlegung von RSA-232 mit mehreren Forumsmitgliedern realistisch werden?
Druckversion
Druckversion
Antworten
Antworten
Seite 1   [1 2]   2 Seiten
Autor
Universität/Hochschule Könnte die Zerlegung von RSA-232 mit mehreren Forumsmitgliedern realistisch werden?
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-11-05


Cipher hat mich bei ihrer Frage hier auf eine Idee gebracht.

Mit dem versteckten Modus "Curven-Index-Überspringen" kann man die lange Warterei abkürzen.
Statt 232stellige Zahlen (die nach Jahren bis heute nicht zerlegt werden konnten) bleiben nur Zahlen im Bereich von 6 bis 15 Stellen über. Natürlich ist wegen der Nichtlinearität die Unsicherheit groß und die Rechnerei pro Index von über 1 min recht aufwendig...
Aber dafür ist die Parallelisierbarkeit gut (mehrere Browser pro PC).

Wenn sich dann noch genügend Leute finden und die Näherungsformel (für den Suchbereich des Index) weiter optimiert wird, könnte es was werden - oder?



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2019-11-05


3 Bemerkungen:

a) Leider muss man Browser unterschiedlicher Installationen (möglichst auch Hersteller) verwenden (wenn man die Suche parallel angeht), da intern was gespeichert wird und mehrere EXE des selben Ordners nicht mehrere unterschiedliche Berechnungen zulassen. Natürlich wäre eine optimierte EXE noch besser (den JAVA-Code hat man ja). Aber Optimierung kommt erst, wenn sich genug Interessenten melden und realistische Aussichten gibt.

b) Wenn die vielen anderen Teams auf der Welt bereits auch mit diesem Trick schon seit Jahren arbeiten, kann man sich diese Arbeit natürlich sparen. (Man hört nur nicht konkretes, wer gerade was genau wie sucht - oder?)

c) die Preisgelder gibt es ja leider nicht mehr - aber der Ruhm wäre im Erfolgsfall enorm.



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-11-06


Weitere Fakten zur Machbarkeit.

Ich habe mal die JAVA-Version besorgt und diese lokale Version mit der online-Version verglichen:



Also etwa gleich schnell. Diese alte Version zeigte auch schon richtig vorzeitig an, ob "zusammengesetzt" - also "is composit":


Auch die Obergrenze wurde richtig abgefangen: der Curven-Index kann maximal 8stellig sein!
Für RSA-232 und einem 8stelligen Index habe ich mal die Zeit gestoppt: etwa 8 min. pro Kurve -> das ist natürlich viel

Wenn man z.B. die vorderen 10 Mio. überspringt und bis 99999999 rechnet,
ergibt das eine Rechenzeit von
(99999999-10e6)*8/(60*24*365) = 1370 Jahre/Thread

Selbst wenn jeder ein 8 virt. Kern PC hätte (i7, normaler AMD),
müssten sich 172 Leute finden, die ununterbrochen 1 Jahr lang rechnen :-(

Wenn sich dann nach 1 Jahr herausstellt, dass der Index doch etwas kleiner als 10 Mio. oder etwas größer als 100 Mio. war (weil nix gefunden), wäre der Frust noch größer...

Das wird wohl nix...



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1044
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-11-06


Auf eine RSA-Knackerei habe ich keine Lust, ehrlich gesagt.
Außerdem könnte das hier bei mir vorhandene ECM 6.4.4 das auch erledigen.
Aber wie das mit den Kurven genau geht (Abschätzung für Fund) habe ich keine Ahnung.




-----------------
Pech in der Liebe , Glück im Verlieren !!!



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-11-06


Hier ein Beispiel, wie schnell ECM sein kann, wenn gleich die 1. Kurve (Kurven-Index 1) zum Erfolg führt (NICHT-RSA-Zahlen mit fast gleich großen Primfaktoren):
2007stellige Zahl in 4 s:




  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 5016
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-11-07


@hyperG

Naheliegender ist bei einem solchen überaus "speziellen" $n$ wohl die Berechnung des Faktorenpaars mittels
\[\lceil\sqrt n\,\rceil\pm\sqrt{\lceil\sqrt n\,\rceil^2-n}\] Probier's einfach mal aus!   cool

PS: Viele CAS haben allerdings ein Problem bei der Berechnung von $\lceil \sqrt n\, \rceil$ für das 2007-stellige
\[n:= 791267484151\cdot 2^{3335} + 4^{3333} + 2504416925898612144763195 \] Derive, welches hier mit keiner Wimper zuckt und auf meinem Rechner nach 1.5s obigen Ausdruck korrekt auswertet, ist da wieder einmal eine erfreuliche Ausnahme!  biggrin

 



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-11-07 21:58


Ja, genau danach habe ich ja die Zahl ausgesucht (2 Primes aus einem sexy Prime ... sexy CPAP Ken Davis 2^3333 + 1582534968299 + 6n
 miteineander multipliziert & in einer ausmultiplizierten Schreibweise).
Mit dem Wissen, dass man die Faktorensuche nicht von vorn (90% aller primitiven Programme) , sondern von hinten beginnen kann, kommt man mit Mathematica sogar auf:


eine Gesamtzeit von nur 0.015 s

Das könnten alle guten Primfaktoren Programme mit einem Extra-Thread parallel prüfen...

Die "normale Primfaktorzerlegung" von Mathematica bekommt das nicht hin. (schwache Leistung)



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 5016
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-11-08 08:20


@hyperG

Kitaktus hat dies erst kürzlich hier schon einmal moniert und ich kann mich dem nur anschließen: Du betrachtest immer nur einseitig die Laufzeit eines Programms und lässt die vom Programmierer investierte Arbeitszeit vollkommen außer Betracht.  eek

Hier haben wir ein weiteres wunderschönes Beispiel dafür: Du musst erst selbst die interne Rechengenauigkeit manuell hochdrehen, damit Mathematica mit der Berechnung diverser Ausdrücke überhaupt zurecht kommt und bestimmst dann deinen Teiler $b$ mit einer Art Probiermethode, auch wenn diese unter den gegebenen Umständen hier sehr schnell zum Ziel führt. Ich muss dagegen, wie ausgeführt, zur Rechenzeit von 1.5s in Derive nur noch die Zeit für die Eingabe der obigen universellen Formel addieren, ohne mir darüber hinaus Gedanken machen zu müssen und bin damit insgesamt sicher schneller am Ziel.   cool



  Profil  Quote  Link auf diesen Beitrag Link
ThomasRichard
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 08.04.2010
Mitteilungen: 394
Aus: Aachen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-11-08 10:41


2019-11-07 01:02 - weird in Beitrag No. 5 schreibt:
@hyperG

Naheliegender ist bei einem solchen überaus "speziellen" $n$ wohl die Berechnung des Faktorenpaars mittels
\[\lceil\sqrt n\,\rceil\pm\sqrt{\lceil\sqrt n\,\rceil^2-n}\] Probier's einfach mal aus!   cool

PS: Viele CAS haben allerdings ein Problem bei der Berechnung von $\lceil \sqrt n\, \rceil$ für das 2007-stellige
\[n:= 791267484151\cdot 2^{3335} + 4^{3333} + 2504416925898612144763195 \] Derive, welches hier mit keiner Wimper zuckt und auf meinem Rechner nach 1.5s obigen Ausdruck korrekt auswertet, ist da wieder einmal eine erfreuliche Ausnahme!  biggrin

Du hast doch auch Maple, oder? Mit isqrt geht das so schnell, dass sich gar kein Timing lohnt (jedenfalls habe ich keine Lust, das extra zu messen):
Maple
n:=791267484151*2^3335+4^3333+2504416925898612144763195:
length(n);
iw:=isqrt(n):
f1:=iw+sqrt(iw^2-n): length(f1);
                              1004
f2:=iw-sqrt(iw^2-n): length(f2);
                              1004
isprime(f1);
                              true
isprime(f2);
                              true

Oder habe ich die Aufgabenstellung missverstanden?
[Den verlinkten Thread habe ich jetzt nicht durchgelesen.]


-----------------
Thomas Richard
Application Engineering / Technischer Support
Maplesoft Europe GmbH



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 5016
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-11-08 13:20


2019-11-08 10:41 - ThomasRichard in Beitrag No. 8 schreibt:
Oder habe ich die Aufgabenstellung missverstanden?

Ja und nein, würde ich dazu sagen.  wink

Es ging hier - gewissermaßen auf einem Nebenschauplatz - auch darum, dass in vielen CAS die Funktionen ceil() und floor() für große Zahlen nicht bedingungslos funktionieren, indem man als User dafür, wie in obigem Programm von HyperG, noch die Rechengenauigkeit entsprechend einstellen muss. Auch Maple ist da keine Ausnahme und man müsste z.B. mit der Anweisung

Digits:=2000

dafür sorgen, dass ceil(sqrt(n)) für unser $n$ hier funktioniert, während Derive diese internen Genauigkeitsanpassungen nach außen hin unsichtbar selbst durchführt, so wie man dies eigentlich erwarten würde.

Was nun dein Konstrukt isqrt(n), welches ich selbst gerne und häufig verwende, betrifft, so ist es hier nur zufällig so, dass es damit funktioniert, denn wie du selber ja sehr viel besser weißt, wird hier nur sqrt(n) auf die nächste ganze Zahl gerundet, das Ergebnis könnte also genauso gut ceil(sqrt(n))-1 sein, in welchem Fall man dann in meiner Formel isqrt(n)+1 nehmen müsste. Mit dieser kleinen Einschränkung, würde ich das natürlich genauso machen, da es algorithmisch weit besser auf den vorliegenden Fall abgestimmt ist, was ich oben über ceil(sqrt(n)) gesagt hatte, bleibt aber trotzdem richtig.



  Profil  Quote  Link auf diesen Beitrag Link
ThomasRichard
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 08.04.2010
Mitteilungen: 394
Aus: Aachen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2019-11-08 16:36


Hallo weird,

das ist ein wichtiger Punkt - danke für den Hinweis.

Die Dokumentation geht zwar darauf ein (?ceil, vorletzter Punkt unter Description), aber das kann man leicht überlesen:

If x is a constant, these functions will use evalr() to try to cautiously evaluate x to a floating point number and then apply themselves to the result.  This computation is performed initially at the current setting of Digits, and then if necessary a limited number of times more at higher settings.  If evalr() continues to return a result which is ambiguous with respect to the function being applied, the original function will return unevaluated. In this case, increasing Digits before calling the function may still help in rare cases.

In diesem konkreten Beispiel reicht Digits:=1252, wie ich ausprobiert habe, damit ceil(sqrt(n)) ausgewertet wird - und dann ist es nach wie vor schnell.

Man kann jedoch nicht alle Fälle vorhersehen; d.h. es bleiben immer Situationen, in denen sich der Anwender darum kömmern muss. Das gilt z.B. auch für das identify-Kommando (Algorithmen PSLQ und LLL), welches manchmal erst mit sehr großen Digits-Werten zu Ergebnissen kommt.

Wenn man Digits zu großzügig erhöht, muss man sich zwar weniger Gedanken machen, verschenkt aber viel Performance. Das passiert vermutlich in Derive.


-----------------
Thomas Richard
Application Engineering / Technischer Support
Maplesoft Europe GmbH



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2019-11-14 23:16


Eigentlich war Beitrag 4 nur dafür gedacht, um mit einem Beispiel zu zeigen, wie schnell ECM bei NICHT-RSA-Spezialfällen sein kann.

Leider war diese "Spezialfall-Untergruppe" zu primitiv, so dass wir komplett vom Thema abgekommen sind.

Ich habe nun schon mindestens 4 NICHT-RSA-Zahlentypen gefunden, die 300stellige Zahlen (mit geeigneten Algorithmus) unter 10 s lösen können, wo alle anderen mir bekannten Programme
(Mathematica, yafu, www.alpertron.com.ar/ECM.HTM )
Stunden, Tage oder Wochen benötigen.

Das interessiert aber keinen. Die einzige Aufmerksamkeit bekommt man erst, wenn man "echte RSA-Zahlen" in weniger als 1 Tag zerlegen kann.

Da mir noch keiner genau sagen konnte, wo die Grenze der RSA-Zahlen-Typen genau liegen (welche Kriterien genau erfüllt sein müssen),
könnte es ja sein, dass es unter den vielen RSA-Zahlen auch noch leichte Unterschiede gibt. (oder jemand beim Bilden einer RSA-Zahl gewisse Kriterien vergessen hat)

Der einzige "Abkürzungs-Weg", um mit 1 PC unter 1 Jahr Rechenzeit bei RSA-232 zu bleiben, schien mir das Überspringen der ersten 20000 "ECM-Curven" zu sein. Leider ist keiner (außer Cipher im anderen Thread)  darauf eingegangen. Allein macht die Suche der geeigneten "Curve" keinen Sinn, da es theoretisch auch 14stellige Curven sein könnten und mit steigender Curve die Rechenzeit leider ansteigt.



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1350
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2019-11-15 13:06


2019-11-14 23:16 - hyperG in Beitrag No. 11 schreibt:
Da mir noch keiner genau sagen konnte, wo die Grenze der RSA-Zahlen-Typen genau liegen ...

Die bekannten Faktorisierungsverfahren lassen sich in zwei Arten einteilen:

1. Die Laufzeit hängt von der Größe der (zu findenden) Primfaktoren ab
2. Die Laufzeit hängt von der Größe der Eingabezahl ab (und ist unabhängig von der Größe der Faktoren)

Probdivision, Pollard-Rho, ECM gehören zur 1. Klasse, Siebverfahren wie MPQS, (G)NFS zur zweiten.
Die RSA-Zahlen sind maximal ungünstig im Sinne der Verfahren 1. Art, 'normale' Zahlen mit vielen kleinen Faktoren können jedoch dennoch sehr schnell zerlegt werden. Das gilt auch für 200stellige oder noch größere Zahlen. Am Ende entscheidet der zweitgrößte Primfaktor über die Gesamtlaufzeit.

Siehe hierzu auch meinen Artikel aus 2008.



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 5016
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-11-15 13:43


2019-11-15 13:06 - Kay_S in Beitrag No. 12 schreibt:
Die RSA-Zahlen sind maximal ungünstig im Sinne der Verfahren 1. Art, [..]

Oder kurz gesagt: Die ECM-Methode kann man für RSA-232 einfach nur "vergessen". Man werfe nur einmal einen kurzen Blick auf die Stelligkeiten des kleinsten Primfaktors der aktuellen "ECM-Rekorde" hier um das zu begreifen.  cool  



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2019-11-17 12:40


2019-11-15 13:06 - Kay_S in Beitrag No. 12 schreibt:
2019-11-14 23:16 - hyperG in Beitrag No. 11 schreibt:
Da mir noch keiner genau sagen konnte, wo die Grenze der RSA-Zahlen-Typen genau liegen ...

Die bekannten Faktorisierungsverfahren lassen sich in zwei Arten einteilen:

1. Die Laufzeit hängt von der Größe der (zu findenden) Primfaktoren ab
2. Die Laufzeit hängt von der Größe der Eingabezahl ab (und ist unabhängig von der Größe der Faktoren)
...

Siehe hierzu auch meinen Artikel aus 2008.

Danke Kay_S, nun habe ich viele "Schlagworte" bekommen, nach denen ich suchen kann.

Bei meinen Untersuchungen eigneten sich Zahlen um die 300 Stellen am besten zur groben Vor-Gruppierung:
a) primitiv , so dass sie jedes "billige Programm" in <10s lösen kann
also entweder kleine Faktoren oder Primzahlzwillinge (gleich in der Nähe der Wurzel)
b) diese habe ich als NICHT-RSA-Zahlen bezeichnet; 2 Untergruppen
 b1) ein "Abkürzungsalgorithmus" findet sich -> können in weniger als 10 s gelöst werden
 b2) kein Abkürzungsalgorithmus bekannt (weit mehr als 5 min)
c) RSA-Zahlen, die entweder Jahre benötigen, oder durch Zufall (durch Überspringen von Kurven; was ich eigentlich mit mehreren Leuten mal versuchen wollte) gefunden werden

Für mich sind die Grenzen von b1, b2 und c noch nicht zu 100% klar
(nur indirekt und schwammig formuliert).
Ich habe mir auch Kay's Programm factor.exe heruntergeladen, konnte aber keines der folgenden Zahlen unter 5 min lösen.

Bisher hatte ich ein Programm, das ich als "Carmichael-ähnlichen Zahlentyp" bezeichnete. Mit Mathematica dachte ich zunächst, dass dieser Algorithmus bekannt sei. Aber nun stellte sich heraus, dass es scheinbar 2 bekannte Algorithmen gibt, die mein Programm gemeinsam in unter 1 s löst:
b1) "Carmichael-ähnlich a)"
293881793250088298254883951432018348703263903839725008584333452078564250461720415805987498495622652722421429761086686267650047941152784363166128693299636579072587976510866963036046215201586963715210261589
- mein Carmichael-Löser 1 ms
- Mathematica < 1 s
- alpertron.com.ar/ECM.HTM über 10 min (habe nicht abgewartet)

b1) "Carmichael-ähnlich b) {Lehman}"
1894488986735220903933120588844762093287003147703361784099243056592430781981200388825927280760914227849576612342830300870433042855761201160791799942003521731732198084992080624582914871061510917913632897910724906376127899772875127838965892901683044490025976783559503417474624565322247661444096346194750125851
- mein Carmichael-Programm 1 ms
- alpertron.com.ar {Lehman} 2.1 s
- Mathematica über 10 min (habe nicht abgewartet)
- yafu bringt auch mit mehreren keine Lösung in 10 min
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C307
rho: x^2 + 2, starting 1000 iterations on C307
rho: x^2 + 1, starting 1000 iterations on C307
pm1: starting B1 = 150K, B2 = gmp-ecm default on C307
ecm: 30/30 curves on C307, B1=2K, B2=gmp-ecm default
ecm: 74/74 curves on C307, B1=11K, B2=gmp-ecm default
ecm: 42/214 curves on C307, B1=50K, B2=gmp-ecm default, ETA: 2.3 min..

Dann noch 2 NICHT-RSA-Zahlentypen, zu denen ich kein bekannten Algorithmus ("Schlagwort") fand:
b1) "unbekannt 1 M"
2370946765649268998742335241843305596324444725650636791603477220120499073638490378484598678745362416370929580825457643910052922376980580940094969717477659564926292671364716031619757788927
- mein Programm < 1 s
- alle anderen mir bekannten brauchen weit über 10 min (nie bis zu Ende gewartet, da es auch Tage werden können)
- selbst yafu mit mehreren nix:
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C187
rho: x^2 + 2, starting 1000 iterations on C187
rho: x^2 + 1, starting 1000 iterations on C187
pm1: starting B1 = 150K, B2 = gmp-ecm default on C187
ecm: 30/30 curves on C187, B1=2K, B2=gmp-ecm default
ecm: 74/74 curves on C187, B1=11K, B2=gmp-ecm default
ecm: 214/214 curves on C187, B1=50K, B2=gmp-ecm default, ETA: 0 sec
pm1: starting B1 = 3750K, B2 = gmp-ecm default on C187
ecm: 3/430 curves on C187, B1=250K, B2=gmp-ecm default, ETA: 12.9 min
...

Und der letzte NICHT-RSA für heute:
b1) "unbekannt 2 B"
41274950888965185949412537806851373243170858022991261210646638215748683160982637878700281232266814443013839598080044223434424842220549430033251038062289414675671302489839659246020468484181584407382810913772955597179926707424577783466009711413167088687400527264239690248039247933158391473000143248448583020953
- mein Programm um die 1 s
- keine Carmichael-ähnliche!
- alle anderen mir bekannten Programme weit über 10 min

Oder wir probieren es mal anders herum: Ihr schickt mir lange Zahlen (150 ...307 Stellen wo alpertron.com.ar länger als 5 min braucht),
und ich setze meine verschiedenen Algorithmen an und schaue, ob nach 10 s eine Lösung vorliegt.

Ein Beispiel hat mir pzktupel schon zugeschickt:
(10^211-1)/9
- kein Algorithmus schaffte unter 5 min
- es ist aber auch keine RSA-Zahl -> also Typ b2)



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2019-11-19 23:06


Was sagen denn andere Programme (wie Derive, Maple usw.) zu den 4 von mir konkret vorgeschlagenen "b1 Zahlen"?

Gibt es auch gewaltige Zeitunterschiede?

Oder konnte kein Programm (außer die von mir genannten 1. Zahl Mathematica < 1 s; 2. Zahl alpertron.com.ar {Lehman} 2.1 s )
die 4 Zahlen zerlegen?

Oder sind alle 4 "Abkürzungsalgorithmen" bereits bekannt und ein Programm löst alle 4 Zahlen in unter 1 s?

Oder kennt sich jemand mit den vielen Parametern von yafu aus?
Ich kenne nur factor(...) und siqs(...).

Oder muss ich weird wieder etwas provozieren, damit ich Antworten bekomme:
Was ist denn mit den tollen Programmen, die "... insgesamt sicher schneller am Ziel" sind?
(ich hoffe, dass meine positiv angedachten Ambitionen richtig gedeutet werden und nicht jemand über reagiert)



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 5016
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2019-11-20 08:31


2019-11-19 23:06 - hyperG in Beitrag No. 15 schreibt:
Oder muss ich weird wieder etwas provozieren, damit ich Antworten bekomme:
Was ist denn mit den tollen Programmen, die "... insgesamt sicher schneller am Ziel" sind?

Ok, ich hab mir jetzt nur einmal die erste deiner Zahlen, nämlich

$n_1 := (2\cdot 199^{42}\cdot 11579 + 1)·(2\cdot 3\cdot5\cdot11\cdot13\cdot199^{42}\cdot233 + 1)$

genauer angesehen und aufgrund seiner Bauart sollte sie für die (p-1)-Methode von Pollard (s.hier) ein "gefundenes Fressen" sein. Tatsächlich braucht Derive auch nur 5.45s für die Faktorisierung und der Löwenanteil dieser Zeit geht für Primzahltests und andere Faktorisierungsmethoden drauf, welche normalerweise ergiebiger sind und daher auch zuerst probiert werden. *)

Maple hat erstaunlicherweise tatsächlich ein Problem mit dieser Zahl, offenbar deshalb, weil es die (p-1)-Methode von Pollard gar nicht erst probiert, da diese für Zahlen dieser Größenordnung aussichtslos ist, außer eben, wenn sie so extrem "konstruiert" sind, wie dies hier der Fall ist.  cool

*) Dies zeigt auch die ganze Problematik von solchen Zeitvergleichen auf: Würde man die (p-1)-Methode vorziehen, käme man wohl auf einen Bruchteil dieser Rechenzeit, aber es würde dafür dann auch die Performance für die Faktorisierung "normaler" Zahlen darunter leiden.

PS: Bei einem Verdacht um diese überaus spezielle Struktur der vorgegebenen Zahl $n_1$, kann man dann auch mal einen "Schnellschuss" wie
Maple 2018
t:=time():igcd(2&^(10000!) mod n1 -1,n1),(time()-t)*s
3561577691720060064219441694697240174898164849563716953667408175\
279156275506507330291492422867995411571, 0.031 s

wagen, der hier auch sofort auf einen der beiden Primfaktoren führt. Und das in nur 0.031s !  biggrin



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, vom Themenstarter, eingetragen 2019-11-20 22:41


Danke weird!

Der Link macht mir jetzt auch einiges zu "Carmichael a)" klar,:
- was factordb.com mit (p-1) meint
- dass dieses Beispiel "Carmichael a)" ein viel zu einfacher Spezialfall ist, der schnell gefunden werden kann
- warum Mathematica ihn so schnell finden konnte, aber andere "Carmichael-ähnliche" nicht

Beim Nachlesen stieß ich dann auch noch auf den mir noch unbekannten Typ
 Williams's (p + 1),
und der Beispielzahl
309stellige Williams p+1 Zahl
170008213545910965886460576572090982063408798024984543559001546422534644045470603998698706971810963093964580198788881904271608774213396896678573575267676754780622889919559692654436815810637860509009977667589657189496387034548011094365919416175990986348895410113935005204972304311894659720336969894022598750477

die auch noch kein mir bekanntes Programm zerlegen konnte.

- faku stürzte beim Befehl factor(...) ab :-(
- mathematica braucht ewig
- ECM findet nach 335 Curven und über 1 h Suche nichts...




  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1044
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2019-11-21 09:57


Yafu raucht nicht ab, startet wie üblich ECM , aber das dauert ja ....


-----------------
Pech in der Liebe , Glück im Verlieren !!!



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, vom Themenstarter, eingetragen 2019-11-22 09:08


So, GMP_WilliamsP1.exe fertig!

Test mit
135stellige Williams p+1 Zahl
726286104974888320831459714524497735770165786243885681724247623636059281197969465033496277725004244158329276076523947799294094896411843

liefert in nur 0.277 s 2 Faktoren!

www.alpertron.com.ar/ECM.HTM ist in 30 min mit 350 Curven nicht fertig!

Die 309stellige aus Beitrag 17 will auch nach 30 min nicht. Entweder ich habe da noch einen Fehler, oder die richtige Start-Basis ist nicht optimal, oder es ist keine Zahl, die für "Williams p+1" Algorithmus geeignet ist.



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, vom Themenstarter, eingetragen 2019-11-22 09:54


Interessant:
Tabelle
Zahl \ Progr.|Carmichael-ähnliche| Williams p+1| Derive |mathematica|ECM
-------------+-------------------+-------------+--------+-----------+---
b1 a)        |   < 0.3 s         | < 0.3 s     | < 5.5 s| <  1 s    |>20 min
b1 b) Lehman |   < 0.4 s         |> 10 min     | ?      | > 10 min  | 2.1 s
unbekannt 1 M|   < 0.5 s (extra) |   0.001 s   | ?      | > 10 min  |>20 min
unbekannt 2 B|      1 s          |> 10 min     | ?      | > 10 min  |>20 min
Williams 135 |   > 10 min        | < 0.3 s     | ?      | > 10 min  |>20 min

Mit anderen Worten: nur die extrem leichte b1 a) kann von allen
4 schnell gelöst werden.

Hinweis: >10 min kann auch Tage bedeuten (habe nur nach 10 min abgebrochen)



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1044
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2019-11-22 11:51


Boah, das ist ja mal ne Hausnummer !
Mein altes UBASIC (16bit) Faktorprogramm fand den Teiler nach 1 min auf einem Intel Dual Core i5-2410M 2.3 GHz


726286104974888320831459714524497735770165786243885681724247623636059281197969465033496277725004244158329276076523947799294094896411843

Factor found !

1464190886433516825191407025843688953983446445200349796994195518630221

...ein komplett anderer und eigener Algorithmus den ich Anfang 2000 einmal entwickelt habe , bin erstaunt !


-----------------
Pech in der Liebe , Glück im Verlieren !!!



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, vom Themenstarter, eingetragen 2019-11-22 14:03


Super pzktupel! Das könnte ein weiterer Abkürzungsalgorithmus sein.
Zwar läuft er 200 mal langsamer (und wir sind ers bei 1 Thread) als Williams p+1 (siehe Bild), aber immer noch zig mal schneller als ECM & mathematica bei diesem Zahlentyp.

Ich schicke Dir mal eine ZIP mit bat.

Der Startparameter für die Iteration kann 3 oder 4 oder 9 oder andere sein (meist nur minimale Zeitunterschiede)




  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, vom Themenstarter, eingetragen 2019-11-22 14:11


Bevor wieder Fragen oder Hinweise kommen, dass das alles nichts mit den RSA-Zahlen zu tun hat:
- je mehr Abkürzungsalgorithmen gefunden werden, um so kleiner wird der Suchbereich für die restlichen Zahlen.

Es könnten auch "RSA-Zahlen Ersteller" gewisse Abkürzungen noch nicht berücksichtigt haben...

Ich habe neulich erst wieder gelesen, dass eine Zahl nicht mehr der nötigen Sicherheit genügt...



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 5016
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2019-11-22 15:59


2019-11-22 14:03 - hyperG in Beitrag No. 22 schreibt:
Super pzktupel! Das könnte ein weiterer Abkürzungsalgorithmus sein.
Zwar läuft er 200 mal langsamer (und wir sind ers bei 1 Thread) als Williams p+1 (siehe Bild), aber immer noch zig mal schneller als ECM & mathematica bei diesem Zahlentyp.

Ich schicke Dir mal eine ZIP mit bat.

Der Startparameter für die Iteration kann 3 oder 4 oder 9 oder andere sein (meist nur minimale Zeitunterschiede)



Ganz allgemein jetzt eine Empfehlung von mir: Wenn du eine Faktorisierung wie die obige vorliegen hast, für welche die Rechenzeit vergleichsweise sehr gering ist, dann überprüfe bitte immer(!), ob eine der folgenden Eigenschaften vorliegt:

1. Die beiden (nicht notwendig primen) Faktoren liegen "sehr nahe" beieinander (etwas ungenau, aber meist zutreffend, sollten sie die gleiche Stelligkeiten haben und in mindestens der Hälfte der führenden Stellen übereinstimmen)-> Fermatsche Faktorisierungsmethode.

2. Einer der beiden Primfaktoren $p$ hat die Eigenschaft, dass $p-1$ keinen wirklich "großen" Primfaktor aufweist-> Pollard's (p-1)-Methode.

3. Einer der beiden Primfaktoren $p$ hat die Eigenschaft, dass $p+1$ keinen wirklich "großen" Primfaktor aufweist-> Williams' (p+1)-Methode.

Ich überlasse es dir, herauszufinden welcher Fall hier vorliegt. Nur als kleiner Hinweis: Williams hat damit absolut nichts zu tun!  eek



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, vom Themenstarter, eingetragen 2019-11-22 16:06


Und der bereits von Kay genannte Pollard-Rho-Algorithmus:
78stellige Pollard-Rho-Zahl
115792089237316195423570985008687907853269984665640564039457584007913129639937

Während hier die anderen Abkürzungsalgorithmen versagen, wird (bei meiner GMP-cpp EXE) nach etwa 10 s das Ergebnis angezeigt.

ECM (Kay's und alpertron.com.ar) ist jedoch bei dieser kleinen Zahl wesentlich schneller: 0.2 s

Diese ertmalig 1980 mit Pollard-Rho zerlegte Fermat-Zahl würde ich zerlegungstechnisch den b2-Zahlen zuordnen:
zwar noch keine RSA-Zahl (die noch länger dauert), aber auch kein richtig effektiver Abkürzungsalgorithmus für Zahlen mit mehr als 300 Stellen bekannt.



[Die Antwort wurde nach Beitrag No.23 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, vom Themenstarter, eingetragen 2019-11-22 16:44


2019-11-22 15:59 - weird in Beitrag No. 24 schreibt:
...
Ganz allgemein jetzt eine Empfehlung von mir: Wenn du eine Faktorisierung wie die obige vorliegen hast, für welche die Rechenzeit vergleichsweise sehr gering ist, dann überprüfe bitte immer(!), ob eine der folgenden Eigenschaften vorliegt:
...

Ich glaube, dass wir immer noch aneinander vorbei reden.
Ich möchte keinem Mathe-Professor gefallen, und nachträglich die bereits vorliegenden zerlegten Zahlen in das richtige "Schubfach" packen,
sondern:
Eine unbekannte Zahl parallel mit zig Abkürzungsalgorithmen (je eine exe) "angreifen".
Der zuerst ein Ergebnis liefert, ist Gewinner und kommt in mein "Gewinnerschubfach", welche ich mit "b1-Zahlen" bezeichnete.

Es kann durchaus sein, dass mein "Pollard (p-1)" Programm entweder noch nicht richtig funktioniert oder noch nicht richtig optimiert wurde, aber es hat noch kein "Rennen" gewonnen.

Ich möchte hier Neuland betreten - ganz andere Ideen angehen...

Und bis jetzt habe ich (als Amateur, der mal kurz hineingeschnuppert hat) - außer der einfachsten b1 a) Zahl mal ausgenommen - zu jeder vorgestellten Zahl einen schnelleren Zerlegungsalgorithmus (Abkürzung) gefunden, als alle Profiprogramme zusammen (die sich schon Jahre mit diesem Thema befassen).

Das hat nur wenig mit Programmiersprache oder schnellem PC zu tun, wo es um Optimierungsfaktoren um 2 geht.
Bei 300stelligen Zahlen geht es darum, ob es unter 20 s zu finden ist (Abkürzung), oder Stunden oder Tage dauert, also Faktoren weit über 300.

Dass man RSA-Zahlen mit den "altbekannten" Algorithmen nicht innerhalb eines Tages lösen kann ist mir klar. Genau aus diesem Grund suche ich andere Wege. Erst wenn man die Schwächen (also den Aufbau, was eine RSA-Zahl genau für Eigenschaften haben muss) kennt, kann man effektiv vorgehen. Wenn eine RSA-Zahl möglichst weit weg von den bekannten Zerlegungsalgorithmen sein will, kann man z.B. an solchen "weit entfernten Stellen" suchen...




  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 5016
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2019-11-22 22:24


2019-11-22 16:44 - hyperG in Beitrag No. 26 schreibt:
Dass man RSA-Zahlen mit den "altbekannten" Algorithmen nicht innerhalb eines Tages lösen kann ist mir klar. Genau aus diesem Grund suche ich andere Wege. Erst wenn man die Schwächen (also den Aufbau, was eine RSA-Zahl genau für Eigenschaften haben muss) kennt, kann man effektiv vorgehen. Wenn eine RSA-Zahl möglichst weit weg von den bekannten Zerlegungsalgorithmen sein will, kann man z.B. an solchen "weit entfernten Stellen" suchen...

Wenn ich dich richtig verstehe, dann ist es offenbar dein Traum, gängige RSA-Zahlen faktorisieren zu können. Die in #24 aufgezählten Methoden sind aber m.E. die einzigen, welche für so einen "lucky Punch" in Frage kommen. Und glaube mir, dieser Tatsache ist man sich beim Design der RSA-Zahlen, wie sie in der Praxis verwendet werden, voll bewusst und verwendet genau aus diesem Grunde sog. Starke Primzahlen, welche genügend weit auseinanderliegen, sodass alle diese Angriffe von vornherein hoffnungslos sind. Dass auch die ECM-Methode, gegen die man sich nicht in dieser Weise vorher "wappnen" kann, für Zahlen dieser Größenordnung auch vollkommen chancenlos ist, hatten wir ja oben auch schon erwähnt.

Es bleibt also dann im Grunde als einzige Möglichkeit das Zahlkörpersieb und damit wurde deine(?) RSA-Zahl mit 232 Stellen ja auch schon 2009 faktorisiert (s. hier). Aber da du ja offenbar in erster Linie an Lösungen unter 20s interessiert bist, fällt dann wohl auch diese Möglichkeit weg, auch wenn seither 10 Jahre vergangen sind.   biggrin  



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.28, vom Themenstarter, eingetragen 2019-11-22 23:03


Nicht "RSA 768"! (Die hat zwar auch 232 Stellen, aber ich suche doch keine bereits zerlegten)

Ich rede von der kleinsten noch nicht zerlegten hier für RSA-232 klicken.

Ich nutze immer folgende Tabelle, da sie übersichtlich den aktuellen Stand zeigt: hier in der engl. Version

Zu Beginn der Frage bin ich noch davon ausgegangen, dass die Geschwindigkeit der "Curven-Abarbeitungszeit" konst. bleibt.
Wenn viele verteilt gewisse Bereiche durchgearbeitet hätten, würde man mit etwas Glück zum Ziel kommen.
Leider habe ich schon im Beitrag 2 gemerkt, dass sie leider stark ansteigt -> und selbst mit allen Forumsmitgliedern nicht innerhalb eines Jahres machbar ist.

Andererseits werden Hard- & Software immer besser und so wurden viele wichtige Verschlüsselungen auf 2048 Stellen hochgeschraubt.
An die will ich nicht ran! Mir reicht die kleinste, die schon lange von keinem mehr als "sicher" angesehen wird. Außerdem würden einige Leute mit schwarzen Anzügen vor meiner Tür stehen, wenn ich wirklich was "universelles" finden würde... Nein, ein kleiner Zufallstreffer recht mir.

Dann kommt noch die Erfahrung hinzu, die ich zusammen mit Norman beim Suchen von Primzahl-Tupel gemacht habe. Mit etwas Glück kann man Dinge finden, von denen wir vor 5 Jahren nicht geträumt hätten...

Auch wenn es momentan noch aussichtslos erscheint, bleibe ich optimistisch -> nur eine Frage der Zeit...

Auch wenn es nur ein Teilerfolg ist, so bin ich Kay & Dir dankbar, auf die Algorithmen von Pollard & Williams gekommen zu sein. Dann noch die Motivation dies programmiertechnisch umzusetzen und teilweise schneller als die meisten Profi-Programme... -> das ist doch was.
Danke.



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.29, vom Themenstarter, eingetragen 2019-11-22 23:13


Trotzdem stehen die 2 Zahlen aus Beitrag 14
und die 309stellige aus Beitrag 19 noch aus...




  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1350
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.30, eingetragen 2019-11-24 22:33


2019-11-17 12:40 - hyperG in Beitrag No. 14 schreibt:

Oder wir probieren es mal anders herum: Ihr schickt mir lange Zahlen (150 ...307 Stellen wo alpertron.com.ar länger als 5 min braucht),
und ich setze meine verschiedenen Algorithmen an und schaue, ob nach 10 s eine Lösung vorliegt.

Ein Beispiel hat mir pzktupel schon zugeschickt:
(10^211-1)/9
- kein Algorithmus schaffte unter 5 min
- es ist aber auch keine RSA-Zahl -> also Typ b2)

Ok, auch von mir ein Beispiel. Das Zahlenpärchen
\[8967 \cdot 10^{150} \pm 1\] ist kein Primzahlzwilling, beide Zahlen sind nachweisbar zusammengesetzt. Doch wer kann die Teiler angeben? Mit nur 154 Stellen eigentlich ein Leichtgewicht smile .



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.31, vom Themenstarter, eingetragen 2019-11-25 17:35


Für 10^150*8967-1
konnte ich keine Abkürzung finden -> Typ b2)

yafu's siqs(10^150*8967-1) ist zu groß :-(

ECM habe ich bis Curve 2300 laufen -> nichts

Hast Du denn schon Faktoren gefunden, oder soll es nur ein Test sein?



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1350
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.32, eingetragen 2019-11-25 17:47


Die Faktoren kenne ich nicht. Ich habe aufsteigend alle \(k \cdot 10^{150} \pm 1\) auf kleine Faktoren getestet. Dies war das erste (zusammengesetzte) Zahlenpaar ohne Fund.



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.33, vom Themenstarter, eingetragen 2019-11-26 19:44


Hallo Kay_S,

ich habe mir mal 2 "Cunningham-ähnliche Zahlen" angeschaut, die kleiner als Deine sind, aber auch:
- große Faktoren haben
- ungerades k
- gerade Potenz

a) 93*10^86-1:
- besteht aus 2 bekannten Faktoren mit 44 & 45 Stellen
- habe noch keinen Abkürzungsalgorithmus gefunden

b) 87*10^140-1:
- kein Abkürzungsalgorithmus gefunden
- yafu sinq() meldet "to big"
- yafu factor(87*10^140-1) hat nach etwa 1h 30 min die 142 Digits in einen 118 digit Factor zerlegt, der wieder zusammengesetzt ist: C118
- kleinste Faktor p1 ist 25stellig und echt prime

Zu C118 konnte ich noch kein Abkürzungsalgorithmus finden
- yafu factor(C118) stürzt ab
- yafu sinq(..) findet mit 1 Thread nach 3 h nichts
- Alpertron's ECM hat nach 2000 Curven noch nichts
- mathematica's FactorInteger nach 15 min nix
-

Interessant: ab "Curve 2000" wird Alpertron mit dem Internet Explorer extrem langsam (um die 40 min pro Curve), Google Chrome ist etwas schneller und das lokale JAVA Programm bleibt unter 3 min (frisst mit der Zeit aber immer mehr RAM; nach dem es die 4 GB überschritten hat, starte ich es neu und springe bis zur letzten Curve; Fehlersuche bei JAVA fange ich nicht an)

Wenn schon 118stellige Faktoren ohne Abkürzungsalgorithmus schwer zu zerlegen sind, dann wird Deine 154stellige zu aufwendig für einfache Untersuchungen.

Trotz der vielen Abkürzungsalgorithmen gibt es doch mehr Zahlen als gedacht.



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1044
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.34, eingetragen 2019-11-26 20:22


ECM liefert nach paar Sekunden
p25=4609823818787153219023643
c118=1887273861648138654444447620077088476914195314300773428971368801535292428144192548945104548041847259222654022125408493


-----------------
Pech in der Liebe , Glück im Verlieren !!!



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.35, vom Themenstarter, eingetragen 2019-11-26 22:39


Norman,

Du hast mal wieder 0 Informationen mitgeliefert, welches ECM-Programm mit welchen Parametern Du verwendet hast!?

a) Deine ecm.exe, die Du mir geschickt hast GMP-ECM 6.1.1 [GMP 4.2.1] [ECM] 32 Bit war nach 10 min nicht  fertig! Andere Parameter?

b) Alpertron.com ECM

etwas unter 6 min

c) die alte JAVA-Version von Alpertron etwas über 5 min


d) yafu-x64.exe von 2013 starten
dann: factor(10^140*87-1) hatte ich ja schon mit 1h 30 min angegeben.

Alle 4 meilenweit von Deinen "paar Sekunden" entfernt!

Oder hast Du "Curven" übersprungen,
oder eine neue yafu-Version (dann bitte genaue Quellenangabe) mit siqs statt ECM verwendet?
Es unterstützt alle Kerne, aber stürzt bei mir oft ab!
(erst unter 130 Stellen läuft siqs)

Und was sagt "Dein schnelles ECM" zu
C118 = (10^140*87-1)/4609823818787153219023643

und zu Kay_S 10^150*8967-1 ?



  Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1044
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.36, eingetragen 2019-11-27 16:46


Kleine Teiler ~30 Stellen, findet ECM fix, deswegen war mir das klar, das es schnell geht.

Nimm die _create batecm.exe

1000 Kurven, B=100000

Nach 12s hat er es bei File o1010

GMP-ECM 6.1.1 [powered by GMP 4.2.1] [ECM]
Input number is 4609823818787153219023643*1887273861648138654444447620077088476914195314300773428971368801535292428144192548945104548041847259222654022125408493 (142 digits)
Using B1=110000, B2=40877772, polynomial x^2, sigma=2748616374
Step 1 took 797ms
Step 2 took 484ms
********** Factor found in step 2: 4609823818787153219023643
Found probable prime factor of 25 digits: 4609823818787153219023643
Composite cofactor (4609823818787153219023643*1887273861648138654444447620077088476914195314300773428971368801535292428144192548945104548041847259222654022125408493)/4609823818787153219023643 has 118 digits

>>>>
Und was sagt "Dein schnelles ECM" zu
C118 = (10^140*87-1)/4609823818787153219023643


Nix, dauert entsprechend...wird nicht verfolgt.


-----------------
Pech in der Liebe , Glück im Verlieren !!!



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.37, vom Themenstarter, eingetragen 2019-11-27 19:11


Also Curven übersprungen, als wenn ich bei Alpertron bei 270 starte:




Nach etwa 2 min habe ich durch zufälliges sigma einen Fund:
GMP-ECM 6.1.1 [powered by GMP 4.2.1] [ECM]
Input number is 8699999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 (142 digits)
Using B1=1006000, B2=1045563762, polynomial Dickson(6), sigma=2057943718
Step 1 took 13245ms
Step 2 took 6177ms
********** Factor found in step 2: 4609823818787153219023643
Found probable prime factor of 25 digits: 4609823818787153219023643
Composite cofactor 1887273861648138654444447620077088476914195314300773428971368801535292428144192548945104548041847259222654022125408493 has 118 digits



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1350
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.38, eingetragen 2019-11-29 07:23


Der Kofaktor von \(87 \cdot 10^{140} - 1\) zerlegt sich weiter in p45*p73:
GMP-ECM
>ecm -one -c 600 11e6 < input.txt
GMP-ECM 7.0.4 [configured with GMP 6.1.2] [ECM]
Input number is 1887273861648138654444447620077088476914195314300773428971368801535292428144192548945104548041847259222654022125408493 (118 digits)
...
Run 82 out of 600:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:3282435261
Step 1 took 11093ms
********** Factor found in step 1: 260419214480549032207585602320911517448635711
Found prime factor of 45 digits: 260419214480549032207585602320911517448635711
Prime cofactor 7247060726347060689802885449197625235662053481258383231645953154184151763 has 73 digits

Nichts gegen Alpertron & Co., aber die nativen Kompilate von z.B. gmp-ecm sind erheblich schneller, insbesondere auf 64 Bit.

Kay





  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 831
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.39, vom Themenstarter, eingetragen 2019-11-29 16:14


Super Kay,

dann kann ich ja die die Berechnung per yafu\siqs() abbrechen (läuft schon über 3 Tage).

Auch bei Dir gilt die gleiche Frage wie bei Norman: wo hast Du die GMP-ECM 7.0.4 her?
- ich habe sie nur als LINUX-Version gefunden (oder arbeitest Du mit LINUX?)
- cpp Quellcode hatte ich mir auch besorgt, aber der erzeugt nur eine
GMP-ECM 7.0.4 [configured with MPIR 3.0.0, --enable-openmp] [ECM]

Zu GMP habe ich nur eine dynamische DLL (umständlich einzubinden)
aber keine lib-Datei.

Den einzigen LINK, den ich fand: gilchrist.ca/jeff/factoring/ecm704dev-svn2990-win64.zip
aber der zeigt ins leere...

Interessant wäre Dein ganzer RUN z.B. 81, damit ich die Zeiten für 1 Kurve mit meiner compilierten EXE vergleichen kann.
(im Auszug ist ja nur ein Step 1 mit Fund von Run82)

Alpertron ist bei mir etwa 3 mal langsamer pro Kurve als meine GMP-ECM 7.0.4.

Dein B1= 11e6 entspricht Alpertrons Curve 2000 (oder größer).

Die sigma-Werte scheinen zufällig, so dass hier nicht nur ein extrem großer Sprung, sondern auch noch ein Zufall mit reinspielt, was für Vergleichsmessungen schwere Aussagen zulässt...



  Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 1Gehe zur Seite: 1 | 2  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]