[HaBo]

SPaRXLi

Anzeige

Hi,
kann mir einer den Algorithmus des "General Number Field Sieve" zum Faktorisieren erklären oder einen Link mir Informationen über diesen geben?

Gruß Thomas!

Akkad

Hast dir ja was ganz nettes ausgesucht :-)


Also :
Erst diese Version des Number Field Sieves lässt es zu, jede beliebige ganze Zahl in Primfaktoren zu zerlegen.
( Die anderen Versionen Quadratic Sieve und Number Field Sieve waren nciht in der Lage diese Aufgabe zu erfüllen. )
Es ist für Zahlen mit mehr als 130 Stellen der bislang beste Algorithmus.

Es ist aber noch nicht möglich, mit diesen Algorithmen ernsthaft einen Schlüssel knacken zu können. Im Rahmen eines Wettbewerbes sollte z.B. die Zahl

10941738641570527421809707322040357612003732945449 2059909138421
31476349984288934784717997257891267332497625752899 7818337970765
37244027146743531593354333897

in ihre beiden Primfaktoren zerlegt werden. Diese Zahl hat genau 155 Stellen, was einer Schlüssellänge von 512-bit entspricht. Die Faktorisierung dauerte 7.4 Monate, allerdings auch mit folgender Hardwareunterstützung :




160 175-400 MHz SGI and Sun workstations
8 250 MHz SGI Origin 2000 processors
120 300-450 MHz Pentium II PCs
4 500 MHz Digital/Compaq boxes
1 Cray C916



Darauf basierend kann man folgende Werte berechnen, die weitere gebräuchliche Schlüssellängen berechnen würden :



Schlüssellänge Anzahl Ziffern Geschätzte Dauer
512-bit 155 c.a. 8 Monate
768-bit 232 c.a. 3 Jahre
1024-bit 309 c.a. 10 Jahre
2048-bit 617 c.a. 500 Jahre


Ich hoffe ich konnte dir einigermassen weiterhelfen, wen du mehr Infos brauchst, kannst du gerne wieder posten.

SPaRXLi

Vielen Dank, für deine ausfürliche Antwort, Akkad!
Ist der "General Number Field Sieve" eigentlich ein Faktorisierungsverfahren, nach dem Prinzip des "Quadratischen Siebs" oder ist dieses wiederum ein ganz anderes Verfahren?
Ich bräuchte noch dringend Informationen über einen dieser Algorithmen, also die genaue Beschreibung dieser!
Ist es einfach, diese Algorithmen in einer Programmiersprache (TP) umzusetzen?
Ich habe schon 3 Programme zum Faktorisieren geschrieben ("Probedivision", "Fermat-Methode", "(p-1) Methode") und wollte diese mit einem der schnellsten Faktorisierungsalgorithmen heutzutage vergleichen.
Es würden mir keine vorhandenen Programme oder Vergleichsfakten weiterhelfen, da ich dieses alles für meine Facharbeit brauche und es bei ihr auf eigenständige Erkenntnisse ankommt.

Also vielen Dank im Vorraus!
Gruß Thomas!