Faktorisieren von Zahlen (Vortrag)

Lange Zeit galt die Zahlentheorie als besonders "reine" und unanwendbare Mathematik. Spätestens durch die Einführung von Rechnern mit Ganzzahlarithmetik für große Zahlen hat sie aber ihre praktischen Möglichkeiten offenbart. So basiert etwa die Sicherheit des RSA-Verfahrens der Datenverschlüsselung darauf, dass es erheblich aufwendiger ist, eine zweihundertstellige natürliche Zahl in Primfaktoren zu zerlegen, als von einer hundertstelligen Zahl festzustellen, ob sie eine Primzahl ist. In der Tat sind es zwei verschiedene Aufgaben, festzustellen, ob eine gegebene natürliche Zahl eine Primzahl ist oder nicht bzw. einen nicht trivialen Teiler einer zusammengesetzten Zahl anzugeben.

In jüngster Zeit hat die Mathematik zu beiden Problemstellungen bedeutend verbesserte Algorithmen geliefert. So ist es jetzt möglich, solche Zahlen in überschaubarer Zeit zu faktorisieren, für die man bei einfachem Durchprobieren aller möglichen Teiler selbst beim Einsatz von Milliarden von Supercomputern deutlich mehr Zeit benötigte als die veranschlagte Lebensdauer des Universums.