DeFacto: Primfaktorzerlegung

Knacken von Verschlüsselungen bei den Projekten RC5-72, Enigma@Home und anderen
Nachricht
Autor
test123
XBOX360-Installer
XBOX360-Installer
Beiträge: 68
Registriert: 26.02.2008 21:45

#217 Ungelesener Beitrag von test123 » 26.02.2008 21:49

Ja, dieser cyrix42 bin ich.

Wenn du wissen willst, warum ich bei WuMV gesperrt wurde, dann solltest du dir dieses Form mal genau anschauen. Ich wurde gesperrt, weil ich RT-"Kritikern", die sich selbst als Laien outen, empfohlen habe ersteinmal die nötige PPhysik und Mathematik zu lernen um zu verstehen, was sie da eigentlich tun... Credo: Nur was du verstanden hast, kannst du auch widerlegen. Frau J.Lopez und Co. begehn nämlich jede Menge logischer Fehler, aber gut. Kritik ist bei dieser Gemeinschaft offenbar unerwünscht, sollte sie von der vorherrschenden Meinung dort Abweichen. Ich verweise mal auf das Forum AlphaCentauri, dort erfährt man weiteres über WumV...

zum Inhalt hier:

Leider reicht der Platz im Gästebuch nicht aus eine ordentliche Analyse zu machen. Aber das sollte man tun, bevor man das Projekt groß feiert, denn es ist nichts weiter als ein naiver Versuch. :)

Das kann man Schülern auch nicht vorwerfen, aber die Rechenzeit ist dort einfach nur verschwendet...

Grüße,
Cyrix

test123
XBOX360-Installer
XBOX360-Installer
Beiträge: 68
Registriert: 26.02.2008 21:45

#218 Ungelesener Beitrag von test123 » 26.02.2008 21:57

Und jetzt mal ernsthaft:

Also: Was dort beschrieben wird, ist i.W. ein zufälliges Raten der einzelnen Bits der Faktoren, und ein Testen, ob die beiden zufällig gewählten Faktoren denn Passen. Dazu werden zuerst immer die letzten Bits betrachtet und das ganze dann "von niedrigen zu hohen Bits" hochgezogen.

Pro Bit gibt es nach deren Argumentation zwei Möglichkeiten. Gelangt man in eine "Sackgasse", so muss nach Back-Tracking in der vorhergehenden Stufe das Bit geändert werden. Geht das nicht, so in der vorvorgehenden, usw. Wir landen also in einem binären Suchbaum der Tiefe log(n) (um genau zu sein: log_2(sqrt(n)), was aber auf das gleiche Hinausläuft), und müssen potentiell alle Knoten chekcen. (Im Erwartungswert immernoch die Hälfte, was für die Zeitkomplexität keine Rolle spielt). Damit fallen schonmal O(sqrt(n)) zu überprüfende Knoten an.

In jedem dieser Knoten sind aber noch einmal O(log(n)) Operationen durchzuführen, sodass wir insgesamt auf eine Komplexität von O(log(n)sqrt(n)) in der zu faktorisierenden Zahl[!] n kommen. Man gibt im normalfall aber die Komplexität in Abhängigkeit der Eingabelänge an, sodass wir auf ziemlich exponentielles Verhalten kommen!


Zum Vergleich: Probedivision läuft auch in O(sqrt(n))...

Grüße,
Cyrix

test123
XBOX360-Installer
XBOX360-Installer
Beiträge: 68
Registriert: 26.02.2008 21:45

#219 Ungelesener Beitrag von test123 » 26.02.2008 21:58

Anders formuliert: Man kommt durch Raten schneller zum Ziel als durch dieses Programm! Oder wieder anders formuliert: Seinen Rechner darauf anzusetzen ist ungefähr genauso gut wie Geld zu verbrennen... ;)


Grüße,
Cyrix

Benutzeravatar
Myrmidon
Brain-Bug
Brain-Bug
Beiträge: 542
Registriert: 04.10.2007 17:55

#220 Ungelesener Beitrag von Myrmidon » 26.02.2008 21:59

test123 hat geschrieben:Ja, dieser cyrix42 bin ich.

Das kann man Schülern auch nicht vorwerfen, aber die Rechenzeit ist dort einfach nur verschwendet...

Cyrix
junge interessierte leute brauchen rechenkapazität, rechenkraft.net hat welche. ob deren projekt zum erfolg führt ist erstmal zweitrangig, da es für den verein ja hauptsächlich um die präsenz geht.
PS: das deren algorithmus schlechter ist hab cih mir fast gedacht, da ich die gefundene Priemzahl einmal mit dem tool der seite www.primzahlen.de getestet hatte und einmal mit dernen prog. und rein subjektig war das programm der beiden wesentlich langsamer.
Bild

