Lade Inhalt...

Schnelle modulare Exponentiation

Bachelorarbeit 2005 118 Seiten

Informatik - Theoretische Informatik

Zusammenfassung

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, gleichbedeutend mit dem Finden eines möglichst schnellen Exponentiationsalgorithmus ist. Im Unterabschnitt 6.1.1 wird auf die Möglichkeit eingegangen, durch mehrere parallel arbeitende Multiplizierer die Exponentiation zu beschleunigen. Es folgt ein Abschnitt über Divisionsketten, ein Verfahren, das nicht nur auf die Reduzierung der Multiplikationen abzielt. Durch Verringerung von zu speichernden Zwischenergebnissen werden langsame Speicherzugriffe verhindert und so eine Beschleunigung der […]

Details

Seiten
118
Erscheinungsform
Originalausgabe
Jahr
2005
ISBN (eBook)
9783832489250
ISBN (Buch)
9783838689258
Dateigröße
1.2 MB
Sprache
Deutsch
Katalognummer
v224100
Institution / Hochschule
FernUniversität Hagen – Informatik
Note
1,3
Schlagworte
kryptographie square multiply fenstertechnik additionskette divisionskette

Autor

Zurück

Titel: Schnelle modulare Exponentiation