Implementieren Sie ein effizientes Verfahren zu Berechnung von a^b mod n (Mathematik für Informatiker)

Question

Seien a, b, n ∈ ℕ und b = b₀2⁰ + b₁2¹ + b₂2² + ...

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

Implementieren Sie ein effizientes Verfahren zur Berechnung von

a^b mod n

durch sukzessives Quadrieren.

Answer 1

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