Schnelle Algorithmen für große Zahlen und ihre Implementierung in C#

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.<br />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.<br />Die Implementierung der vorgestellten Algorithmen erfolgte in C#.