Lezioni di Geometria Franco Ghione |
![]() |
Codici lineari L'algebra lineare e le proprietà delle applicazioni lineari tra spazi vettoriali su un campo finito, possono essere utili per definire dei particolari codici per criptare un messaggio che si vuole mantenere segreto. In generale un determinato messaggio
x viene codificato in un nuovo messaggio irriconoscibile y = L(x). Questo nuovo messaggio y viene trasmesso
e può essere letto
da chiunque intercetti la trasmissione. Tuttavia per riconoscerlo occorre decriptarlo e per fare questo occorre conoscere l'operatore
L-1 di decodifica, operatore che, si suppone, sia noto solo al destinatario del messaggio. Il destinatario dunque riceve
il segnale
y, lo decodifica calcolando L-1(y) e può in questo modo leggere il messaggio originale
x = L-1(y). Il modo più semplice per fare questo è supporre L lineare. con questa notazione la stringa (x1,x2,x3,x4) corrisponde al numero decimale
Possiamo dunque pensare le parole come vettori
dello spazio F4 di dimensione 4. ![]() Con questo codice, la parola 9, ad esempio, che si scrive come x = (1,0,0,1) si codifica nella stringa A.x
cioè, eseguendo il prodotto, in y = (0,1,0,0). Questa è la striga che viene trasmessa e che può anche essere intercettata. Il destinatario
del messaggio, conoscendo il codice, può decodificare la stringa ricevuta calcolando A-1.y. ![]() Per produrre degli zeri nella prima colonna abbiamo sostituito la seconda riga con la somma delle prime due e la quarta con la somma della quarta con la prima. Il secondo elemento della seconda colonna è zero. Sostituiamo allora la seconda riga con la sua somma con la terza riga e facciamo operazioni elementari per produrre degli zeri sotto i pivot. ![]() A questo punto dobbiamo produrre degli zeri sopra il pivot della quarta colonna. Per questo sostituiamo la terza riga con la sua somma con la quarta, la seconda con la sua somma con la quarta e la prima con la sua somma con la quarta. ![]() Resta ancora da siatemare la prima riga. Per questo sostituiamo la prima riga con la sua somma con la seconda ![]() le ultime 4 colonne della matriche che abbiamo ottenuto sono le colonne della matrice A-1 che cercavamo ![]() Il messaggio in codice y può essere ora decodificato moltiplicandolo per la matrice A-1. Se
y = (0,1,0,0) allora, eseguendo il prodotto, abbiamo A-1.y = (1,0,0,1) e quindi la parola trasmessa era
23 + 1 = 9. e quindi la prima colonna della matrice A è (1,1,0,1). Analogamente, dato che e2 = u1 + u2, abbiamo la seconda colonna di A è allora (1,1,1,1). Poichè e3 = u3 + u4 la terza colonna di A è (0,1,1,1). Poichè, infine, e4 = u1 + u3 + u4 e quindi la quarta colonna di A è (1,0,0,1). Una volta calcolata la matrice A è possibile, per la spia decodificare qualunque messaggio y venga trasmesso dato che attraverso A, come abbiamo fatto precedentemente, si può calcolare A-1 e quindi x = A-1y. |