Matematica e Crittologia
Aritmetiche finite (o modulari)
Teoria dei numeri - La funzione di Eulero - Il teorema di Eulero-Fermat

L'aritmetica ordinaria opera su insiemi infiniti di numeri: l'insieme $\mathbb{N}$ dei numeri naturali: $\mathbb{N} = \{ 0, 1, 2, 3, 4 ...\}$ quello dei relativi $\mathbb{Z} = \{0, \pm 1, \pm 2, \pm 3, \pm 4 ...\}$.

Nella realtà però si ha spesso a che fare con situazioni nelle quali i numeri possibili sono finiti; l'orologio ha solo 12 o 24 ore; e anche i numeri gestiti da un computer sono sempre limitati.

Si definisce allora aritmetica finita un'aritmetica che opera su un insieme limitato di numeri, di solito un sottoinsieme di $\mathbb{N}$ escludendo i negativi. Si dice anche aritmetica modulare o circolare, in quanto una volta raggiunto l'ultimo numero si ricomincia dal primo.

Esempio classico quello dell'orologio; le ore si susseguono da 0 a 23, il 24 coincide con il punto di partenza, quindi con lo 0; e con la mezzanotte si ricomincia da 0. L'insieme è $\{0, 1, 2, 3, ... 22, 23\}$.

L'aritmetica dell'orologio è quindi un'aritmetica modulo 24.

In generale un'aritmetica finita modulo n si basa sull'insieme $\{0, 1 , 2 ... n-1\}$; questi numeri possono vedersi come i possibili resti di una divisione per n.

Molti ambienti e linguaggi informatici prevedono un operatore per il calcolo del resto; il simbolo è mod (linguaggio Pascal) o % (linguaggio C e simili). P.es. $19 \mod 7 = 5 \quad;\quad 19\% 7 = 5$.

Le regole di calcolo si basano sul calcolo del resto: la somma algebrica e il prodotto vengono prima eseguite nell'aritmetica ordinaria, e qui si calcola il resto della divisione tra il risultato e il modulo dell'aritmetica. Sono possibili anche algoritmi di calcolo più veloce e che eviti il calcolo di numeri troppo grandi.

Esempi in modulo 24:

Operazione mod 24Operazione
ordinaria
Calcolo del resto
$15 + 13 = 4 \mod24$$ 15 + 13 = 28$$28 \% 24 = 4$
$15 \times 13 = 3 \mod24$$ 15 \times 13 = 195$$195 \% 24 = 3$
$16 \times 12 = 0 \mod24$$ 16 \times 12 = 192$$192 \% 24 = 0$
$7 ^ 3 = 7 \mod24$$ 7^3 = 343$$343 \% 24 = 7$
$7 ^ 4 = 1 \mod24$$ 7^4 = (7^3) \times 7 = 1$$49 \% 24 = 1$

Le aritmetiche finite ereditano di norma le proprietà dell'algebra ordinaria della somma ordinaria fra numeri interi; si tratta quindi di un gruppo finito commutativo.

Lo stesso vale per il prodotto, ma il terzo esempio qui sopra mostra che la regola di annullamento del prodotto (un prodotto è nullo se e solo se lo è almeno uno dei due fattori) non è più valida.

Questo inconveniente può evitarsi solo se $n$ è primo; in questo caso si ha un campo finito o di Galois (vedi anche gruppo moltiplicativo).

Un caso di particolare interesse è quello della potenza di un numero.

Naturalmente è possibile definire e calcolare le operazioni inverse, per esempio il reciproco ; di norma il calcolo delle operazioni inverse è molto più oneroso di quello della corrispondente operazione diretta; per numeri grandi la complessità può diventare proibitiva, cosa che è stata sfruttata per progettare cifrari robusti. Esempio classico il calcolo del logaritmo finito, che è alla base del sistema Diffie-Hellman per la trasmissione sicura delle chiavi.

L'aritmetica finita più semplice è quella modulo 2, definita quindi nell'insieme {0, 1}. La tabellina dell'addizione è ovviamente molto breve e sorprendentemente equivale alla tabella della sottrazione:

01
001
110
+01
001
110
     0 + 0 = 0    0 + 1 = 1                  0 - 0 = 0    0 - 1 = 1
     1 + 0 = 1    1 + 1 = 0                  1 - 0 = 1    1 - 1 = 0

che equivale poi all'operazione logica di disgiunzione esclusiva (XOR).

Le aritmetiche finite trovano applicazione in molti metodi della crittografia, dal cifrario di Vernam ad RSA.


Valido HTML 4.01!