¿Explicación del método binario de derecha a izquierda de aritmética modular?

Question

He estado estudiando este enlace desde Wikipedia de Modulo de un gran número, aquí está el pseudocódigo.

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

No entiendo la explicación dada en Wiki. Por qué tengo que verificar si Exp%2 es uniforme o impar. Además, ¿por qué estoy haciendo las tres operaciones?

Answer 1

Este algoritmo es una combinación del Exponencia por cuadros algoritmo y aritmética de módulo.

Para entender lo que está pasando, primero considere una situación en la que exponent es un poder de 2. Entonces, suponiendo que exponent = 2 ^ k, el resultado podría calcularse cuadrando el resultado k veces, es decir

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

Cuando exponent no es un poder de 2, necesitamos hacer multiplicaciones adicionales. Resulta que si podemos dividir exponent A los 2 sin resto, podemos cuadrar la base y dividir el exponente. Sin embargo, si hay un resto, también debemos multiplicar el resultado intermedio por el valor de la corriente base.

Lo que ve es la misma exponencia al cuadrar la aplicada a la multiplicación de módulos. El algoritmo denota división entera por dos utilizando el exponent >> 1 operación, que es idéntica a floor(exponent / 2).