Swappa : Uni / Crittografia: Gruppi, Anelli e Campi

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

• a³ = a + a + a
• a⁰ = e, dove e è l'elemento identità
• a^-n = (a')ⁿ, 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