Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-1393
Authors: Hahn, Georg
Title: Parallelisierte Faktorisierung mit dem Quadratischen Sieb
Online publication date: 1-Feb-2018
Year of first publication: 2018
Language: german
Abstract: Titel: Parallelisierte Faktorisierung mit dem Quadratischen Sieb Seit Euklid um 300 v. Chr. bewies, dass jede natürliche Zahl eine eindeutige Darstellung in Primfaktoren besitzt, ist die Faktorisierung natürlicher Zahlen ein Forschungsgebiet der Mathematik. Allerdings blieb die sogenannte Probedivision ("Trial Division"), d.h. das Probieren aller Teiler bis zur Wurzel der zu faktorisierenden Zahl, bis zum 17. Jahrhundert die einzige bekannte Faktorisierungsmethode. 1643 formulierte Pierre de Fermat ein neues Faktorisierungsverfahren, das eine Zahl als nicht triviale Differenz zweier Quadrate darstellt. Aus einer solchen Darstellung lassen sich anschließend zwei Teiler, die nicht notwendig Primzahlen sein müssen, berechnen. Diese Technik wird im folgenden Kapitel dargestellt und liefert zudem die Grundlage für weitere Faktorisierungsverfahren wie der Kettenbruchmethode von Morrison-Brillhart, dem Quadratischen Sieb und dem Zahlkörpersieb sowie deren Varianten. Das Quadratische Sieb wurde 1981 von Carl Pomerance vorgestellt und basiert auf der von Fermat eingeführten Strategie, eine Quadratdarstellung zu konstruieren. Es baut auf vorherige Ansätze von Kraitchik und Dixon auf. Das Verfahren war bis 1993 die schnellste bekannte Faktorisierungsmethode, bis es durch eine Weiterentwicklung, dem Zahlkörpersieb ("Number Field Sieve" NFS) abgelöst wurde, das bis heute als schnellstes Verfahren gilt. Dennoch zeigt sich, dass das Quadratische Sieb Zahlen bis ca. 110 Stellen in der Praxis am schnellsten faktorisiert. Im zweiten Kapitel der Arbeit wird die Theorie der Basisversion des Quadratischen Siebes vorgestellt. Es folgen Details zur algorithmischen Umsetzung und speziell der Bezug auf den parallelisierten Einsatz in der Praxis. Dazu wurde der Algorithmus im Rahmen dieser Arbeit als Server-Client-Netzwerk realisiert, dessen Details der Implementierung im 3. Kapitel vorgestellt werden. Es folgen eine theoretische Laufzeitbetrachtung sowie Testfälle des parallelisierten Einsatzes und eine anschließende Diskussion der Ergebnisse im 4. und 5. Kapitel. Die Arbeit schließt mit einem Ausblick auf Erweiterungen des Basisalgorithmus des Quadratischen Siebes im 6. Kapitel. Title: Parallelised factorisation using the quadratic sieve The factorisation of integers has become an active research area in mathematics ever since Euclid proved the existence of a unique prime factor decomposition around 300 BC. However, the so-called trial division, that is the factorisation of an integer by trying all prime factors up to its square root, remained the only known factorisation method until the 17th century. In 1643 Pierre de Fermat proposed a new factorisation method which aimed to express an integer as non-trivial difference of two squares. Expressing an integer in such a way allows one to calculate two divisors which do not need to be prime. Fermat’s technique will be introduced in the next chapter as it lays the foundations of several other factorisation algorithms, for instance the continued fraction factorisation of Morrison-Brillhart, the quadratic sieve algorithm as well as the number field sieve and its variants. The quadratic sieve was introduced by Carl Pomerance in 1981. It is based on Fermat’s idea to express an integer as the difference of two squares and extends earlier approaches of Kraitchik and Dixon. The quadratic sieve remained the fastest known factorisation method until its successor, the number field sieve (NFS), was presented in 1993. The NFS is considered the fastest method to date. However, the quadratic sieve empirically proves to be faster in practice for integers up to 110 digits. The second chapter of the thesis presents a basic version of the quadratic sieve algorithm, followed by details on its implementation, in particular with a view to its parallelisation. To this end, the algorithm was implemented as a server-client network system. Details of the implementation are given in chapter 3. A theoretical runtime analysis, including test cases of a parallelised application of the algorithm, and a discussion of all results can be found in chapters 4 and 5. The thesis concludes with an outlook on extensions of the basic quadratic sieve algorithm in chapter 6.
DDC: 510 Mathematik
510 Mathematics
Institution: Johannes Gutenberg-Universität Mainz
Department: FB 08 Physik, Mathematik u. Informatik
Place: Mainz
ROR: https://ror.org/023b0x485
DOI: http://doi.org/10.25358/openscience-1393
URN: urn:nbn:de:hebis:77-diss-578476
Version: Original work
Publication type: Masterarbeit
License: In Copyright
Information on rights of use: https://rightsstatements.org/vocab/InC/1.0/
Extent: 34 S.
Annotation: (Bachelorarbeit)
Appears in collections:JGU-Publikationen

Files in This Item:
  File Description SizeFormat
Thumbnail
57847.pdf195.21 kBAdobe PDFView/Open