Universitätsbibliothek Wien

Faktorisierungsverfahren für ganze Zahlen

Wolf, Manuel (2012) Faktorisierungsverfahren für ganze Zahlen.
Diplomarbeit, Universität Wien. Fakultät für Mathematik
BetreuerIn: Burde, Dietrich

[img]
Vorschau
PDF
Alle Rechte vorbehalten / All rights reserved

Download (1191Kb)
URN: urn:nbn:at:at-ubw:1-30345.60297.862369-0
URN: urn:nbn:at:at-ubw:1-30345.60297.862369-0

Link zu u:search

Abstract in 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.

Schlagwörter in Deutsch

Zahlenfaktorisierung / Faktorisierungsverfahren / Primfaktorzerlegung / RSA-Verfahren / Algorithmen

Abstract in 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 in Englisch

Integer Factorization / Factorization Algorithms / Prime Factorization / RSA-Algorithm / Algorithms

Dokumentenart: Hochschulschrift (Diplomarbeit)
AutorIn: Wolf, Manuel
Titel: Faktorisierungsverfahren für ganze Zahlen
Umfangsangabe: 107 S.
Institution: Universität Wien
Fakultät: Fakultät für Mathematik
Publikationsjahr: 2012
Sprache: ger ... Deutsch
BetreuerIn: Burde, Dietrich
BeurteilerIn: Burde, Dietrich
Klassifikation: 31 Mathematik > 31.14 Zahlentheorie
AC-Nummer: AC09387528
Dokumenten-ID: 20401
(Das PDF-Layout ist ident mit der Druckausgabe der Hochschulschrift.)

Urheberrechtshinweis: Für Dokumente, die in elektronischer Form über Datennetze angeboten werden, gilt uneingeschränkt das österreichische Urheberrechtsgesetz; insbesondere sind gemäß § 42 UrhG Kopien und Vervielfältigungen nur zum eigenen und privaten Gebrauch gestattet. Details siehe Gesetzestext.

Dokument bearbeiten (nur für AdministratorInnen) Dokument bearbeiten (nur für AdministratorInnen)