Bibliographic Metadata

Title
Schnelle Algorithmen für große Zahlen und ihre Implementierung in C# / Hannes Glavanovits
AuthorGlavanovits, Hannes
CensorWiesenbauer, Johann
Published2007
Description110 Bl.
Institutional NoteWien, Techn. Univ., Dipl.-Arb., 2007
LanguageGerman
Bibl. ReferenceOeBB
Document typeThesis (Diplom)
Keywords (DE)Algorithmen / große Zahlen / ggT / FFT / Multiplikation großer Zahlen / Potenzen
URNurn:nbn:at:at-ubtuw:1-20271 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Schnelle Algorithmen für große Zahlen und ihre Implementierung in C# [0.51 mb]
Links
Reference
Classification
Abstract (German)

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

Stats
The PDF-Document has been downloaded 35 times.