Die Mathe-Redaktion - 07.12.2019 04:28 - 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 943 Gäste und 4 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?
Thema eröffnet 2019-11-05 21:08 von
hyperG
Druckversion
Druckversion
Antworten
Antworten
Seite 2   [1 2]   2 Seiten
Autor
Universität/Hochschule Könnte die Zerlegung von RSA-232 mit mehreren Forumsmitgliedern realistisch werden?
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1045
Aus: Thüringen,Erfurter Raum
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, eingetragen 2019-11-29 16:20


Sigma ist Zufall, siehe TODO File

1) efficiency/memory
- use a random sigma value of 64 bits by default


-----------------
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.41, vom Themenstarter, eingetragen 2019-11-29 18:09


Also ich habe nun eine ECM-Version mit GMP gefunden, aber diese ist noch langsamer als meine selbst compilierte MPIR-Version:
ECM 7.0.4-dev [configured with GMP 6.1.1
GMP-ECM 7.0.4-dev [configured with GMP 6.1.1, --enable-asm-redc] [ECM]
Input number is (10^140*87-1)/4609823818787153219023643 (118 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:519209101
Step 1 took 20734ms
Step 2 took 10735ms
Run 2 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:797936743
Step 1 took 20625ms
Step 2 took 10656ms
Run 3 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:3581571077
Step 1 took 20547ms
Step 2 took 10719ms

Also immer > 31 s / Kurve
ECM 7.0.4 [configured with MPIR 3.0.0
GMP-ECM 7.0.4 [configured with MPIR 3.0.0, --enable-openmp] [ECM]
Input number is 1887273861648138654444447620077088476914195314300773428971368801535292428144192548945104548041847259222654022125408493 (118 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:380151056
Step 1 took 20735ms
Step 2 took 17531ms
Run 2 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:4211437570
Step 1 took 18781ms
Step 2 took 13375ms
Run 3 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:3424740350
Step 1 took 12641ms
Step 2 took 14125ms
...
Run 209 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:3542609715
Step 1 took 12422ms
Step 2 took 13109ms

immer > 25 s /Kurve

Nun laufen schon schon 7 dieser EXE über 1 Stunde (je über 200 RUNs *7 =1400 RUNs) und noch immer hat bei mir "der Zufall" kein passendes sigma gefunden ( was den Faktor Findet).

Also war Kays Fund bei RUN 82 nur reiner Zufall?
Oder Kays Version wählt bessere sigmas (aber es sind beide V 7.0.4)...



  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.42, eingetragen 2019-11-29 18:40


2019-11-29 16:14 - hyperG in Beitrag No. 39 schreibt:
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]

Ich habe ein eigenes Binary erstellt (ecm704_win64_broadwell.zip), die Quelltexte für GMP und für ECM sind ja verfügbar. Da ich Windows nutze, verwende ich hierfür mingw mit dem gcc-Compiler. Für die bestmögliche Performance sollte man direkt für die Zielmaschine erzeugen (in diesem Fall Intel Broadwell).

Ein aktuelles 32-Bit-Binary kann ich nicht bieten (da ich kein 32-Bit-OS mehr benutze, wenngleich der Compiler entsprechend eingestellt werden kann), ich habe nur ein 10 Jahre altes (ecm623_win32_core2.zip).

Nachfolgend die Zeiten für 5 Runs auf Core i3-8100 (1 Thread):
GMP-ECM
>ecm -one -c 5 11e6 < in.txt
GMP-ECM 7.0.4 [configured with GMP 6.1.2] [ECM]
Input number is 1887273861648138654444447620077088476914195314300773428971368801535292428144192548945104548041847259222654022125408493 (118 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:2348745683
Step 1 took 11171ms
Step 2 took 5875ms
Run 2 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:4202478987
Step 1 took 10860ms
Step 2 took 5875ms
Run 3 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:1402032702
Step 1 took 10890ms
Step 2 took 5844ms
Run 4 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:1407331734
Step 1 took 10891ms
Step 2 took 5828ms
Run 5 out of 5:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:1951566020
Step 1 took 10906ms
Step 2 took 5844ms



  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.43, vom Themenstarter, eingetragen 2019-11-29 18:43


Und noch eine 3. Version für Skylake CPUs (i9), die immer über 17 s pro Kurve benötigt (schnellste bis jetzt):
7.0.4-dev [configured with GMP 6.1.1 Skylake
GMP-ECM 7.0.4-dev [configured with GMP 6.1.1, --enable-asm-redc] [ECM]
Input number is (10^140*87-1)/4609823818787153219023643 (118 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:3005003736
Step 1 took 16328ms
Step 2 took 8485ms
...
Run 3 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:4001090372
Step 1 took 13797ms
Step 2 took 6328ms
Run 4 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:2154888867
Step 1 took 13281ms
Step 2 took 7594ms
...
Run 6 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:723429435
Step 1 took 11234ms
Step 2 took 6859ms
Run 7 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:1369760914
Step 1 took 14828ms
Step 2 took 6297ms
Run 8 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:251373221
Step 1 took 11985ms
Step 2 took 6484ms
Run 9 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:739770079
Step 1 took 9984ms
Step 2 took 7860ms

Läuft nun als 8. exe parallel, d.h. nun schon:
- die ersten 2000 Kurven durch großes B1 (entspricht bei Alpertron 2000 Curven) übersprungen
- dann 8 exe mit je etwa 200 Kurven, also fast 2000 Kurven

Zusammen also etwa 4000 Kurven und noch kein Fund...


[Die Antwort wurde nach Beitrag No.41 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.44, vom Themenstarter, eingetragen 2019-11-29 19:11


Danke Kay für die EXE.

Sie zeigt sich auf meinem i9 (wo schon 16 andere Threads laufen; ohne diese würde dieser 1 Thread minimal schneller, also so wie Dein i3) so:
GMP-ECM 7.0.4 [configured with GMP 6.1.2 broadwell
GMP-ECM 7.0.4 [configured with GMP 6.1.2] [ECM]
Input number is (10^140*87-1)/4609823818787153219023643 (118 digits)
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:336293537
Step 1 took 15062ms
Step 2 took 8610ms
Run 2 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:1134756358
Step 1 took 15015ms
Step 2 took 7594ms
Run 3 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:1655760913
Step 1 took 16172ms
Step 2 took 8625ms
Run 4 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:806308488
Step 1 took 14984ms
Step 2 took 8375ms
Run 5 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:1434066239
Step 1 took 17079ms
Step 2 took 6953ms
Run 6 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:2566947929
Step 1 took 15937ms
Step 2 took 8828ms
Run 7 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:904459016
Step 1 took 16328ms
Step 2 took 7157ms
Run 8 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:4226052677
Step 1 took 12578ms
Step 2 took 7656ms
Run 9 out of 10000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=1:3457433247

also etwa immer > 22 s.
Du hast die GMP Nachvolgeversion 6.1.2. Kannst Du mir die GMP.lib zukommen lassen oder LINK angeben?

Dass Dein RUN82 ein Zufallstreffer war, wo ich jetzt schon 8 EXE mit je 380 RUNS suchen lasse,
musst Du doch aber zugeben - oder?



  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.45, eingetragen 2019-11-29 19:38


Bitte: libgmp.zip. Es kann natürlich sein, dass MPIR besser ist als GMP, ich habe die Entwicklungen der letzten Jahre nicht verfolgt.

Ich habe ja ebenfalls drei Rechner mit je vier Threads bemüht. In der Summe waren es schon zwischen 1000 und 2000 Kurven. Aber das ist natürlich ein Stück weit Glücksache. Die Readme-Datei spricht von im Mittel 4480 Kurven für B1=11000000.



  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.46, vom Themenstarter, eingetragen 2019-11-30 10:57


Danke für die lib.

Leider sind die statischen LIBs nie lange kompatibel zur Entwicklungsumgebung. Ich wollte noch mehr optimieren und MSVC 2017 nimmt nicht mal mehr die LIBs von 2012!

Aber die MPIR.lib ist viel zu langsam!

Also werde ich alles auf die schnelle dynamische GMP.DLL umstellen, denn die sind für die Nachfolgeversionen GMP 7.xxx überall zu haben. Bedeutet viel Fleißarbeit...

So, nach 1 Tag und mit 12 parallelen Prozessen (also etwa 14400 Kurven!) kam ein Fund für eine 118stellige Zahl vom Typ b2):
GMP-ECM 7.0.4 [configured with MPIR 3.0.0
GMP-ECM 7.0.4 [configured with MPIR 3.0.0, --enable-openmp] [ECM]
Input number is 1887273861648138654444447620077088476914195314300773428971368801535292428144192548945104548041847259222654022125408493 (118 digits)
Using B1=10500000, B2=35133391030, polynomial Dickson(12), sigma=1:101089680
Step 1 took 15656ms
Step 2 took 17657ms
Run 2 out of 10000:
...
Run 1265 out of 10000:
Using B1=10500000, B2=35133391030, polynomial Dickson(12), sigma=1:2783475302
Step 1 took 17625ms
Step 2 took 15532ms
********** Factor found in step 2: 260419214480549032207585602320911517448635711
Found probable prime factor of 45 digits: 260419214480549032207585602320911517448635711
Probable prime cofactor 7247060726347060689802885449197625235662053481258383231645953154184151763 has 73 digits

Wenn man Beitrag 38 ließt, könnte jemand denken (habe auch E-Mail, wo das getan wurde) 82 * 11 s /60 = 15 min. Nein, es war eindeutig ein Zufallstreffer und dann noch im Step1!
Wenn ich bei B1=11e6 geblieben wäre, hätte ich immer noch nichts...
Deshalb variierte ich B1 auch noch und fand nun B1=10500000.




  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.47, vom Themenstarter, eingetragen 2019-11-30 18:15


Beide Primfaktoren haben zwar große Faktoren in ihren Vorgängern & Nachfolgern, aber leider nicht zur Differenz des AM, wie es laut Definition für starke Primzahlen gefordert wird:


Danke weird, das ist doch eine schöne objektive Unterscheidung von
Zahlen des Types b2) und c)=RSA.



  Profil  Quote  Link auf diesen Beitrag Link
hyperG hat die Antworten auf ihre/seine Frage gesehen.
Seite 2Gehe 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]