Wiederholtes Quadrieren

Potenzreste schnell berechnen · Abschnitt 17 von 64

Intuition

Exponenten verdoppeln, Reste klein halten

Große Exponenten wirken unheimlich – bis du sie in Zweierpotenzen zerlegst und wiederholt quadrierst. Dann wird aus $2^{100}$ ein kurzer Rechenweg modulo $m$ .

Gelöstes Beispiel

Dreizehnte Potenz modulo 7

$3^2\equiv2$ , $3^4\equiv4$ und $3^8\equiv2\pmod7$ . Wegen $13=8+4+1$ folgt $3^{13}\equiv2\cdot4\cdot3\equiv3$ .

Checkliste

Quadriertabelle

Basis reduzieren.
Exponenten 1, 2, 4, 8 und so weiter notieren.
Jeden Rest zum nächsten Tabellenwert quadrieren.
Nur benötigte Werte kombinieren.
Zwischenprodukte erneut reduzieren.

Typischer Fehler

Exponenten korrekt lesen

Beim Quadrieren wird aus $a^8$ die Potenz $a^{16}$ , nicht $a^9$ . Die Tabellenüberschrift ist genauso wichtig wie der berechnete Rest.