Open Daily: 10am - 10pm | Alley door pickup 10am - 7pm 3038 Hennepin Ave Minneapolis, MN
612-822-4611

  • Open Daily: 10am - 10pm
    Alley-side Pickup: 10am - 7pm

    3038 Hennepin Ave Minneapolis, MN
    612-822-4611

Open Daily: 10am - 10pm | Alley-side Pickup: 10am - 7pm
3038 Hennepin Ave Minneapolis, MN
612-822-4611
Schnelle modulare Exponentiation

Schnelle modulare Exponentiation

Schmidt, Uwe

Paperback

General Computers

ISBN10: 3838689259
ISBN13: 9783838689258
Publisher: Diplom.de
Published: Aug 2 2005
Pages: 124
Weight: 0.38
Height: 0.29 Width: 5.83 Depth: 8.27
Language: German
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

Also in

General Computers

View All