|
 I vari sistemi crittografici, gli algoritmi per cifrare e
decifrare messaggi si basano sulle proprietà dell'aritmetica modulare: l'implementazione dell'algoritmo
RSA si basa su tale
aritmetica. La prima intuizione su questo argomento è dovuta a
Gauss,
con l'invenzione del suo calcolatore a orologio.
L'aritmetica modulare consiste nella riduzione
dell'insieme dei numeri interi positivi e negativi, ossia Z, ad un
numero finito di classi di equivalenza, cioè di sottoinsiemi
i cui elementi hanno come caratteristica comune: il resto della
divisione per un certo numero n.
Sia n un intero e sia
 la
relazione di equivalenza in Z detta congruenza modulo n e si denota
anche con Zn
La notazione a
 b(mod
n)
e vengono chiamati rappresentanti della classe
Lo operazioni di addizione e moltiplicazione in Zn
verificano
le seguenti proprietà fondamentali:
- ([a]+[b])+[c]=[a]+([b]+[c]),
- [a]+[0]=[0]+[a]=[a]
- [a]+[-a]=[0]
- [a]+[b]=[b]+[a]
- ([a][b])[c]=[a]([b][c])
- [a][1]=[1][a]=[a]
- [a][b]=[b][a]
- ([a]+[b])[c]=[a][c]+[b][c]
Applicazioni con Excel: tabelle di Cayley delle operazioni di
somma e di
Prodotto in Zn ,
dove sono evidenziate le celle che contengono i rispettivi elementi neutri 0 e
1.
Osservazioni
-
nella tabella della
somma la distribuzione degli
opposti è estremamente regolare ed è facile formulare una legge
generale: l'opposto di a in Zn è  .
-
nella tabella del
prodotto non tutti
gli elementi hanno inverso (solo 2,4,5,7 e 8 sono invertibili);
come è noto, in Zn ammettono
inverso solo i numeri a primi
con n,
cioè tali che MCD (a, n) = 1
-
se (e solo se) n
è
primo allora tutti gli elementi (non nulli) di Zn
ammettono
inverso. in altri termini Zn
è
un anello per ogni n,
ed è un campo se e solo se n è
primo.
Nella crittografia
un'operazione ricorrente è la potenza all'interno delle congruenze.
Applicazioni con Excel :
potenza
in Zn
Osservazioni
- l'ultima colonna della potenza in Zn è
composta di soli 1, cioè per ogni
risulta
 .
Se così fosse, l'inverso di
a in Zn sarebbe
essendo
- la congettura è corretta se e solo se n è primo, come
afferma il piccolo teorema di
Fermat.
- Se il teorema di Fermat risolve il problema del calcolo
dell'inverso di a in Zn quando n è
primo, rimane aperto il problema nel caso n non
sia primo. Occorrerà aspettare più di un secolo perché questo
problema venga risolto da
Eulero.
- La generazione di numeri
casuali (random) è ottenuta
grazie all'aritmetica modulare.
Applicazioni dell'aritmetica modulare con
Excel
 |
