Erläuterung des rechten bis linken binären Methode der modularen Arithmetik?

Question

Ich habe diesen Link aus Wikipedia of Modulo einer großen Zahl untersucht, hier ist der Pseudocode.

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

Ich verstehe die in Wiki abgegebene Erklärung nicht. Warum muss ich prüfen, ob Exp%2 gerade oder ungerade ist. Auch warum mache ich die drei Operationen?

Answer 1

Dieser Algorithmus ist eine Kombination der Exponentiation durch Quadrat Algorithmus und Modulo -Arithmetik.

Um zu verstehen, was los ist, denken Sie zunächst eine Situation, wenn exponent ist eine Kraft von 2. Dann unter Annahme dessen exponent = 2 ^ k, Das Ergebnis könnte berechnet werden, indem das Ergebnis quadriert wird k Zeiten, dh

res = (...((base ^ 2) ^2 ) ... ) ^2))
              ---------------------
                     k times

Wann exponent ist keine Kraft von 2, Wir müssen zusätzliche Multiplikationen herstellen. Es stellt sich heraus, dass wenn wir teilen können exponent Mit 2 ohne Rest können wir die Basis quadrieren und den Exponenten teilen. Wenn es jedoch einen Rest gibt, müssen wir das Zwischenergebnis zusätzlich mit dem Wert des Stroms multiplizieren base.

Was Sie sehen, ist die gleiche Exponentiation durch Quadrat, die auf die Modulo -Multiplikation angewendet wird. Der Algorithmus bezeichnet die ganzzahlige Division um zwei mit der exponent >> 1 Operation, der identisch ist mit floor(exponent / 2).