Da einige der vielen Reicheleutekinder hier sicher das ein oder andere Megahertz oder sogar einen ganzen CPU Core am rumgammeln haben, möchte ich mal an dieser Stelle auf das Defacto genannte Faktorisierungsprojekt hinweisen. 2 Schüler eines Info LK haben einen neuen Algorithmus für die Faktorisierung einer großen Dezimalzahl (>100 Bit) entworfen und möchten damit bei JugendForscht teilnehmen.


Was ist denn Faktorisierung?
Grob gesagt ist das die Zerlegung einer natürlichen Zahl n (also 1,2,3,4..) in 2 Faktoren p und q, die zusammen multipliziert n ergeben. Dabei sind p und q Primzahlen, n jedoch nicht. Z.B. ist die Faktorisierung von n=33: p=11 und q=3 -> p*q = 11*3 = 33.

Wozu ist das denn gut?
Die Sicherheit verschiedener sog. asymmetrische Verschlüsselungssysteme (bekanntester Vertreter ist RSA) beruht darauf, dass obige angesprochene Faktorisierung für große Dezimalzahlen n schwer ist. Dies ist auch als Faktorisierungsannahme bekannt. Es wird angenommen, dass Faktorisierung ein Problem ist, dass für sehr große Dezimalzahlen nur in einer nicht annehmbaren Zeit und nur mit großem Rechenaufwand gelöst werden kann (grob gesagt). Würde jemand beweisen können, dass Faktorisierung leicht ist, bzw. fände jemand einen Algorithmus, der eine annehmbare Laufzeit bietet, wäre die Sicherheit dieser Kryptosysteme nicht mehr gegeben.

Und was hat das jetzt mit den Infoheinis zu tun?
Die haben einen Algorithmus zu diesem Problem entworfen und wollen zeigen, dass er für wirklich große Zahlen (weitaus mehr als 100bit) eine bessere Laufzeit bringt, als die bisher bekannten.

Okok und was zum Henker soll ich da jetzt tun?
Das Ganze braucht immer noch vieeeel Rechenkraft. Die Jungs haben ein Programm geschrieben, dass man auf seinem Rechner installiert und laufen läßt. Es verbindet sich mit den Programmen anderer Nutzer und versucht mittels verteilter Berechnung auf mehreren Rechnern eine Zahl zu faktorisieren. Je mehr Leute mitmachen, desto besser die auswertbaren Ergebnisse.

Wie gesagt treten die beiden am 04. März bei JugendForscht damit an und ich finde, das ist recht vielversprechend, auch wenn die Gefahr besteht, dass der Algorithmus absoluter Bullshit ist. Wenn ihr euch beteiligen wollt, dann bitte unter dem Usernamen #tu-dresden, denn darunter rechnen auch schon ganz paar andere Leute aus der Uni. Der der am meisten gerechnet hat, bekommt einen Sonderpreis. Ich glaube zwar nicht, dass man die Power von Rechenkraft.net schlagen kann, aber Hauptsache die TU steht oben mit drin

An die Nerds unter euch, die evtl. zuviel Zeit haben: Das Programm ist in Borland Delphi 2005 geschrieben und nur für Windows verfügbar. Das ist natürlich äußerst schlecht, denn gerade große Kisten laufen unte Unix. Den Quellcode geben die Jungs auf Anfrage raus und falls sich jemand findet, der das nach C portieren könnte, wäre das ne großartige Sache.

Hier gibt es das Programm, Leistungsindex und theoretische Grundlagen des Algorithmus: Defacto Homepage
Danke für die Aufmerksamkeit.

Ich soll mithelfen, dass PGP eines Tages womöglich geknackt wird?

Dieser Beitrag wurde von .henne: 24 Feb 2008, 22:07 bearbeitet

Es ist besser, dass Wissenschaftler zeigen können, dass ein bestimmtes Verfahren nicht sicher ist und es daraufhin überarbeitet oder nicht mehr benutzt wird, als dass jemand "böses" rausfindet, wie es geht und dieses Wissen geheim hält. In der Kryptowelt ist es ungemein wichtig fair zu spielen und das Austesten der Sicherheit von Kryptosystemen gehört dazu. Niemand möchte seine vertraulichen Daten einem System anvertrauen, das "vielleicht" sicher ist.

