Detailansicht
Faktorisierungsverfahren für ganze Zahlen
Manuel Wolf
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Dietrich Burde
DOI
10.25365/thesis.20401
URN
urn:nbn:at:at-ubw:1-30345.60297.862369-0
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
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.
Abstract
(Englisch)
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.
Schlagwörter
Schlagwörter
(Englisch)
Integer Factorization Factorization Algorithms Prime Factorization RSA-Algorithm Algorithms
Schlagwörter
(Deutsch)
Zahlenfaktorisierung Faktorisierungsverfahren Primfaktorzerlegung RSA-Verfahren Algorithmen
Autor*innen
Manuel Wolf
Haupttitel (Deutsch)
Faktorisierungsverfahren für ganze Zahlen
Paralleltitel (Englisch)
Factorization Algorithms for Integers
Publikationsjahr
2012
Umfangsangabe
107 S.
Sprache
Deutsch
Beurteiler*in
Dietrich Burde
Klassifikation
31 Mathematik > 31.14 Zahlentheorie
AC Nummer
AC09387528
Utheses ID
18247
Studienkennzahl
UA | 405 | | |