Come funziona questa funzione per il calcolo dell'esponenziazione modulare?

Question

Come funziona questa funzione per il calcolo dell'esponenziazione modulare?

#1 da (3 voti)

1

So che la regola in matematica per modulo è questa:

ab mod n =(a mod n ) (b mod n) mod n

Ho trovato il seguente codice per calcolare l'esponenziazione modulare:

pow(base,exponent,modulus){
 if (exponent==0) return 1;
 else {
  newexp=pow((base*base)%modulus,exponent/2,modulus)
  if (exponent%2 != 0){
    return (base*newexp)%modulus;
      }
  else return (newexp%modulus);
  }

Tuttavia, non capisco come questo codice si colleghi alla teoria e perché produca un risultato corretto. Qualcuno può spiegarmi come attua la teoria?

numbers theory algorithms

posta Maverick98 25.11.2017 - 18:28

fonte

1 risposta

Leggi altre domande sui tag numbers theory algorithms

Qual è un buon modo diagrammatico per rappresentare la comunicazione di eventi asincroni tra due sistemi? Come implementare la convalida prima di impostare un valore di proprietà in MVVM (WPF)

score 3 · Accepted Answer

Diamo un'occhiata a questa uguaglianza

ab mod n =(a mod n ) (b mod n) mod n.

spiega il tuo algoritmo.

L'intero trucco è pensare alle tre possibilità per exponent : può essere nullo, se può essere pari o può essere dispari.

Se exponent è 0 , è facile: qualsiasi numero elevato alla potenza dell'esponente 0 è 1. Questa è la prima dichiarazione di ritorno.

Se exponent è pari a , exponent%2 è 0. Ciò significa che puoi scrivere l'esponente come 2*k , dove k è exponent/2 :

pow(a,exponent,n) = a^exponent mod n 
                  = a^(2*k) mod n 
                  = (a^2)^k mod n 
                  = (a*a)^k mod n
                  = pow (a*a, k, n)
                  = pow (a*a, exponent/2, n)
                  = newexp

Poiché questa espressione è modulo n, l'applicazione di modulo n una volta di più non la cambierà, quindi è uguale a newexp % n . Ecco la spiegazione dell'ultima dichiarazione di reso.

Se exponent è dispari , exponent%2 è 1. Ciò significa che puoi scrivere l'esponente come 2*k+1 , dove k è exponent/2 (divisione intera):

pow(a,exponent,n) = a^exponent mod n 
                  = a^(2*k+1) mod n 
                  = (a^(2k)*a) mod n
                  = (a^(2k) mod n) * (a mod n) mod n
                  = ((a^2)^k mod n) * (a mod n) mod n
                  = ((a*a)^k mod n) * (a mod n) mod n
                  = pow (a*a, k, n) * (a mod n) mod n

Perché pow(a*a, k, n) è un numero modulo n, sappiamo che:

pow(a*a, k, n) mod n = pow(a*a, k, n)

Quindi possiamo continuare la nostra uguaglianza:

pow(a,exponent,n) = pow (a*a, k, n) * (a mod n) mod n    
                  = (pow (a*a, k, n) mod n) * (a mod n) mod n
                  = (a*pow (a*a, k, n)) mod n
                  = (a*pow (a*a, exponent/2, n)) mod n
                  = (a*newexp) mod n

E qui hai la spiegazione per la seconda dichiarazione di ritorno.