Abstract (deu)
Die vorliegende Diplomarbeit behandelt das Faktorisierungsproblem, also von der Berechnung eines Teilers einer zusammengesetzten ganzen Zahl, und primär den Methoden, die sowohl historisch als auch aktuell dafür zur Anwendung kommen. Zuvor führen wir alle mathematischen Grundlagen, die wir zur Vorstellung der Faktorisierungsalgorithmen benötigen, ein. Die im Hauptteil beinhalteten Methoden zur Teilerberechnung, deren Funktionsweisen wir detailliert vorstellen, sind die Probedivision, Pollards - und (p-1)-Methode, die Elliptic Curve Method, die Methode nach Fermat, nach Legendre, der Kettenbruchalgorithmus, das quadratische Sieb und das Zahlkörpersieb. Für ein besseres Verständnis geben wir einige der Algorithmen als funktionstüchtigen Code des Algebra- Programms PARI/GP an und testen diese auf ihre Geschwindigkeit und Eigenschaften. Zwei Fragen schenken wir bei der Beschreibung dieser Methoden besondere Beachtung:
1) Wie schnell arbeitet der jeweilige Algorithmus?
2) Spielen Charakteristika der zu faktorisierenden Zahlen eine Rolle?
Diese Fragestellungen sind im Besonderen im Anwendungsbereich des Faktorisierungsproblems, dem RSA-Verfahren in der Verschlüsselungstheorie, von zentraler Bedeutung, da die Sicherheit des Verfahrens auf deren Komplexität beruht. Danach nehmen wir aktuelle Faktorisierungsprogramme praktisch unter die Lupe, testen also mittels ausgewählter Zahlen ihre Faktorisierungsgeschwindigkeit. Abschließend erfolgt wir eine Zeitreise durch die Faktorisierungsgeschichte, eine Analyse des gegenwärtigen Forschungsstandes und ein Blick in die Zukunft der Zahlenfaktorisierung.