Teoria dei numeri - Aritmetiche finite
Il calcolo dell'inverso nelle aritmetiche finite
Il teorema di Eulero-Fermat


Metodo

L'inverso di un numero x in un'aritmetica finita modulo N è quel numero y per il quale risulta xy = 1 mod N.
Un metodo di calcolo è fornito, quando x ed N sono primi tra di loro, dal teorema di Eulero-Fermat che asserisce:

xΦ(N) = 1 mod N

dove Φ(N) è la funzione di Eulero.

Allora l'inverso è semplicemente il numero

y = xΦ(N)-1 mod N

Infatti moltiplicando modulo N ambo i membri dell'uguaglianza per x si ha:

xy = x*xΦ(N)-1 = xΦ(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 finita.
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; è p.es. possibile estendere a questo problema l'algoritmo di Euclide per il calcolo del MCD.

Esempio

Si prenda il numero 5 in un aritmetica finita di ordine 18; si calcoli la funzione di Eulero Φ(18) = 6, e l'inverso di 5 viene ad essere 55 MOD 18 = 3125 MOD 18 = 11. E in effetti 5 * 11 = 55 = 1 mod 18.

Applicazioni

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

c = me mod N

e poi la potenza con l'altro numero:

m* = cd mod N = m ed mod N = m1 + k.Φ(N) mod N = m.mk.Φ(N) mod N

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

m* = m.1k 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.

Valido HTML 4.01!