Matematica Discreta
Lezione del giorno 3 maggio 2010
Teoria dei gruppi e quadrati latini ortogonali.
Applicheremo alcuni risultati della teoria dei gruppi alla teoria dei quadrati latini ortogonali.
Ricordiamo che un quadrato latino di ordine n è una matrice nxn i cui elementi sono scelti in un insieme A di cardinalità n, e tale che in nessuna riga e nessuna colonna vi siano due elementi uguali.
Dati 2 quadrati latini di ordine n:
X=(aij), Y=(bij) (con i=1,2,….,n; j=1,2,….,n)
(in cui gli elementi aij appartengono ad un insieme A, gli elementi bij appartengono ad un insieme B, entrambi da cardinalità n) si dice che essi sono ortogonali se la matrice nxn che ha nella casella della riga i e colonna j la coppia (aij,bij) contiene n2 coppie tutte diverse, e quindi contiene tutte le possibili coppie del prodotto cartesiano AxB.
Dimostreremo, con la teoria dei gruppi finiti, che è possibile costruire per ogni naturale n>1 dispari una coppia di quadrati latini ortogonali di ordine n.
Premettiamo un risultato:
Teorema. Se A è un gruppo commutativo finito di cardinalità dispari n, e se x,y sono elementi di A tali che x2=y2 si ha necessariamente x=y.
Dimostrazione:
Essendo n dispari, n-1 è pari, dunque n-1=2k con k numero naturale, cioè n=2k+1.
Calcolando le potenze xn, yn con le regole sulle potenze, e tenendo conto che, per un Teorema precedente, elevando ogni elemento di A alla cardinalità n si ottiene l’elemento neutro eA, si ha:
e=xn = x2k+1 = (x2)k*x e=yn = y2k+1 = (y2)k*x
Si deduce che (x2)k = x’ (simmetrico di x), (y2)k = y’ (simmetrico di y).
Da ciò e dall’ipotesi x2=y2 si ha allora x’=y’ e calcolando il simmetrico di ambo i membri si ha la tesi x=y (ricordando che il simmetrico del simmetrico di un elemento è l’elemento stesso).
Osservazione: poiché il Teorema usato nella dimostrazione (quello che afferma che elevando ogni elemento di un gruppo finito alla cardinalità del gruppo si ottiene l’elemento neutro) vale anche nel caso di un gruppo non commutativo, anche il Teorema precedente vale nel caso di un gruppo non commutativo.
Sia A un gruppo commutativo finito di cardinalità n dispari. Costruiremo due quadrati latini ortogonali di ordine n che hanno entrambi elementi in A.
Siano a1, a2,….., an gli n elementi distinti di A.
Il primo quadrato è la tavola dell’operazione * di A: è la matrice nxn in cui nella casella in riga i e colonna j vi è l’elemento ai*aj. Sappiamo già che tale matrice è un quadrato latino, come dimostrato in una delle lezioni precedenti (sfruttando le leggi di cancellazione valide nel gruppo A).
Il secondo quadrato è costruito in modo simile: è la matrice nxn in cui nella casella in riga i e colonna j vi è però l’elemento ai*aj’ (dove aj’ indica il simmetrico di aj) . Dimostriamo che anche tale matrice è un quadrato latino: se per assurdo nella riga i vi fossero 2 elementi uguali in colonne diverse j,k si avrebbe:
ai*aj’ = ai*ak’
dalla legge di cancellazione a sinistra seguirebbe aj’ = ak’, e calcolando il simmetrico di ambo i membri (ricordando che il simmetrico del simmetrico di un elemento è l’elemento stesso) si avrebbe aj = ak, contraddizione perché a1, a2,….., an sono n elementi distinti.
Analogamente se per assurdo nella colonna j vi fossero 2 elementi uguali in righe diverse i,k si avrebbe:
ai*aj’ = ak*aj’
dalla legge di cancellazione a destra seguirebbe aj = ak, contraddizione perché a1, a2,….., an sono n elementi distinti.
Dimostriamo ora che i 2 quadrati latini costruiti sono ortogonali.
Se per assurdo così non fosse, nella matrice contenente coppie di elementi dei 2 quadrati vi sarebbero 2 coppie uguali in caselle diverse: dunque la coppia (ai*aj , ai*aj’) nella casella in riga i, colonna j, coinciderebbe con la coppia (ar*as , ar*as’) nella casella in riga r, colonna s, da cui le due eguaglianze
ai*aj = ar*as ; ai*aj’ = ar*as’
Essendo le caselle diverse, dovrebbero essere diversi gli indici di riga i,r oppure gli indici di colonna j,s: supponiamo per esempio js (se è ir si ragiona in modo analogo).
Dalla seconda delle 2 eguaglianze precedenti, componendo a destra ambo i membri con aj mediante l’operazione * si ha:
ai = ar*as’*aj
e sostituendo nella prima eguaglianza si ha:
ar*as’*aj*aj = ar*as
Dalla legge di cancellazione a sinistra segue:
as’*aj*aj = as
e componendo a sinistra ambo i membri con as mediante l’operazione *:
aj*aj = as*as
dunque aj2 = as2 e per il Teorema precedente aj = as, contraddizione perché a1, a2,….., an sono n elementi distinti.
Esempio. Costruiamo 2 quadrati latini ortogonali di ordine n=7. Fissiamo un gruppo commutativo finito di cardinalità 7, per esempio Z7 = {0,1,2,3,4,5,6} rispetto all’operazione di somma fra classi (per semplicità di scrittura omettiamo le parentesi quadre nell’indicare ogni classe [a]).
Il primo quadrato è la matrice nxn che rappresenta la tavola operazionale della somma fra classi (dove si fanno corrispondere ordinatamente alle righe e colonne gli elementi 0,1,2,3,4,5,6 del gruppo Z7):
0 1 2 3 4 5 6 1 2 3 4 5 6 0 2 3 4 5 6 0 1 3 4 5 6 0 1 2 4 5 6 0 1 2 3 5 6 0 1 2 3 4 6 0 1 2 3 4 5
Il secondo quadrato è costruito in modo analogo, ma in ogni casella vi è la somma di un elemento e del simmetrico di un altro elemento (si deve ricordare la regola pratica: il simmetrico di [0] è [0], mentre il simmetrico di una classe [a][0] è la classe [7-a]).
Facendo i calcoli si ottiene:
0 6 5 4 3 2 1 1 0 6 5 4 3 2 2 1 0 6 5 4 3 3 2 1 0 6 5 4 4 3 2 1 0 6 5 5 4 3 2 1 0 6 6 5 4 3 2 1 0
(per esempio per calcolare l’elemento nella riga 6, corrispondente a [5], e colonna 4, corrispondente a [3], si deve calcolare [5]+[7-3] = [5]+[4] = [9] = [2] etc….).
Il quadrato ottenuto dalle coppie di elementi dei 2 quadrati è:
00 16 25 34 43 52 61 11 20 36 45 54 63 02 22 31 40 56 65 04 13 33 42 51 60 06 15 24 44 53 62 01 10 26 35 55 64 03 12 21 30 46 66 05 14 23 32 41 50
e come previsto tale quadrato contiene 49=72 coppie tutte diverse, ossia tutte le possibili coppie di numeri 0,1,2,3,4,5,6.
Questa è una possibile soluzione del problema degli ufficiali di Eulero nel caso di 72=49 ufficiali di 7 reggimenti e 7 gradi diversi (dove i reggimenti e i gradi sono indicati appunto dai numeri 0,1,2,3,4,5,6).
In generale tale algoritmo fornisce una soluzione per un qualunque numero n2 di ufficiali di n reggimenti ed n gradi diversi, quando n è dispari.
Algoritmi diversi (e più complessi) si utilizzano per fornire soluzione anche nel caso n pari (ma con n2 ed n6 perché sappiamo che per tali valori la soluzione non esiste).
Crittografia.
E’ la scienza che studia la possibilità che un soggetto A (mittente) spedisca un messaggio ad un utente B (destinatario) attraverso un canale di comunicazione non sicuro, in modo che per un soggetto C (intruso), che sia in grado di intercettare il messaggio, sia “difficile” conoscere le informazioni in esso contenuto.
In un sistema crittografico il messaggio originale (detto messaggio in chiaro) prima di essere trasmesso dal mittente A viene opportunamente modificato (la cosiddetta cifratura che trasforma il messaggio in chiaro in un messaggio cifrato); è il messaggio cifrato che viene trasmesso lungo il canale di comunicazione: quando il destinatario B lo riceve, ne effettua una opportuna modifica (la cosiddetta decifratura) che fornisce come risultato il messaggio in chiaro originale.
Anticamente il concetto di ”messaggio” era ristretto ad un messaggio di tipo “testuale”, cioè costituito da caratteri alfabetici.
Poiché il messaggio può sempre essere suddiviso in “blocchi” (che poi il destinatario dovrà
“incollare” per riottenere l’intera informazione originale) potremo anche in certi casi identificare il concetto di messaggio con il singolo carattere alfabetico: la cifratura e la decifratura opereranno in questo caso sulle singole lettere del testo.
Se vogliamo formalizzare la struttura di un sistema crittografico, servendoci della teoria degli insiemi, possiamo dire che si possono individuare un insieme finito X dei messaggi in chiaro, un insieme finito Y dei messaggi cifrati (in molti casi concreti gli insiemi X,Y saranno uguali), una funzione di cifratura f : X Y (che trasforma ogni messaggio in chiaro xX in un messaggio cifrato y=f(x)X) e in una funzione di decifratura g : Y X (che ritrasforma il messaggio cifrato y=f(x)Y nel messaggio in chiaro x=g(y)X).
Dal punto di vista insiemistico, la proprietà della funzione di decifratura g si traduce nel fatto che per ogni messaggio in chiaro xX si deve avere g(f(x))=x, dunque la composizione gf deve coincidere con la funzione identica iX dell’insieme X.
Vedremo dagli esempi che la funzione di cifratura e la funzione di decifratura si servono di elementi ausiliari (detti rispettivamente chiavi di cifratura e chiavi di decifratura) che sono utilizzati nella trasformazione di un messaggio in chiaro in messaggio cifrato e nella ritrasformazione di un messaggio cifrato nel messaggio in chiaro da cui esso proveniva.
Il sistema crittografico di Cesare.
E’ un sistema crittografico molto semplice (ma poco sicuro) che pare fosse utilizzato dagli antichi Romani.
Supponiamo che l’insieme dei messaggi in chiaro X e quello dei messaggi cifrati Y coincidano entrambi con l’insieme delle 21 lettere dell’alfabeto italiano:
X = Y = {A,B,C,D,E,F,G,H,I,L,M,N,O,P,Q,R,S,T,U,V,Z}
Diamo un valore numerico intero compreso fra 0 e 20 alle lettere: A=0, B=1, C=2,…., Z=20.
Fissiamo una lettera dell’alfabeto (sarà la chiave di cifratura del nostro sistema crittografico) e calcoliamo il suo valore numerico a con 0a20 (tale valore numerico è detto offset); definiamo poi la funzione di cifratura f : X Y nel modo seguente: disponiamo in modo “circolare” gli elementi di X (in modo che la lettera successiva alla Z sia la A), e per ogni messaggio in chiaro xX (dunque x è una delle 21 lettere dell’alfabeto) definiamo il messaggio cifrato y=f(x) uguale a quella lettera che si trova (a partire dalla lettera x) spostandosi di a posizioni lungo l’alfabeto in verso orario.
Per esempio se la chiave di cifratura è la lettera D con valore numerico a=3, e se x=E allora f(E)=H (la lettera H si trova 3 posizioni più avanti rispetto alla lettera E). Ovviamente non ha molto senso scegliere come chiave di cifratura la lettera A con offset a=0, in quanto la cifratura di ogni lettera la lascerebbe invariata.
La funzione di decifratura g : Y X utilizza una chiave di decifratura uguale a quella di cifratura, ed è definita nel modo seguente: dato yY (quindi y è una delle 21 lettere dell’alfabeto) si definisce g(y) uguale a quella lettera che si trova (a partire dalla lettera y) spostandosi di a posizioni lungo l’alfabeto in verso antiorario.
E’ ovvio che, se y=g(x) è la cifratura del messaggio in chiaro x, g(y) coincide con il messaggio in chiaro originale x.
Per rendere operativamente più semplice la cifratura, il mittente scrive, sotto la successione delle lettere dell’alfabeto, la stessa successione “shiftata” verso destra di a posizioni (se a è l’offset cioè il valore numerico della chiave di cifratura) sempre pensando ad una struttura “circolare”: sotto ogni lettera x si trova la sua cifratura f(x).
Per esempio nel caso a=3 (chiave di cifratura è la lettera D):
A B C D E F G H I L M N O P Q R S T U V Z
D E F G H I L M N O P Q R S T U V Z A B C
In questo caso, per cifrare il testo in chiaro “ATTACCATESUBITO” applicando ad ogni lettera del testo la funzione f di cifratura, si ottiene il seguente testo cifrato (da trasmettere lungo il canale di comunicazione):
“DZZDFFDZHVAENZR”
Analogamente, per rendere operativamente più semplice la decifratura, il destinatario scrive, sotto la successione delle lettere dell’alfabeto, la stessa successione “shiftata” verso sinistra di a posizioni: sotto ogni lettera y si trova la sua decifratura g(y).
Nell’esempio precedente (con a=3):
A B C D E F G H I L M N O P Q R S T U V Z
U V Z A B C D E F G H I L M N O P Q R S T
Decifrando il testo ricevuto “DZZDFFDZHVAENZR” (lettera per lettera) si riottiene il testo originale “ATTACCATESUBITO”.
Come abbiamo visto, nel sistema crittografico di Cesare la chiave di cifratura coincide con quella di decifratura, e ovviamente deve essere concordata in anticipo fra il mittente e il destinatario.
Il sistema di Cesare è poco sicuro: l’intruso che intercetti il messaggio cifrato, potrebbe cercare di risalire al messaggio in chiaro con il metodo della “forza bruta”, provando a decifrare il messaggio con tutte le possibili chiavi (che sono in tutto 21) fino ad ottenere un messaggio che abbia un senso compiuto.
