Titelaufnahme

Titel
Faktorisierung : ein Survey
Weitere Titel
Integer Factorisation a survey
VerfasserPrinz, Stefan
Betreuer / BetreuerinHaböck, Ulrich
Erschienen2015
Datum der AbgabeJanuar 2015
SpracheDeutsch
DokumenttypBachelorarbeit
Schlagwörter (DE)Faktorisierung / Primzahlen / Elliptische Kurven / Mathematik / Zahlentheorie / Kryptographie
Schlagwörter (EN)Integer / Factorisation / Elliptic curve / Mathematics / Number Theory / Cryptography
Zugriffsbeschränkung
 _
Klassifikation
Zusammenfassung (Deutsch)

In den letzten Jahren, und vor allem nach den Enthüllungen der NSA-Affairen, wurde die Kryptographie zu einem der wichtigsten Punkten in IT-Systemen. Verschlüs- selungssoftware auf Endgeräten sind aus den privaten, kommerziellen und natürlich staatlichen Bereichen nicht mehr wegzudenken. Vor allem die asymmetrische Kryptographie stützt sich auf schwer lösbare mathematische Probleme. Die Sicherheit eines Großteils dieser Algorithmen basiert auf der Tatsache, dass es zurzeit keine effiziente Methode gibt, die Primfaktoren einer großen Zahl zu finden. Diese Verfahren würden ihre Sicherheit vollständig verlieren, man eine große Zahl schnell faktorisieren könnte. Diese Arbeit beschäftigt sich mit der Primfaktorisierung von Zahlen. Es werden vier wohlbekannte Faktorisierungsalgorithmen sowie deren Grundlagen behandelt. Die Fermatsche Methode, Pollards p − 1-Methode und die Pollard-Rho Methode und sind die drei Algorithmen, die in exponentieller Laufzeit terminieren. Der Vierte ist Hendrik W. Lenstras Elliptische-Kurven-Methode, die zu den subexponentiellen Algorithmen gehört. Die drei exponentiellen Algorithmen wurden implementiert, auf verschiedene Eingaben geprüft, gemessen, verglichen und analyisert.

Diese Arbeit überprüft Einsatzfähigkeit der Algorithmen und bestätigt die Tatsache, dass exponentielle Faktorisierungsalgorithmen für bestimmte Anwendungsfälle durchaus einsetzbar sind. Durch die Kombination mehrerer Verfahren, können auch sehr große Zahlen faktorisiert werden.

Zusammenfassung (Englisch)

Since the NSA affiars, cryptography became more and more important. Where security software was mostly interesting for companies and governmental facilities, nowadays also private people tend to pay more attention to security on their devices. Especially asymetric cryptography is based on hard mathematical problems. A big part of them is based on integer factorisation. It is difficult to find divisors of a big integer. Once an efficient method for factorisation is found, all those cryptographic methods are broken. This paper discusses four algorithms for integer factorsiation as well as the ideas they are based on. The Fermat Method, Pollard’s p − 1 Method and the Pollard-Rho-Method are the three algorithms, which terminate in exponential runtime. The fourth algorithm discussed in this paper, is Hendrik W. Lenstras Elliptic-Curve-Method, which is a subexponential time algorithm. The three exponential time algorithms were implemented, tested, compared and analysed. The results are, that also exponential time algorithms can be used for different usecases. Also big integers can be factored faster, through combination of these methods.