Modulare Potenzierung für hohe Zahlen in C++

Question

Ich habe kürzlich an einer Implementierung des Miller-Rabin-Primatitätstests gearbeitet. Ich beschränke mich dabei auf alle 32-Bit-Zahlen, da es sich um ein Projekt handelt, das ich nur zum Spaß mache, um mich mit C++ vertraut zu machen, und ich möchte eine Zeit lang nicht mit 64-Bit-Zahlen arbeiten müssen. Ein zusätzlicher Bonus ist, dass der Algorithmus für alle 32-Bit-Zahlen deterministisch ist, so dass ich die Effizienz erheblich steigern kann, weil ich genau weiß, auf welche Zeugen ich testen muss.

Bei niedrigen Zahlen funktioniert der Algorithmus also außergewöhnlich gut. Ein Teil des Prozesses beruht jedoch auf der modularen Potenzierung, d. h. (num ^ pow) % mod. so zum Beispiel,

3 ^ 2 % 5 = 
9 % 5 = 
4

Hier ist der Code, den ich für diese modulare Potenzierung verwendet habe:

unsigned mod_pow(unsigned num, unsigned pow, unsigned mod)
{
    unsigned test;
    for(test = 1; pow; pow >>= 1)
    {
        if (pow & 1)
            test = (test * num) % mod;
        num = (num * num) % mod;
    }

    return test;

}

Wie Sie vielleicht schon erraten haben, treten Probleme auf, wenn die Argumente alle außergewöhnlich große Zahlen sind. Wenn ich z. B. die Zahl 673109 auf ihre Primzahl prüfen will, muss ich an einer Stelle suchen:

(2 ^ 168277) % 673109

Nun ist 2 ^ 168277 eine außergewöhnlich große Zahl, und irgendwo in diesem Prozess läuft der Test über, was zu einer falschen Auswertung führt.

auf der Rückseite, Argumente wie

4000111222 ^ 3 % 1608

aus demselben Grund ebenfalls falsch bewerten.

Hat jemand Vorschläge für die modulare Potenzierung in einer Weise, die diesen Überlauf verhindern und/oder manipulieren kann, um das richtige Ergebnis zu erzeugen? (die Art, wie ich es sehe, ist Überlauf nur eine andere Form von Modulo, das heißt num % (UINT_MAX+1))

Answer 1

Sie können folgende Identität verwenden:

(a * b) (mod m) === (a (mod m)) * (b (mod m)) (mod m)

Versuchen Sie es auf einfache Art und Weise und verbessern Sie sich schrittweise.

    if (pow & 1)
        test = ((test % mod) * (num % mod)) % mod;
    num = ((num % mod) * (num % mod)) % mod;