0 Daumen
664 Aufrufe

Seien a, b, n ∈ und b = b020 + b121 + b222 + ...

mit b∈ {0,1} die Darstellung von b als Binährzahl.

Implementieren Sie ein effizientes Verfahren zur Berechnung von

ab mod n

durch sukzessives Quadrieren.

Avatar von

1 Antwort

0 Daumen

Hallo Hamburger,

ist eigentlich 'ne Informatikfrage. Zugegebenermaßen ein wenig tricky. Der mathematische Hintergrund besteht darin, ein Produkt \(a^b \cdot r\) so umzuformen, dass am Ende \(1 \cdot r_n\) dort steht. Man beginnt mit \(r_0=1\) und mit jedem Iterationsschritt wird das \(b\) halbiert und das \(a\) quadriert: $$a_i^{b_i} \cdot r_i = \left( a_i^2\right)^{\lfloor b_i/2\rfloor} \cdot r_i \cdot a_i^{(b_i \mod 2)}$$Jedesmal wenn bei der Division von \(b\) durch \(2\) ein Rest bleibt - d.h. \(b\) ungerade ist - wird das \(r_i\) mit dem \(a_i\) multipliziert. Im nächsten Schritt ist dann $$a_{i+1} = a_i^2 \\ b_{i+1} = \left\lfloor \frac {b_i}2 \right\rfloor \\ r_{i+1} = r_i \cdot a_i^{(b_i \mod 2)}$$(Bem.: das \(b_i\) ist nicht das \(b_0\), \(b_1\) bzw. \(b_2\) aus der Aufgabenstellung, sondern der Exponent \(b\) im \(i\)'ten Schritt des Algorithmus')

Man benötigt noch eine Funktion mod, die den Modulo berechnet. Dann könnte der Code z.B. in C so aussehen:

int pow_modulo( int a, int b, int n )
{
int result = 1;
for( ; b > 0; b = b / 2 )
{
if(b & 1)
result = mod(result * a, n);
a= mod(a* a, n);
}
return result;
}

Wichtig dabei ist, dass es sich bei \(b\,/\,2\) um eine Integerdivision handelt. D.h. ein Rest wird verworfen und das Ergebnis ist wieder ein ganze Zahl. Der Ausdruck \(\text{b \& 1}\) entspricht der Prüfung auf das niederwertigste Bit - also auf \(b_0\),

Wenn es sich bei den \(b_i\) codetechnisch um eine Liste handelt, könte man den Code etwa so schreiben

int pow_modulo( int a, list b, int n )
{
int result = 1;
for(; !b.empty(); b.pop_front())
{
if(b.front() > 0) // := b_0
result = mod(result * a, n);
a = mod(a * a, n);
}
return result;
}

das 'empty' prüft, ob die Liste leer ist. Das pop_front beseitigt das erste Element - also das \(b_0\) und das 'front' fragt das erste Element ab.

Gruß Werner

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community