Schnelle Exponentiation PDF

Preview

Summary

Schnelle Exponentiation Mitschrift...

Description

Schnelle Exponentiation Überblick „Schnelle Exponentiation“, auch „binäre Exponentiation“ oder „Square & Multiply“ genannt, ist ein Algorithmus, der ca. 200 v. Chr. in Indien entdeckt wurde. Er dient der Effizienzsteigerung bei der Berechnung von Potenzen.

Idee Multiplikationen einsparen durch Quadrieren.

Beispiel z = x4 z = x·x·x·x (drei Multiplikationen) z = (x2 )2 (zwei Multiplikationen) k Funktioniert nur mit natürlichen Potenzen, d.h. x ; k ∈ N .

Funktionsweise/Algorithmus 1. Binärdarstellung von k bestimmen 2. 0 → Q; 1 → QM 3. Q: Quadrieren; M: Multiplizieren mit x 4. Exponent von links nach rechts abarbeiten

• Startwert: • Jede Binärzahl beginnt mit

2

→1 · x

– Erstes QM-Paar streichen – x als Startwert wählen

Beispiel 311 = ? 1110 = 10112 → (QM ) Q QM QM 32 = 9 92 = 81 81 · 3 = 243 2432 = 59.049 59.049 · 3 = 177.147

Tobias Braun

1 von 3

28.10.2010

Effizienz Laufzeit

• Herkömmliche Potenzierung: (k − 1) Multiplikationen • Schnelle Exponentiation: log2 k Multiplikationen (≈ Anzahl der Ziffern von k in Binärdarstellung)

Vergleich der Anzahl der Multiplikationen

x10 x100

9

4

99

8

x1.000

999

14

x1.000.000

999999

25

x1.000.000,000

999.999.999

41

Binäre Modulo-Exponentiation Beschreibung

• „Diskrete Exponentialfunktion“ • Berechnung von bx mod m Verfahren

• Gleiches Prinzip wie bei der schnellen Exponentiation ➡ Für große Exponenten effizient berechenbar

• Zusätzlich nach jedem Multiplizieren Bildung des Rests ➡ Hält die Zahlen klein

Tobias Braun

2 von 3

28.10.2010

Beispiel 223

mod 15 = ? 2310 = 101112 → (QM ) Q QM QM QM 22 = 4 42 = 16 16 · 2 = 32

32 mod 15 = 2 22 = 4 4·2= 8 8 mod 15 = 8 82 = 64 64 · 2 = 128 128 mod 15 = 8

Umkehroperation: „diskreter Logarithmus“ x • Kleinste Lösung x der Gleichung a ≡ m mod p

• Diskrete Exponentialfunktion: effizienter Algorithmus verfügbar. • Diskreter Logarithmus: kein effizienter Algorithmus bekannt! • Beispiel: Größenordnung 10200 – Diskrete Exponentialfunktion: ca. 3000 Multiplikationen und Modulo-Operationen – Diskreter Logarithmus: ca.10200 Multiplikationen und Modulo-Operationen ➡ Einwegfunktion

Anwendungsbeispiele • Anwendung in der Kryptographie • Große Potenzen modulo p leicht ausrechnen. • Beweisen, dass eine Zahl keine Primzahl ist, ohne einen Teiler anzugeben. – Primzahlen als Schlüssel sind sicherer.

Tobias Braun

3 von 3

28.10.2010...