Il calcolo della potenza in un'aritmetica modulare di ordine n può essere naturalmente effettuato calcolando prima la potenza nell'aritmetica normale e quindi riducendola a modulo n, in formule ab MOD n.
In tal modo però si utilizzano numeri maggiori di n e quindi fuori dell'aritmetica in questione, numeri che se l'esponente b è grande possono divenire enormi, appesantendo il calcolo.
Conviene allora calcolare la potenza a piccoli passi, ogni volta riducendo il risultato a modulo n.
La scelta più semplice è quella di moltiplicare b volte per a e ogni volta ridurre il risultato in modulo n. Ma si può ottenere una velocità di calcolo maggiore elevando al quadrato ripetutamente senza superare l'esponente b, quindi proseguire come prima moltiplicando passo passo per a
| 32 MOD 12 | = | 9 MOD 12 = 9 |
| 92 MOD 12 | = | 81 MOD 12 = 9 |
| 92 MOD 12 | = | 81 MOD 12 = 9 |
| 9 * 3 MOD 12 | = | 27 MOD 12 = 3 |
| 3 * 3 MOD 12 | = | 9 MOD 12 = 9 |
Si voglia calcolare 310 in modulo 12; il calcolo si scompone in ((32)2)2 * 3 * 3 ovvero: si calcola 38 elevando tre volte il quadrato, quindi si moltiplica ancora due volte per 3, ad ogni passo riducendosi a modulo 12, secondo la traccia riportata a destra.
D'altra parte 310 = 59049 e 59049 = 4920 * 12 + 9, dunque 59049 MOD 12 = 9.
L'esistenza di un algoritmo efficiente per il calcolo della potenza è fondamentale per il cifrario RSA dove le operazioni di cifratura e decifratura consistono appunto in un elevamento a potenza nell'ambito di un'aritmetica modulare.
