Title: Schnelle Algorithmen für große Zahlen und ihre Implementierung in C#
Language: Deutsch
Authors: Glavanovits, Hannes 
Qualification level: Diploma
Keywords: Algorithmen; große Zahlen; ggT; FFT; Multiplikation großer Zahlen; Potenzen
Advisor: Wiesenbauer, Johann
Issue Date: 2007
Number of Pages: 110
Qualification level: Diploma
Abstract: 
Große Zahlen spielen in der heutigen Computerarithmetik eine entscheidende Rolle. Sie finden Verwendung in der Kryptographie, Faktorisierungsproblemen, Primzahltests, ... In diesen Gebieten werden Berechnungen mit sehr großen Zahlen durchgeführt. Zu diesem Zweck sind korrekte Losungen mit einer schnellen Implementation nötig. Ein symbolisch korrekter Algorithmus kann eine nichtakzeptable Laufzeit besitzen. Im folgenden werden die bekanntesten und am meisten verbreitesten Algorithmen für die Multiplikationen, Potenzen sowie dem Finden des größten gemeinsamen Teilers vorgestellt. Weiters erfolgt eine Implementierung in C# innerhalb einer Klassenstruktur, welche die Basisoperationen bereitstellt.
Es werden die wichtigsten Technicken vorgestellt. Bei der Multiplikation sind dies die theoretischen Ansätze zur Aufwandsreduktion sowie mehrere Varianten der FFT und ihre Implementierungsmöglichkeiten in komplexen, reellen bzw. ganzzahligen Körpern, Ringen. Neben der Multiplikation wird auch eine andere grundlegende arithmetische Operation erläutert, das Potenzieren. Hierbei ist zu unterscheiden zwischen verschiedenen Methoden, mit und ohne Vorberechnung, sowie ob modulo N reduziert wird oder nicht. Das Finden des größten, gemeinsamen Teilers ist ein Grundproblem der Faktorisierung, sowie im Bereich der Untersuchung von Primzahlen. Der Euklidische Algorithmus und alle seine Varianten werden vorgestellt, sowie spezielle Algorithmen für eine gegebene Aufgabenstellung, z.B. für große Zahlen oder Inversionen.
Die Implementierung der vorgestellten Algorithmen erfolgte in C#.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-20271
http://hdl.handle.net/20.500.12708/14590
Library ID: AC05034667
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

23
checked on Feb 22, 2021

Download(s)

94
checked on Feb 22, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.