Ich hab ne "Leistung" von 243 und es kostet mich 30 Watt mehr Strom

Sichere Computerei, versaute Umwelt.. man kann nicht alles haben

na toll ...jetzt habt ihr mir schon alles weggerechnet

oder funktioniert das bei mir nicht ? Laut defacto homepage nichts zu tun und alle warten

Evtl. ist da grad mal wieder was scheifgelaufen. Das ganze ist ja noch ziemlich Beta und so. Einfach am Ball bleiben

124694589804397747745910035287962246228812678775942676981589128634273071725
011494672018627686987614157663094558171435147 = 189794923557009787593011659902144642471475138627063438398550028703976971148
200962201807552713384437504059124892756329713030643703750678607010900646243
00995315179077313248572844588490817536 * 219444962751747547330237450047488370802975705437255788668602651464201546946
693016388453629435205268629939697293359520503517356578582518553945125118534
678925431558424408158476373006441018320296049186298527536912605171848452813
981063237564612227634624193105714021249235288241107652014100725650067539120
61951

Das ist im Verwaltungsteil der Hompage eine der gefundenen Lösungen. Aber sollten die beiden Faktoren nicht kleiner sein als das Produkt? Oder hab ioch grad einen Knick in der Logik?

Dieser Beitrag wurde von solaris: 25 Feb 2008, 14:57 bearbeitet

Das sieht tatsächlich mal so richtig falsch aus (Hat wahrscheinlich Stormi's Kiste berechnet )

Jo is wohl falsch. Und die Jungs sind wohl mit Bugfixing beschäftigt.

Im Gästebuch steht zu lesen, dass der Server ausgefallen ist, entweder weil das Programm fehlerhaft ist, oder weil ein Idiot von Rechenkraft.net den Absturz absichtlich mittels Manipulation herbeigeführt hat. Bis zur Klärung bleibt der Server leider offline. Wenn man sich den zugehörigen Thread im Rechenkraft.net Forum ansieht, dann könntes einem zumindest ziemlich hochkommen. Keinen Plan von Mathe haben, aber sich einen auf Quad Core Rechenleistung schütteln..
Nunja ich denke, dass das alles bald wieder behoben ist.

geht wieder

... wow... die Punkte rennen ja nur so nach oben, aber der Rechenkraft EV zieht uns mal derbe davon...

im Moment sind nur 2 Rechner von uns online... wenn wir mit denen mithalten wollen fehlen uns noch locker 15 Cores...also mal ran da !!!

Leute macht mit!

Kannste knicken Da haben einige ganze Serverfarmen mit mehreren Cores, die Tag und nacht laufen. War aber zu erwarten.

Eben schrieb einer im Gästebuch von DeFacto:

Hallo!
Sorry euch das sagen zu müssen, aber euer Algorithmus ist schlecht, vom Laufzeitverhalten. Ihr sucht in einem binären Entscheidungsbaum der Höhe log(n), wobei n die zu faktorisierende Zahl ist. Da ihr potentiell alle Einträge durchprobieren müsst, seid ihr exponentiell in der Stellenanzahl der zu faktorisierenden Zahl, was schlechter ist als die bisher bekannten Faktorisierungsverfahren wie z.B. QS oder NFS. Es lohnt sich also NICHT hier Rechenzeit zu investieren. Dazu sollte man sich lieber bei anderen Profjekten wie NFS-NET oder ähnliches beteiligen! p.s.: Ihr braucht nicht weniger Rechenzeit als Probedivision! Grüße, Cyrix

Ka, ob der richtig liegt oder nicht. Habe momentan viel zu lernen und kann den Algorithmus nicht checken. Möglich wäre es aber, denn die etablierten Algorithmen sind recht ausgetüftelt und garantiert NICHT von irgendwelchen Uniabbrechern in einer Garage erfunden worden.