Titelaufnahme

Titel
Schnelle Algorithmen für große Zahlen und ihre Implementierung in C# / Hannes Glavanovits
VerfasserGlavanovits, Hannes
Begutachter / BegutachterinWiesenbauer, Johann
Erschienen2007
Umfang110 Bl.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2007
SpracheDeutsch
Bibl. ReferenzOeBB
DokumenttypDiplomarbeit
Schlagwörter (DE)Algorithmen / große Zahlen / ggT / FFT / Multiplikation großer Zahlen / Potenzen
URNurn:nbn:at:at-ubtuw:1-20271 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Schnelle Algorithmen für große Zahlen und ihre Implementierung in C# [0.51 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

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#.