Bild

Benutzeravatar
yoyo
Vereinsvorstand
Vereinsvorstand
Beiträge: 8045
Registriert: 17.12.2002 14:09
Wohnort: Berlin
Kontaktdaten:

#221 Ungelesener Beitrag von yoyo » 26.02.2008 22:01

Hallo,
um ehrlich zu sein kann ich mir auch nicht vorstellen dass 2 Schüler die Faktorisierung beschleunigen, einen besseren Algorythmus finden als bisherige Mathematiker. Aber es könnte ja passieren. Aber dafür gibts ja auch die JugendForscht Gremien, die das besser analysieren können als ich. Auch weiß ich nicht genau was denn nun konkret das Forschungsobjekt ist, nur der Algorythmus oder auch die verteilte Rechenumgebung oder beides oder noch was anderes. Daher werde ich das Projekt zumindest erstmal bis zum nächsten JugendForscht Meilenstein weiter unterstützen.

Du könntest den Algorythmus, den sie verwenden und die die "besser" sind ja mal versuchen für mich Laien zu erläutern.

yoyo

PS: Herzlich Willkommen hier bei uns!!
HILF mit im Rechenkraft-WiKi, dies gibts zu tun.
Wiki - FAQ - Verein - Chat

Bild Bild

test123
XBOX360-Installer
XBOX360-Installer
Beiträge: 68
Registriert: 26.02.2008 21:45

#222 Ungelesener Beitrag von test123 » 26.02.2008 22:02

Nun, die Schüler sollten wenigstens etwas sinnvolles mit der Rechenkraft, die ihnen hier zur Verfügung gestellt wird machen!

Ansonsten ist dies nur ein "wir Heizen unseren Raum jetzt mal nicht mit der Heizung sondern mit Prozessoren-Abwärme". Leider passiert hier nicht mehr!
Nochmal: Sogar der völlig naive Ansatz ist besser als das dort vorgestellte Programm!


Cyrix

test123
XBOX360-Installer
XBOX360-Installer
Beiträge: 68
Registriert: 26.02.2008 21:45

#223 Ungelesener Beitrag von test123 » 26.02.2008 22:05

Hallo yoyo!

Die Mathematik hinter aktuellen Verfahren ist nicht trivial (eigentlich wollte ich an der Schiene promovieren, klappt jetzt nicht, aber gut).

Wie gesagt: Was die Schüler hier machen ist verklausuliert folgendes:

Wenn ich eine gegebene Zahl n in ein Produkt a*b zerlegen will, dann kann ich das versuchen so zu machen: Ich rate a und b, berechne das Produkt, und schaue nach, ob n herausgekommen ist. Wenn ja, dann freue ich mich, wenn nein, probiere ich weiter.

(Ein klein wenig intelligenter machen sie es schon, aber das ist etwa das, was da in dem Programm passiert...)


Grüße,
Cyrix

test123
XBOX360-Installer
XBOX360-Installer
Beiträge: 68
Registriert: 26.02.2008 21:45

#224 Ungelesener Beitrag von test123 » 26.02.2008 22:09

(Die Leistung der Schüler in dem Projekt ist eben nicht die Faktorisierung, sondern "höchstens" [ohne es klein reden zu wollen] die Architektur der Verteilung der Aufgaben auf verschieden Rechner.)


Grüße,
Cyrix

Benutzeravatar
Michael H.W. Weber
Vereinsvorstand
Vereinsvorstand
Beiträge: 22419
Registriert: 07.01.2002 01:00
Wohnort: Marpurk
Kontaktdaten:

#225 Ungelesener Beitrag von Michael H.W. Weber » 26.02.2008 22:11

Ich selbst habe von Mathematik nicht ausreichend Ahnung, um das zu beurteilen. Sollte die Kritik berechtigt sein - und ich habe die beiden DeFacto-Betreiber per eMail über die Einwände informiert mit der Bitte um Stellungnahme - dann ist klar, daß wir hier nicht längerfristig unsere Rechenzeit investieren können, da es sinnvollere Projekte gibt. Was wir aber in jedem Fall tun sollten - sozusagen aus Solidarität - ist eine Unterstützung am 4. März zu gewähren. Wichtig wäre nun zu wissen, wo das Projekt Priorität legt.

Michael.
Zuletzt geändert von Michael H.W. Weber am 26.02.2008 22:12, insgesamt 1-mal geändert.
Fördern, kooperieren und konstruieren statt fordern, konkurrieren und konsumieren.

