Schnelles Exponentieren

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Schnelles Exponentieren

Beitrag von marlic »

Hier, falls es noch andere interessiert:

Gesucht ist \(s = a^b\ mod\ n\)

Sei:
\(b = \sum_{i=0}^k c_i 2^i\)
also c die Binäre Darstellung von b.

1. b in Binärer Form aufschreiben - und zwar in eine Tabelle, jeweils eine binäre Ziffer je Spalte.
\(| \quad c_k \quad | \quad c_{k-1} \quad |\ldots|\quad c_1 \quad |\quad c_0 \quad |\)

2. Unter \(c_0\), das heißt ganz rechts in der Tabelle, a eintragen, d.h. \(d_0 = a\)

3. Von rechts nach links unter jedes \(c_i\) jeweils das Quadrat (modulo n) der Zahl rechts daneben schreiben, d.h. \(d_{i+1} = d_i^2,\quad i=0..k-1\)

4. Das Produkt der Zahlen die unter einer 1 stehen bilden, d.h. \(s = \prod_{i=0}^k d_i^{c_i}\ mod\ n\)

Was dabei rauskommt ist das Ergebnis.
"Copy & Passed"

Wahlspruch der Plagiatoren

Zurück zu „Archiv“