Supponiamo di voler calcolare
cominciamo con
L'algoritmo presentato di seguito, si basa su questo approccio. Ovvero, utilizzare l'esponente in binario, per calcolare il resto modulo qualche numero di una cifra molto grande.
Di seguito le cifre in binario che corrispondono all'esponente decimale per cui si vuole calcolare il modulo.
Ricordiamo di avere qualcosa della forma:
Prima di vederlo in pseudocodice, vediamo più o meno qual è lo scopo dell'algoritmo.
L'algoritmo parte da
Poi considera una ad una le cifre binarie dell'esponente, partendo dalla cifra più significativa (più a sinistra).
L'algoritmo esegue
Poi controlla se la cifra attualmente considerata è
In breve, quando la cifra dell'esponente in binario è
d = 1;
for(i = k; i >= 0; i--){
d = (d * d) % q;
if(b_i == 1) { // b_i vuol dire il b dell'iterazione i (il bit in posizione i)
d = (d * a) % q;
}
}
return d;
CDimostrazione di correttezza
Passo base: se
Ipotesi induttiva: supponiamo vero l'algoritmo per una certa iterazione
Passo induttivo: dimostriamo la valenza dell'algoritmo per l'iterazione successiva (
int expmod(int a, int b, int q){
// restituisce un valore minore di q
if(b == 0) return 1;
if(b % 2 == 0) // se b pari
return sq(expmod(a, b/2, q)) % q;
else // b dispari
return (a * expmod(a, b - 1, q)) % q;
}
C