Faktorisierungsverfahren für ganze Zahlen

Abstract

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.

This diploma thesis is about the factorization problem, i.e. to compute a factor of a composite integer, and primary the historical and current methods to do this. First of all we discuss the mathematical background we need to present the factorization algorithms. The main part of this thesis, the detailed introductions of the factorization algorithms, will cover the trial division algorithm, Pollard's Rho- and (p-1)-method, the elliptic curve method, Fermat's factorization method, Legendre's factorization method, the continued fraction method, the quadratic sieve and the number field sieve. For a better understanding we specify for some of the methods a working source code for the algebra software PARI/GP, which we will check for speed and properties. The two following questions will cause our special interest:
 1) How fast terminates the algorithm?
 2) Do the characteristics of the factoring numbers play a role?
 These questions are in particular important for the RSA-algorithm in the cryptography, where the factorization problem plays the central part for the security.
 Afterwards we test some of the current factorization softwares for their speed and finally we go on a time travel of the factorization history, analyze the state of the art and look into the future of the integer factorization.