Calcolo di potenze modulo n online

Come calcolare ab mod n

Ci sono diversi modi per calcolare \(a^b \, \text{mod} \, n\). Il metodo più efficiente consiste nel:

  1. Dividere l'esponente \(b\) in potenze di due (ossia scriverlo in binario), ottenendo \(b = (d_{k-1},d_{k-2},...,d_1,d_0\)).
  2. Costruire la seguente tabella \begin{array} {c|c} (b)_2 & c_0 = 1 \\ \hline d_{k-1} & c_1 \equiv c_0^2 \cdot a^{d_{k-1}} \, \text{mod} \, n \\ \hline d_{k-2} & c_2 \equiv c_1^2 \cdot a^{d_{k-2}} \, \text{mod} \, n \\ \hline \vdots & \vdots \\ \vdots & \vdots \\ \hline d_1 & c_{k-1} \equiv c_{k-2}^2 \cdot a^{d_1} \, \text{mod} \, n \\ \hline d_0 & c_k \equiv c_{k-1}^2 \cdot a^{d_0} \, \text{mod} \, n \\ \end{array}
Risultato: \(a^b \equiv c_k \, \text{mod} \, n \)

Tool online per calcolare potenze in modulo n

Questo tool ti permette di risolvere online le potenze modulo n passo dopo passo.
I numeri inseriti devono essere interi positivi eccetto per la base, che può essere anche negativa, e il modulo, che può essere solo maggiore di zero.



Esempio

Supponiamo di dover calcolare \(3^{17} \, \text{mod} \, 25\):

  1. Converti \(17\) in binario: \((17)_2=10001\)
  2. Costruisci la tabella: \begin{array} {c|l} (17)_2 & c_0=1 \\ \hline 1 & c_1 \equiv1^2 \cdot 3^1 = 1 \cdot 3 = 3\, \text{mod} \,25 \\ \hline 0 & c_2 \equiv3^2 \cdot 3^0 = 9 \cdot 1 = 9\, \text{mod} \,25 \\ \hline 0 & c_3 \equiv9^2 \cdot 3^0 = 81 \cdot 1 = 81 \equiv 6\, \text{mod} \,25 \\ \hline 0 & c_4 \equiv6^2 \cdot 3^0 = 36 \cdot 1 = 36 \equiv 11\, \text{mod} \,25 \\ \hline 1 & c_5 \equiv11^2 \cdot 3^1 = 121 \cdot 3 = 363 \equiv 13\, \text{mod} \,25 \\ \end{array}
Risultato: \(3^{17} \equiv 13\, \text{mod} \,25 \)