Munterbunt

Schnelles Potenzieren

Übersicht > Verschiedenes > Schnelles Potenzieren

Aufgabe

In den Public Key Cryptosystem-Verfahren zur Verschlüsselung von Kreditkartennummern etc. müssen lange, beispielsweise 128-stellige Zahlen, auch effizient potenziert werden können. Wir gehen davon aus, dass das verwendete Chiffriergerät problemlos sehr lange Zahlen miteinander multiplizieren kann. Gesucht ist ein Verfahren, das mit möglichst wenigen Multiplikationen von einer Zahl $a$ die Potenz $a29$ berechnen kann!
Hinweis: Naiv kann $a.a .....a$ berechnet werden, indem man 28-mal mit $a$ multipliziert....

Lösung

Ein effizientes Verfahren lehnt sich an das Verfahren von Horner zur Auswertung von Polynomfunktionen an:

29 1.24+1.23+1.22+0.21+1.20 ((( 2 )2 )2)2 a = a = a .a .a .a

7 Multiplikationen