http://signature.statseb.fr I: Kaputte Seite A
http://signature.statseb.fr II: Kaputte Seite B

Bild Bild Bild

Benutzeravatar
EdmundBlackadder
Task-Killer
Task-Killer
Beiträge: 784
Registriert: 20.02.2008 17:56
Kontaktdaten:

schade, dass der Traum so schnell platzt!?

#226 Ungelesener Beitrag von EdmundBlackadder » 26.02.2008 22:12

Michael H.W. Weber hat geschrieben:
laguna2 hat geschrieben:Huh? Laut Taskmanager rechnet er was...
Nur was?
Ja, einfach Hirn ausschalten und rechnen lassen (Hintergrund des Projekts wurde oben ja gepostet).

Michael.
Nun, ohne hier allzu kritisch zu sein, möchte ich anmerken, das das schon naiv ist, in ein Projekt einzusteigen, ohne ansatzweise prüfen zu lassen, ob das einen "Sinn" macht, wie auch immer. Sowas können uns nur EU-weit leisten oder auch in Bayern! Manche rechnen schon lange bei Seti nicht mehr mit und hier wird einfach blind losgeschlagen. Ich hatte gehofft, dass mal irgendwer den Algorithmus anschaut und das auch erklären kann. Vielleicht hätten die 2 vor dem Start entsprechende "Experten" aufsuchen sollen. Wenn das alles stimmt, finde ich es schon merkwürdig, dass der Algorithmus so schlecht sein soll.
Also ich für meinen Teil bleibe noch dabei bis 4.3. Gut, ich kapiere andere Projekte auch nur ansatzweise. Das hält mich aber nicht von DC ab. Ich bin lernwillig, sonst wäre ich nicht hier.

Euer Edmund
Verschenke 2 Stück Lenovo T400 (Screen defekt) 4GB Laptops mit Dockingstation und 17" Monitor.
Ritschie hat geschrieben:Ich will ja nicht nur für Credits rechnen, sondern 'nen sinnvollen Beitrag leisten.

test123
XBOX360-Installer
XBOX360-Installer
Beiträge: 68
Registriert: 26.02.2008 21:45

#227 Ungelesener Beitrag von test123 » 26.02.2008 22:15

Hallo!

Nun, wer seinen Rechner wozu benutzt, ist noch seine Sache. Ich wollte nur angeben, dass hier der Stromverbrauch für etwas vollkommen Sinnloses verpulvert wird.

Ihr rechnet, um den zwei Leuten ein gutes Gefühl zu geben, nicht aber, um inhaltlich etwas vorwärts zu bringen...


Grüße,
Cyrix

Benutzeravatar
Michael H.W. Weber
Vereinsvorstand
Vereinsvorstand
Beiträge: 22419
Registriert: 07.01.2002 01:00
Wohnort: Marpurk
Kontaktdaten:

Re: schade, dass der Traum so schnell platzt!?

#228 Ungelesener Beitrag von Michael H.W. Weber » 26.02.2008 22:19

EdmundBlackadder hat geschrieben:
Michael H.W. Weber hat geschrieben:
laguna2 hat geschrieben:Huh? Laut Taskmanager rechnet er was...
Nur was?
Ja, einfach Hirn ausschalten und rechnen lassen (Hintergrund des Projekts wurde oben ja gepostet).

Michael.
Nun, ohne hier allzu kritisch zu sein, möchte ich anmerken, das das schon naiv ist, in ein Projekt einzusteigen, ohne ansatzweise prüfen zu lassen, ob das einen "Sinn" macht, wie auch immer.
Ja, das ist korrekt, allerdings bringst Du hier mein Posting ziemlich aus dem Zusammenhang. Es bezog sich darauf, daß zum technischen Betrieb des Clients nicht weiter "herumgedoktort" werden muß. Keineswegs ging es um den Inhalt des Projekts. Deswegen hatte ich extra auch nochmal auf die URL mit der Projektbeschreibung hingewiesen, damit jeder vorher dort nachsieht, ob es sinnvoll ist. Und natürlich hatte ich schon erwartet, daß Einwände von unseren mathematisch besser betuchten kommen würden, falls da etwas offensichtlich ungereimt ist. Aber wie gesagt, jetzt stellt sich erst mal die Frage, wo die Priorität bei dem Projekt liegt: Ist es der mathematische Ansatz oder z.B. die Aufgabenverteilung auf verschiedene Rechner.

Michael.
Fördern, kooperieren und konstruieren statt fordern, konkurrieren und konsumieren.

http://signature.statseb.fr I: Kaputte Seite A
http://signature.statseb.fr II: Kaputte Seite B

Bild Bild Bild

Antworten

Zurück zu „Kryptographie“