:: Crittografia: Gruppi, Anelli e Campi ::
Torna alla pagina di Crittografia
I gruppi {G, +}
Il gruppo è un insieme di elementi, in cui è definita l'operazione binaria +. NON È necessariamente la somma come la intendiamo noi, potrebbe essere una qualsiasi operazione che agisce su due operandi (binaria), e che ha le seguenti proprietà
- chiusura: per ogni a e b appartenenti a G, a + b appartiene a G
- associatività: (a + b) + c = a + (b + c)
- esistenza dell'elemento identità: in altre parole il neutro, che per intenderci è quello che mi rende possibile l'operazione a + e = e + a = a, con e che è l'elemento identità
- esistenza dell'inverso: per ogni a appartenente a G, esiste un a' tale che a + a' = 0 (0 è il neutro)
Per esempio, prendiamo un insieme, Nn, composto da n simboli distinti. E poi, di questo insieme facciamo tutte le n! possibili permutazioni, e le raggruppiamo in un insieme, Sn. Sn è quindi l'insieme di tutte le permutazioni di n simboli distinti.
Bene, è possibile dimostrare che Sn è un gruppo, ovvero valgono le proprietà di cui sopra.
Un elemento di Sn può essere ad esempio: {3, 1, 2} supponendo che Nn abbia tre elementi. La scrittura {3, 1, 2} significa che prendo il primo elemento di Nn, e lo metto nel 3° posto, poi il 2° e lo metto nel 1° ed infine il 3° lo metto nel 2°. Indica praticamente le destinazioni degli elementi.
L'operazione + la definiamo così: {3, 1, 2} + {α, β, γ} = {γ, β, α}, per la regola qui sopra. Prendo il secondo elemento e lo spaciugo secondo quanto mi dice il primo elemento.
Quest'operazione in Sn gode delle proprietà di:
- chiusura: sì
- associatività: sì
- elemento identità: sì, ed è {1, 2, 3} che trasforma sempre una permutazione in se stessa
- esiste l'inverso: sì, e l'inverso di una permutazione è quella permutazione che sommata alla prima mi dà il neutro. Ad esempio, {1, 3, 2} + {1, 3, 2} = {1, 2, 3}
Se n è un numero finito, allora il gruppo è detto finito e l'ordine del gruppo è n. Altrimenti è un gruppo infinito.
Gruppo Abeliano
È un gruppo, in cui per l'operazione + vale anche la proprietà aggiuntiva:
- commutatività = a+ b = b + a, per ogni a, b appartenenti a G
Gruppo ciclico
Definiamo l'elemento a potenza come la ripetizione dell'operazione (qualsiasi cosa il voglia dire, ovviamente).
Vigono codeste proprietà:
- a3 = a + a + a
- a0 = e, dove e è l'elemento identità
- a-n = (a')n, dove a' è l'inverso di a
Orbene, un gruppo si dice ciclico se esiste un a tale che, elevato a potenza, genera tutti gli elementi del gruppo {G, +}. Tale elemento a è detto generatore del gruppo.
Per intenderci, prendiamo il gruppo degli interi >= 0, con l'operazione +: {N+, +}. L'elemento 1 è un generatore. Infatti, le potenze saranno 1+1, 1+1+1, 1+1+1+1, 1+1+1...+1 e generano tutti gli elementi del gruppo (gli interi maggiori di 0).
Anello
Un anello si segna così: {R, +, *}, cioè è un insieme di elementi in cui sono definite 2 operazioni binarie, + e * (in seguito spesso ometteremo il segno * per indicare la seconda operazione, proprio come si fa con le moltiplicazioni).
Le proprietà che deve avere sono:
- rispetto al +, deve essere un gruppo abeliano
- chiusura rispetto a *
- associatività rispetto a *
- distributività: a(b+c) = ab + ac; (a+b)c = ac + cb
L'anello insomma è un insieme di elementi in cui valgono somma, sottrazione e moltiplicazione.
Anello commutativo
Se vale anche la proprietà commutativa per l'operazione *, allora l'anello è un anello commutativo.
Dominio integrale
Un dominio integrale è un anello commutativo in cui vigono anche queste proprietà:
- esiste l'elemento identità per *
- annullamento del prodotto: se ab = 0, allora ho o che a=0, o che b=0
Per esempio, l'insieme di tutti gli interi, positivi, negativi, e con lo 0, e con le normali operazioni + e *, è un dominio integrale.
Campo
Il campo è un dominio integrale {F, +, *} in cui esiste anche l'inverso moltiplicativo:
- per ogni a appartenente ad F, esiste un a-1 tale che aa-1 = a-1a = 1, dove 1 è l'elemento identità
Insomma, ogni numero ha il suo inverso, e vuol dire che un campo è un insieme di elementi in cui sono definite somme, sottrazioni, moltiplicazioni e divisioni.
Riassuntino
|
{G, +}
|
{R, +, *}
|
{F, +, *}
|
|
Gruppo
|
Anello
|
Campo
|
|
Gruppo abeliano
|
Anello commutativo
|
|
|
Gruppo ciclico
|
Dominio integrale
|
|
Torna alla pagina di Crittografia
