Kryptographie-Grundlagen

Primfaktorzerlegung

Die Zerlegung einer (großen) Zahl in ihre Primfaktoren ist eines der ältesten Probleme der Zahlentheorie. Neben der versuchsweisen Division, die einfach, aber bei großen Zahlen sehr zeitaufwendig ist, existieren einige effizientere Faktorisierungsalgorithmen, von denen an dieser Stelle nur der neueste und vermutlich bald auch schnellste, das so genannte Zahlenkörpersieb (Number Field Sieve, NFS) genannt werden soll.

Im Moment ist man in der Lage, Zahlen mit etwa 130 Dezimalstellen (entspricht zirka 440 Bit) zu faktorisieren. 1993 benötigte man dazu etwa 5000 MIPS-Jahre (eine theoretische Größe für den Rechenaufwand). Vor einiger Zeit schaltete man über das Internet 1600 Rechner zusammen, die gemeinsam etwa acht Monate brauchten. Nach Aussage der beteiligten Wissenschaftler wäre der Aufwand unter Verwendung des neuen NFS nur ein Zehntel dieser Zeit gewesen. Der Rechenaufwand zur Faktorisierung einer großen Zahl mit n Stellen mit Hilfe des NFS (seine heuristische, asymptotische Laufzeit) lässt sich mit der folgenden Formel abschätzen:

Wie man sieht, steigt der Rechenaufwand mit der Länge der zu faktorisierenden Zahl exponenziell an. Die Primfaktorzerlegung großer Zahlen ist ein seit langem sehr intensiv untersuchtes Problem. Große Fortschritte in Form neuer, wesentlich schnellerer Algorithmen sind daher in diesem Bereich unwahrscheinlich. Dies macht Kryptoalgorithmen, die auf der Primfaktorzerlegung beruhen, zu guten Kandidaten für sichere Kryptoalgorithmen.