Metodo

L'inverso di un numero $x$ in un'aritmetica modulare modulo $N$ è quel numero $y$ per il quale risulta $xy = 1 \mod N$.

Una formula per calcolarlo è fornita, quando $x$ ed $N$ sono primi tra di loro, dal teorema di Eulero-Fermat che asserisce:

$$x^{\Phi(N)} = 1 \mod N$$

dove $\Phi(N)$ è la funzione di Eulero.

Allora l'inverso è semplicemente il numero

$$y = x^{\Phi(N)-1} \mod N$$

Infatti moltiplicando modulo $N$ ambo i membri dell'uguaglianza $xy = 1$ per $x$ si ha:

$$ xy = x \times x^{\Phi(N)-1} = x^{\Phi(N)} = 1 \mod N$$

L'utilità di questo metodo di calcolo è ovviamente legata all'esistenza di un algoritmo efficiente per il calcolo della potenza in un'aritmetica modulare.

Va inoltre rilevato che il calcolo della funzione di Eulero per numeri elevati ha la stessa complessità della fattorizzazione. Se $N$ è molto grande conviene usare altri metodi; è per esempio possibile estendere a questo problema l'algoritmo di Euclide per il calcolo del MCD.

Viceversa per numeri piccoli, il calcolo dell'inverso si può semplicemente fare con metodo esaustivo, provando tutti i numeri minori di $N$.

Esempio

La tabella a destra mostra interattivamente i reciproci dei numeri di un dato modulo. Si noti che il numero di elementi che ammettono inverso è pari alla funzione di Eulero che è mostrata nelle prime righe, la cosa è conseguenza immediata della definizione di $\Phi(N)$.

Si prenda il numero $5$ in un aritmetica modulo $18$; si calcoli la funzione di Eulero $\Phi(18) = 6$, e l'inverso di $5$ viene ad essere $5^5 = 3125 = 11 \mod 18$. E in effetti $5 \times 11 = 55 = 1 \mod 18$.

Si prenda il numero $12$ in un aritmetica modulo $18$; si calcoli la funzione di Eulero $\Phi(18) = 6 $, e l'inverso di $12$ non esiste perché $ 12 $ non è primo con $ 18 $.

Applicazioni

Supponiamo di avere due numeri $d$ ed $e$ che siano uno l'inverso dell'altro in un'aritmetica modulare di ordine $\Phi(N)$, in altre parole sia $de = 1 \mod \Phi(N)$, o che è lo stesso $de = 1 + k \Phi(N)$ con $k$ intero positivo qualsiasi. Allora se calcoliamo una potenza con uno dei due numeri come esponente:

$c = m^e \mod N$

e poi la potenza con l'altro numero:

$m*$ = $c$^d mod N = $m$ ^ed mod N = $m$^{1 + k.Φ(N)} mod N = $m$.m^k.Φ(N) mod N

ma per il teorema di Fermat-Eulero è m^Φ(N) = 1 mod N, e dunque

$m*$ = $m$.1^k mod N = $m$

In altre parole con il secondo elevamento a potenza si ritrova il numero di partenza $m$. Se consideriamo $m$ come un messaggio da trasmettere e $c$ come lo stesso messaggio cifrato abbiamo in pratica un metodo di cifratura che usa il primo esponente ($e$) come chiave di cifratura e il secondo ($d$) come chiave di decifratura.

Ed è proprio questo il meccanismo alla base del cifrario RSA.

---

Riferimenti bibliografici

Siti e pagine web

X Funzione di Eulero calcolata usando la classica formula $\Phi(N) = N \times \left (1-\frac{1}{p_1} \right) \times \left (1-\frac{1}{p_2} \right) \dots $, dove $p_1, p_2 \dots $ sono i fattori primi di $N$ (anche se stesso se è primo).

X Funzione di Eulero calcolata contando i numeri minori di $N$ e primi con $N$.