Matematica e crittologia
La teoria dei gruppi
Aritmetiche finite - Teoria dei numeri

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à:

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.

Si dice poi ordine di un gruppo il numero di elementi dell'insieme base. Si definisce anche la nozione di ordine di un elemento di un gruppo.

È importante la nozione di sottogruppo e il relativo teorema di Lagrange.


Esempi di gruppi
ArgomentoGruppoOrdineInsiemeOperazioneElem. NeutroElemento Inverso
Aritmetica
ordinaria
Gruppo additivoZ = {0, ±1, ±2, ±3 ...}
Numeri relativi
+
Addizione
0 (Zero)
a + 0 = a
-a (opposto)
a + (-a) = 0
Gruppo additivoP = {0, ±2, ±4, ±6 ...}
Numeri pari
+
Addizione
0 (Zero)
a + 0 = a
-a (opposto)
a + (-a) = 0
Gruppo moltiplicativoQ - {0}
Numeri razionali
.
Moltiplicazione
1 (Uno)
a.1 = a
1/a (reciproco)
a.(1/a) = 1
Aritmetica
finita (modulare)
Gruppo additivoN 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 costituisce un gruppo commutativo; l'insieme delle sei possibili isometrie (rotazioni o simmetrie assiali) di un triangolo equilatero su se stesso costituisce un gruppo non commutativo.

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