Le potenze modulo n

Per calcolare la potenza modulo con le congruenze $$ a^m \mod n $$ posso usare questo algoritmo

1. Calcolo tutte le potenze a^x con x=2^k < m
2. Scrivo l'esponente m in base 2 (binario)
3. Scrivo il prodotto delle potenze a^x corrispondenti ai valori 1 del numero m in binario
4. Calcolo le potenze e i prodotti riducendo man mano il risultato in modulo m

Il risultato finale è la potenza a^m in modulo n.

Un esempio pratico

Devo calcolare la seguente potenza a^m con a=3 e m=29 in modulo 7

$$ 3^{29} \mod 7 $$

Calcolo tutte le potenze con esponente 2^k minore di m=29

$$ 3^{2^0} \mod 7 \text{ perché } 2^0=1 < 29$$

$$ 3^{2^1} \mod 7 \text{ perché } 2^1=2 < 29 $$

$$ 3^{2^2} \mod 7 \text{ perché } 2^2=4 < 29 $$

$$ 3^{2^3} \mod 7 \text{ perché } 2^3=8 < 29 $$

$$ 3^{2^4} \mod 7 \text{ perché } 2^4=16 < 29 $$

Mi fermo qui perché 2⁵=32 > 29

Pertanto ho le seguenti congruenze

$$ 3^{2^0} \mod 7 $$

$$ 3^{2^1} \mod 7 $$

$$ 3^{2^2} \mod 7 $$

$$ 3^{2^3} \mod 7 $$

$$ 3^{2^4} \mod 7 $$

Ora scrivo l'esponente m=29 in base 2 (binario).

$$ (11101)_{29} $$

Associo il primo valore (1) all'ultima potenza, il secondo valore (1) alla penultima potenza e così via.

Scrivo un prodotto con tutte le potenze corrispondenti ai valori 1.

$$ 3^{2^4} \cdot 3^{2^3} \cdot 3^{2^2} \cdot 3^{2^0} \mod 7 $$

Calcolo le potenze

$$ 3^{16} \cdot 3^8 \cdot 3^4 \cdot 3^1 \mod 7 $$

$$ 43046721 \cdot 6561 \cdot 81 \cdot 3 \mod 7 $$

Nota. Se qualche potenza è ancora molto grande posso semplificarla o usare lo stesso algoritmo in forma ricorsiva. Ad esempio la potenza 3¹⁶ è molto complessa da calcolare a mente ma posso semplificarla in un prodotto di potenze $$ 3^{16}=3^4 \cdot 3^4 \cdot 3^4 \cdot 3^4 \mod 7 $$ $$ 3^{16}=81 \cdot 81 \cdot 81 \cdot 81 \mod 7$$ Nel modulo 7 il numero 81 diviso 7 ha resto 4. Quindi riscrivo l'equazione direttamente in modulo 7. $$ 3^{16}= 4 \cdot 4 \cdot 4 \cdot 4 \mod 7$$ $$ 3^{16}= 16 \cdot 16 \mod 7$$ Poiché 16 diviso 7 ha resto 2 posso riscriverla in questo modo $$ 3^{16}= 2 \cdot 2 \mod 7$$ $$ 3^{16}= 4 \mod 7$$ In questo modo posso scrivere la potenza 3¹⁶ direttamente in modulo 7, senza doverla calcolare in decimale.

Ora trasformo tutti i valori in modulo 7

$$ 4 \cdot 2 \cdot 4 \cdot 3 \mod 7 $$

Svolgo le moltiplicazioni trasformando man mano il risultato parziale in modulo 7 quando è superiore a 7 per semplificare i calcoli.

$$ 4 \cdot 2 \cdot 4 \cdot 3 \mod 7 $$

$$ 1 \cdot 4 \cdot 3 \mod 7 $$

$$ 4 \cdot 3 \mod 7 $$

$$ 5 \mod 7 $$

Ho trovato il risultato finale

$$ 3^{29} \mod 7 $$

$$ 5 \mod 7 $$

La potenza di 3²⁹ modulo 7 è equivalente a 5 modulo 7.

$$ 3^{29} \equiv 5 \mod 7 $$

E così via.