Spiegazione del metodo binario da destra a sinistra di aritmetica modulare?

Question

Ho studiato questo collegamento da Wikipedia di modulo di un gran numero, ecco lo pseudocodice.

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

Non capisco la spiegazione fornita in wiki. Perché devo verificare se Exp%2 è uniforme o strano. Inoltre perché sto facendo le tre operazioni?

Answer 1

Questo algoritmo è una combinazione del Esponenziale da quadrati algoritmo e aritmetica del modulo.

Per capire cosa sta succedendo, prima considera una situazione quando exponent è un potere di 2. Quindi, assumendolo exponent = 2 ^ k, il risultato potrebbe essere calcolato quadrando il risultato k volte, cioè

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

quando exponent non è un potere di 2, dobbiamo fare ulteriori moltiplicazioni. Si scopre che se possiamo dividere exponent Entro 2 senza resto, possiamo quadrarsi della base e dividere l'esponente. Se, tuttavia, c'è un resto, dobbiamo inoltre moltiplicare il risultato intermedio per il valore della corrente base.

Quello che vedi è la stessa esponenziale quadrata applicata alla moltiplicazione del modulo. L'algoritmo indica la divisione interi di due usando il exponent >> 1 operazione, che è identica a floor(exponent / 2).