Inhaltsangabe: Zusammenfassung: In dieser Arbeit werden Algorithmen
dargestellt und analysiert, die die in kryptographischen Verfahren
häufig vorkommende modulare Exponentiation a^e mod m möglichst schnell
berechnen. Nach der Einleitung in Kapitel 1 werden in Kapitel 2 einige
wichtige mathematische Grundlagen vorgestellt. Dabei handelt es sich um
den euklidischen Algorithmus, den erweiterten euklidischen Algorithmus,
um die modulare Arithmetik, Primzahlen und die für die Beurteilung der
Komplexität von Algorithmen wichtige O-Notation. In Kapitel 3 werden
einige kryptographische Verfahren, in denen die modulare Exponentiation
eine große Rolle spielt, beschrieben. Zur Beurteilung der Komplexität
wird für jedes Verfahren aufgeführt, wie oft und mit welchen Bitlängen
die modulare Exponentiation berechnet wird. Die modulare Multiplikation
ist Thema des Kapitels 4. Algorithmen für die Multiplikation und für die
Reduktion nach der „Schulmethode" werden dargestellt. Es wird gezeigt
wie mit einem speziellen Algorithmus für die Quadrierung eine
Beschleunigung um ca. 25% erzielt werden kann. Ein rekursiver
Multiplikationsalgorithmus, der für sehr große Zahlen schneller als der
klassische Algorithmus arbeitet, wird vorgestellt. Den Schluss des
Kapitels 4 bildet ein Abschnitt über die Montgomerymultiplikation. In
Kapitel 5 werden Methoden zur modularen Exponentiation behandelt, die
ohne Vorberechnungen auskommen. Hierbei handelt es sich um die
Binär-Methode, die m-ary-Method und die Fenstertechnik. Neben der Anzahl
der Multiplikationen ist auch die Anzahl der während der Berechnung zu
speichernden Zwischenergebnisse ein wichtiger Parameter für die
Ausführungsgeschwindigkeit. Beide Parameter werden für die jeweiligen
Verfahren diskutiert. Die modulare Exponentiation mit Vorberechnungen
wird in Kapitel 6 behandelt. Dort wird zunächst auf die Additionsketten
eingegangen. Es wird gezeigt, dass das mathematische Problem des Findens
einer möglichst kurzen Additionskette, gleichbe
