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.

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