Binäre Exponenten als Bauplan

Potenzreste schnell berechnen · Abschnitt 18 von 64

Definition

Binärzerlegung

Jede positive ganze Zahl ist eindeutig eine Summe verschiedener Zweierpotenzen. Beispielsweise ist $73=64+8+1$ .

Gelöstes Beispiel

Nur drei Tabellenwerte

Für $a^{73}$ werden aus der Quadriertabelle nur die Werte zu $a^{64}$ , $a^8$ und $a$ multipliziert.

Beweis

Warum multipliziert wird

Aus $n=2^{e_1}+\cdots+2^{e_r}$ folgt mit $a^{u+v}=a^ua^v$ die Identität $a^n=a^{2^{e_1}}\cdots a^{2^{e_r}}$ .

Satz

Wenige Rechenschritte

Bis zum Exponenten $n$ sind nur $\lfloor\log_2 n\rfloor$ Quadrierungen nötig. Das Verfahren funktioniert unabhängig davon, ob Basis und Modul teilerfremd sind.