La teoria dei gruppi
Nell'algebra moderna hanno grande importanza i gruppi, strutture algebriche astratte, che trovano applicazioni
in molte applicazioni tra le quali non mancano quelle crittografiche.
Per definizione un gruppo è una struttura algebrica formata da un
insieme U e da un'operazione binaria o definita gli elementi dell'insieme che deve godere
delle seguenti proprietà:
- Chiusura: il risultato dell'operazione aob con a e b appartenenti a U deve a sua volta
appartenere a U.
- Associativa: dati tre qualsiasi elementi di U a, b, c deve essere:
(a o b) o c = a o (b o c);
in altre parole non ha importanza l'ordine delle operazioni e
quindi si possono tralasciare le parentesi e scrivere semplicemente a o b o c.
- Elemento neutro: esiste nell'insieme U un elemento i detto identico o neutro tale
che per ogni a appartenente a U: a o i = a
e i o a = a; in altre parole l'elemento neutro non ha alcun effetto rispetto
all'operazione o.
- Elemento inverso: per ogni elemento a appartenente a U, esiste un elemento
a-1 tale che a o a-1 = i.
Si noti che non è richiesta la proprietà commutativa; esisteranno dunque gruppi che godono anche
di questa proprietà e che si diranno gruppi commutativi (o abeliani) e gruppi non commutativi.
| Esempi di gruppi |
|---|
| Argomento | Gruppo | Ordine | Insieme | Operazione | Elem. Neutro | Elemento Inverso
|
|---|
Aritmetica
ordinaria
| Gruppo additivo | ∞ | Z = {0, ±1, ±2, ±3 ...}
Numeri relativi
| +
Addizione
| 0 (Zero)
a + 0 = a | -a (opposto)
a + (-a) = 0
|
|---|
| Gruppo additivo | ∞ | P = {0, ±2, ±4, ±6 ...}
Numeri pari
| +
Addizione
| 0 (Zero)
a + 0 = a | -a (opposto)
a + (-a) = 0
|
| Gruppo moltiplicativo | ∞ | Q - {0}
Numeri razionali | .
Moltiplicazione
| 1 (Uno)
a.1 = a | 1/a (reciproco)
a.(1/a) = 1
|
Aritmetica
finita (modulare)
| Gruppo additivo | N
| ZN = {0, 1, 2 ... N-1}
= {n | 0 <= n < N}
| aob = a + b (mod N)
Addizione modulare
| 0 (Zero)
ao0 = a | N - a
ao(N-a) = (a + N - a) (mod N) = 0
|
|---|
| Gruppo moltiplicativo | Φ(N) | Z*
{n |(0 < n < N) and (MCD(n, N) = 1)}
| aob = a.b (mod N)
Moltiplicazione modulare
| 1 (Uno)
ao1 = a | a-1
ao(a-1) = 1
|
Altri esempi di gruppi
L'insieme delle tre rotazioni di un triangolo equilatero su se stesso e l'operazione di composizione
delle rotazioni (una rotazione seguita da un'altra rotazione) costituisce un gruppo commutativo; le tre rotazioni
possibili sono I (0°), r (60°) e r2 (120°).
I è l'elemento neutro, r è l'inverso di r2
mentre I è l'inverso di se stesso.
L'insieme delle isometrie di un triangolo equilatero ABC su se stesso e l'operazione di composizione
delle isometrie (una seguita da un'altra) costituisce un gruppo non commutativo; alle tre rotazioni
del gruppo precedente si aggiungono i tre ribaltamenti del triangolo sulle sue tre altezze,
I è ancora l'elemento neutro, e i tre ribaltamenti sono gli inversi di se stessi
(ribaltando due volte di seguito un triangolo si ottiene la posizione di partenza).
L'insieme delle possibili permutazioni di 3 lettere dell'alfabeto p.es. A, B, C e l'operazione di combinazione tra permutazioni (una permutazione seguita da un'altra) costituiscono un gruppo del tutto equivalente al precedente, in termini matematici isomorfo al precedente. Infatti basta mettere in corrispondenza biunivoca
le lettere con i vertici del triangolo per convincersi dell'equivalenza.
L'insieme delle possibili permutazioni delle 26 lettere dell'alfabeto e l'operazione di combinazione tra permutazioni costituiscono un gruppo che ha particolare interesse in ambito crittografico; molti cifrari
si basano infatti su sostituzioni di una lettera con un'altra, e cioè appunto su permutazioni delle
lettere dell'alfabeto.
I gruppi di permutazioni rivestono un particolare interesse perchè è stato dimostrato che ogni
possibile gruppo finito è isomorfo a un gruppo di permutazioni.
Fonti bibliografiche e collegamenti
- Israel Grossman, Wilhelm Magnus - I Gruppi e i loro grafi - Zanichelli
- Wenbo Mao - Modern Cryptography: Theory and Practice - Prentice Hall