Il CampoVersario di Evaristo.

galois2

Il 25 ottobre 1811, esattamente 71527 giorni fa, nasceva a Bourg-la-Reine, in Francia, Évariste Galois.

A 19 anni Galois trovò la soluzione a un problema matematico che era rimasto fino ad allora irrisolto e con il quale i matematici di tutto il mondo si erano scontrati per almeno 350 anni: dimostrare quali sono le condizioni necessarie e sufficienti che definiscono se una equazione è risolvibile a mezzo radicali[1].

Sebbene questo risultato fu considerato all’epoca il più grande successo degli studi condotti da Galois nella sua breve vita (Galois morì a 21 anni in un duello, le cronache riportano per difendere l’onore di una ragazza, ma altre fonti riferiscono che la cosa fosse stata organizzata per ragioni politiche), la parte di quel lavoro che indubbiamente ha lasciato il segno più profondo, un segno senza il quale molte tecnologie che oggi diamo per scontate non esisterebbero, è che Évariste per affrontare questo problema si inventò una intera nuova branca della matematica, gettandone le basi: la teoria dei gruppi e dei campi, ossia, più in generale, l’algebra astratta.

Una parte enorme delle applicazioni matematiche nel campo dell’informatica, praticamente tutte quelle alla base della crittografia (gli strumenti che possono rendere le comunicazioni impossibili da intercettare da parte di estranei), della compressione dati (la possibilità di rendere un file da trasmettere “più piccolo”, senza cui non avremmo avuto la TV digitale, i telefoni cellulari, gli streaming video e audio, …), e dei sistemi di correzione degli errori (senza i quali non esisterebbe sostanzialmente nessun sistema di trasmissione digitale delle informazioni, dalla TV a tutte le tecnologie utilizzate per le connessioni internet né i sistemi di memorizzazione dati ad alta densità, dai CD ai dischi a stato solido), sono basate su un oggetto matematico che prende il nome da quel ragazzo: I Campi di Galois[2].

Se vi è venuta un pochino di curiosità in merito a cosa sia un Campo di Galois in questo articolo cercherò di spiegarlo nel modo più semplice possibile, alla portata di uno studente delle scuole primarie. Ovviamente con molte semplificazioni e prendendo qualche licenza.

Quello che serve è saper fare le quattro operazioni sui numeri interi e ricordare vagamente cosa sono una equazione e un sistema di equazioni lineari. Non è complicato vero? Poi facciamo anche un ripassino ma intanto iniziamo.

L’idea dietro a cui sta tutta la teoria dei campi è in fondo abbastanza semplice: la maggior parte delle “cose” che conosciamo sulla matematica “funzionano” in base al fatto che i numeri hanno alcune proprietà. Quali sono? Solo queste:

  • Esiste un insieme di numeri, o più propriamente di “simboli”, su cui stiamo lavorando, e su questi numeri sono definite due operazioni, che possono essere sempre fatte su due numeri qualsiasi ottenendone un terzo, chiamate somma (“+”) e “moltiplicazione (“•”).
  • Sia la somma che la moltiplicazione sono commutative (cioé è sempre vero che “a+b=b+a” e che “a•b=b•a” ) e associative (ossia è sempre vero che “a+(b+c)=(a+b)+c” e che “a•(b•c)=(a•b)•c”).
  • La moltiplicazione è “distributiva” rispetto all’addizione, quindi è sempre vero che (a+b)•c=(a•c)+(b•c).
  • C’è un numero speciale, lo “zero”, tale che se faccio “a+0” o “0+a” (abbiamo già detto che è lo stesso), il risultato è sempre e comunque a. Insomma questo numero è “neutro” rispetto all’addiziome, possiamo aggiungere zero tante volte quante vogliamo e il risultato non cambia.
  • C’è anche un numero neutro rispetto allla moltiplicazione, che chiamiamo “uno”: qualsiasi cosa moltiplicata per uno da sempre se stessa, quindi è sempre a•1=1•a=a.

Abbiamo studiato tutti, a partire dalle elementari, che queste proprietà sono vere per i numeri così come li conosciamo, che siano essi naturali, interi, razionali o real, e infatti nell’algebra elementare si danno per scontate.

Per avere quello che in matematica si chiama un “campo” però ci servono altre due proprietà che non sono vere, ad esempio, per i numeri naturali:

  • Per ogni numero esiste un “inverso additivo”, cioè preso un certo numero “a” posso trovare un altro numero “b=-a” tale che a+b=0 ; questa proprietà non ce l’hanno i numeri naturali perché, ovviamente, l’inverso di 1 è “-1” che non è un numero naturale ma un intero.
  • Per ogni numero, tranne quello che ho chiamato “zero”, esiste anche un inverso moltiplicativo, cioè preso un numero “a” posso trovare un altro numero “c=1/a” tale che “a•c=1”, quest’ultima non è vera nemmeno per i numeri interi perché ad esempio 1/2 non è intero ma razionale.

La cosa interessante è che basta che una qualche “entità” abbia queste proprietà e quasi tutta la matematica che conosciamo può essere usata su questa entità, questo è vero non solo per i numeri (che tutti sappiamo “sono infiniti”) ma anche per alcuni insiemi finiti di simboli: possiamo prendere in alcuni casi un insieme “finito” di simboli, definire le operazioni in modo che queste proprietà siano vere e trattarli come se fossero numeri, utilizzando poi moltissimi degli strumenti che la matematica mette a disposizione nell’algebra elementare.

La cosa servì a Galois per un obiettivo completamente diverso da quello per cui è poi diventata fondamentale per molte applicazioni moderne (come accennato stava lavorando sulla risoluzione delle equazioni con i radicali), ma secoli dopo divenne fondamentale con l’avvento dei computer.

Vi sembrerà strano ma un computer non può, in alcun modo, “rappresentare”, cioè contenere in memoria, un numero arbitrario, nemmeno un semplice numero intero. Il motivo è banale per un matematico, anche se sembra strano: la memoria di un computer è “finita”, ha una dimensione massima e quella è, per quanto grande sia; invece un numero, anche intero, potenzialmente non lo è. Possiamo usare dei trucchi per rappresentare nella memoria di un computer numeri molto grandi o fare dei computer con una memoria grandissima ma, comunque la mettiamo, esisterà sempre anche solo un numero intero talmente grande che nella memoria di quel computer non ci sta.

Quindi alcune cose che concettualmente sono molto semplici se fatte su un computer, prima o poi, si scontrano con questo limite: per esempio dal punto di vista matematico diamo per scontato che se ho due numeri interi, a e b, posso sempre calcolare un c=a+b, ho scritto prima che il fatto che qualsiasi addizione si possa sempre fare è una delle “premesse” dell’algebra; in un computer (qualsiasi computer) esisteranno sempre due numeri a e b tali che la loro somma a+b “è troppo grande” per stare nella memoria del computer, e quindi quella addizione non si potrà fare.

Ma Galois dimostrò che per usare molti strumenti della matematica non c’era bisogno di lavorare con numeri che possono avere “infiniti valori diversi”, tutt’altro. In pratica il tipo di matematica su cui lavorò Galois spiega come possiamo definire queste operazioni su un insieme di oggetti “finito”, mantenendo valide queste proprietà: proviamo a immaginare un universo in cui esistono solo sette numeri: 0, 1, 2, 3, 4, 5 e 6. Badate bene: non “da uno a sette”, perché ci serve lo zero, i nostri sette numeri sono “da zero a sei”.

Ora proviamo a definire le nostre operazioni partendo da quelle che conosciamo (l’addizione, la sottrazione, la moltiplicazione, la divisione), ma siccome i nostri numeri sono solo “da zero a sei” ci serve un trucco: l’aritmetica dell’orologio.

Se io dico che sono le sette del mattino, fra quattro ore che ora sarà? 7+4=11, saranno le undici. Ma se vi chiedo invece che ora sarà fra 21 ore? 7+21 farebbe 28 e certamente non saranno “le 27”: siccome il nostro orologio ha solo 24 ore (per chiarezza: le chiamo da zero a ventitre!) dopo il 23 ripartiamo da zero, quindi sull’orologio 7+21=4. Posso anche dire che ore saranno fra 100 ore: 7+100=107≈11, dove quel “≈” sta a significare “equivalente a” e si può calcolare intuitivamente “togliendo 24 tante volte quante bastano” oppure con un trucchetto: dividendo per 24 e prendendo il resto della divisione (provate).

Così come in un orologio ci sono solo 24 ore, e quindi dobbiamo ridurre i risultati a stare tra zero e ventitrè, nel nostro mondo di soli sette numeri dobbiamo ridurre i risultati ad essere tra zero e sei, e lo facciamo nello stesso modo, quindi:

  • 2+2 fa 4, 3+2 fa 5, come ci si aspetta; ma 4+4 (che farebbe otto e non “ci sta”) lo risolviamo togliendo sette, e quindi 4+4=1
  • 2•3 fa 6; ma 3•3 farebbe nove, e quindi anche quì togliamo sette: 3•3=2; analogamente 5•4=6 (togliamo due volte 7), 6•5=2 (togliamo 3 volte sette), eccetera.
  • Per finire 2-5, che farebbe meno tre, lo risolviamo aggiungendo sette: 2-5=4 !

La cosa sorprendente è che in questo mondo strano con solo sette numeri “torna tutto”: vale la proprietà distributiva delle moltiplicazioni, si possono scrivere e risolvere le equazioni (che avranno il numero che ci si aspetta di soluzioni), si possono scrivere e risolvere (con gli stessi strumenti che conosciamo) sistemi di equazioni lineari, eccetera.

Non solo: possiamo anche inventarci una “geometria”, in cui il piano invece che essere costituito da un insieme infinito di punti è una specie di campo della battaglia navale quadrato con un numero intero e finito di “punti” che sono le caselline e, indovinate un po’?, su questo “piano” valgono gran parte delle cose che conosciamo per la geometria “dei numeri infiniti”.

Una delle cose che Galois dimostrò è che se prendiamo una certa quantità di simboli (nell’esempio sopra i numeri da zero a sei) e questa quantità è un numero primo (come 7) oppure una potenza esatta di un singolo numero primo (come 49 = 7•7, oppure 225=5^3, oppure 256=2^8) allora esiste sempre un modo per definire le nostre operazioni che rende questo insieme di simboli un “campo”; dimostrò anche che se definiamo le operazioni in modi diversi in verità il campo è sempre lo stesso: abbiamo solo “cambiato nome” ai nostri simboli.

Per contro se il numero di simboli con cui lavoriamo è un numero composto da fattori primi distinti (ad esempio 10, che è 2•5) allora non è possibile definire delle operazioni che ci consentano di trattare questo insieme di simboli come un campo.

Se prendiamo un insieme costituito da un numero primo di simboli (come nel caso di sette) il modo più semplice è definire le operazioni come già le conosciamo salvo prendere come risultato “il resto della divisione per quel numero primo”, è esattamente quello che ho fatto nell’esempio sopra; se invece il numero di simboli con cui lavoriamo è una potenza esatta di un numero primo le operazioni sono concettualmente un ben più complesse ma, in pratica, ancora fattibili[3].

Se non ci avete fatto caso prima ho fatto un esempio importante dal punto di vista pratico: 2 è un numero primo, 2 all’ottava potenza fa 256, e quindi è possibile definire un “campo” con 256 simboli.

Ricordiamoci che la memoria di un computer è organizzata in “byte” e un byte può avere esattamente 256 valori diversi, è chiaro che il GF256 (che non è la perpetuazione del Grande Fratello per i nostro pronipoti, sta per “Galois Field 256”, ossia “Campo di Galois con 256 elementi”) è un candidato ideale per i computer: il campo GF256, anche noto come “Rijndael Field”, è infatti uno dei più usati in crittografia e altre applicazioni, perché i byte sono ideali per rappresentare i valori dei “numeri” in quel campo e ogni valore possibile di un byte corrisponde esattamente a un elemento di quel campo.

Vi avevo promesso (o minacciato) una ripassatina, piccola piccola, ad alcune basi della matematica delle medie e del liceo, eccola: i sistemi di equazioni lineari.

  • Se abbiamo un’equazione di primo grado in un’incognita è molto facile risolverla, ad esempio se scrivo 2•x+3=7 con un paio di passaggi ricavo facilmente che x=2, e infatti 2•2+3=4+3=7; se non vi ricordate i passaggi non importa, basta che abbiate chiaro che si può sempre fare.
  • Se le incognite, cioè le variabili che non conosco, sono due (chiamiamole x ed y), allora mi servono due equazioni. Ad esempio se dico che deve essere x+y = 1 e al tempo stesso x-y=1 è facile verificare che i conti tornano con x=1 e y=0, e in genere è anche abbastanza facile (ma non importa se non ricordiamo come) trovare questo risultato. Però possono capitarmi due intoppi: il primo è che le due equazioni potrebbero in realtà essere la stessa equazione, ad esempio se dico x+y=1 e 2•x+2•y=2 la seconda si può ottenere dalla prima e quindi qualsiasi valore di x e y che soddisfa la prima soddisfa anche la seconda, in questo caso si dice che le equazioni “non sono indipendenti” e il mio sistema ha infinite soluzioni; il secondo è che le due equazioni potrebbero contraddirsi, ad esempio se dico x+y=1 e x+y=2 è ovvio che se fa uno non fa due, non ci saranno mai due valori per i quali le due equazioni sono contemporaneamente vere, in questo caso diremmo che il sistema è “impossibile”.
  • Se ho un certo numero di incognite, diciamo “n incognite” e ho “n equazioni” la situazione è molto simile: se le n equazioni sono indipendenti tra loro e non si contraddicono posso trovare la soluzione (unica), altrimenti (se non sono indipendenti) le soluzioni sono infinite o (se due si contraddicono) la soluzione non c’è. Al liceo avevamo studiato un metodo (mettere le equazioni in forma “normale”, prendere tutti i coefficienti e metterli in una matrice, controllare il rango di questa matrice e poi fare altre operazioni) che ci consentiva di prendere un sistema con “n” equazioni qualsiasi, capire come stanno le cose e, se esiste ed è unica, trovare la soluzione.
  • Ovviamente se le equazioni sono meno delle incognite non avremo mai una soluzione unica, ma se invece abbiamo delle equazioni “di troppo”, ossia abbiamo “n” equazioni con “m” incognite, dove n è più grande di “m”, purché le equazioni siano sempre tutte indipendenti e non si contraddicano a vicenda, possiamo sempre trovare la soluzione con un trucco banale: ignoriamo le equazioni di troppo.

A questo punto sono certo che indovinerete: sta cosa dei sistemi di “n” equazioni lineari in “m” incognite è una delle tante, tantissime, cose che restano tali e quali se invece che lavorare con “numeri veri” stiamo lavorando in un campo di Galois. Vere, identiche, con le stesse formule, gli stessi modi per risolverle, le stesse procedure; solo che i “numeri” sono piccoli, finiti e facili da gestire al computer.

Circa 150 anni dopo la nascita di Evariste Galois, nel 1960, due matematici chiamati Irving Stoy Reed e Gustave Solomon pubblicarono un articoletto, piccolo piccolo (una pagina e mezza, otto formule, un solo esempio, pochi fronzoli[4]), in cui dicevano queste cose:

  • Supponiamo che io abbia un messaggio di “m” simboli, posso immaginare che questi simboli siano “numeri” di un campo di Galois
  • Se calcolo il valore di un certo polinomio, cioè di una certa espressione (quello di grado “m” che ha quei “simboli” come coefficienti, ma è un dettaglio che a noi ora non interessa) per “n” valori distinti ottengo una sequenza di “n” simboli, con n più grande di m.
  • Se metto questi n simboli uno sopra all’altro e ci metto di fianco una certa matrice (chiamata matrice di Vandermonde, dal nome del matematico francese Alexandre-Théophile Vandermonde che studiò queste matrici all’inizio del 700, ma anche questo è un dettaglio) ottengo i coefficienti di “n” equazioni, che sono indipendenti tra loro, che non si contraddicono, che hanno “m” incognite e che hanno come soluzioni gli “m” numeri da cui ero partito.
  • Se “trasmetto” a qualcuno questi “n” numeri, chi li riceve può ricostruire il messaggio originale risolvendo le equazioni; se invece che riceverli tutti “n” il destinatario se ne perde un po’, basta che ne abbia almeno “m” e saranno abbastanza per risolvere il sistema di equazioni e ricostruire il messaggio originale; addirittura se ne riceve qualcuno “sbagliato” finché quelli sbagliati sono abbastanza pochi avrà informazioni sufficienti per capire quali sono le equazioni che “non quadrano” con le altre, scartarle, e ricostruire comunque la soluzione corretta.

Vi siete persi? Non importa, riassumo solo quello che ci serve per proseguire.

Reed&Solomon dimostrarono che se prendo un messaggio, ad esempio, di 100 “byte” (potrebbe essere un SMS o un pezzetto di un file), considero questi “byte” dei numeri in un campo di Galois e faccio determinate operazioni posso ottenere un pacchetto più grande, ad esempio di 256 byte, e trasmetterlo a qualcuno; se il destinatario ne riceve “almeno 100” e sa che gli altri sono andati persi, oppure se lo riceve tutto ma, ad esempio, con una settantina di byte “sbagliati” può comunque ricostruire il messaggio originale.

Prima di riflettere sulle applicazioni pratiche di questa cosa ricordiamoci che viene dagli studi di Galois (inizio 700), dalle matrici di Vandermonde (metà 700), dagli studi sui sistemi di equazioni lineari di Eugène Rouché e Alfredo Capelli (fine 800), e completiamo il quadro dicendo che Reed e Solomon non dissero nemmeno in dettaglio come risolvere le equazioni se qualche dato era arrivato “sbagliato” per il banale motivo che non avevano idea di come farlo: loro espressero il principio, al modo di utilizzarlo praticamente iniziò a lavorarci un anno dopo un altro matematico, William Wesley Peterson, e poi nove anni dopo altri due matematici di nome Elwyn Berlekamp e James Massey[5] trovarono il modo “pratico” di decodificare il messaggio in presenza di errori, e dopo altri 10 anni Richard Blahut[6] mostrò come il metodo poteva essere enormemente migliorato e semplificato grazie al fatto che moltissimi altri strumenti matematici di solito applicati ai numeri complessi e usati nella teoria dei segnali e delle telecomunicazioni (le trasformate di Fourier, l’analisi di spettro, eccetera) avevano anche esse le corrispondenti “forme” nei campi di Galois (la trasformata NTT e lo spettro discreto), forme che consentirono poi di sviluppare algoritmi e circuiti molto più efficienti per implementare i codici Reed-Solomon.

L’applicazione di questa cosa è, sostanzialmente, in qualsiasi oggetto del nostro quotidiano che abbia a che fare con il trasmettere delle informazioni via radio o cavo oppure con il memorizzarle: dai telefoni cellulari ai computer, dai CD alla TV digitale, dalle comunicazioni via satellite al GPS.

Nessuno di questi oggetti, nella forma che conosciamo, potrebbe esistere senza gli strumenti di cui ho parlato sopra, a partire dal lavoro di Évariste Galois.

Il motivo è molto semplice: tutti i mezzi di comunicazione moderni sono digitali, ossia trattano la voce, le immagini, i documenti, il testo e i programmi come “numeri” o “simboli”; ogni volta che trasmettiamo o memorizziamo dei dati c’è una probabilità significativa che una parte di questi dati vada persa o sia “danneggiata” (un disturbo lungo la linea, un difetto della superficie di un disco, un fruscio in una trasmissione radio).

Mentre in una vecchia radio analogica il fruscio di fondo o un crepitio di un disturbo lo possiamo anche sentire ad orecchio ma non ha grandi conseguenze, per un computer basta che in un programma o un file ci sia un solo byte “corrotto” per avere effetti catastrofici: tutto il file o il programma è potenzialmente inutilizzabile.

Se a questo aggiungiamo che i moderni sistemi di trasmissione dati e di memorizzazione sono progettati, con il fine di andare più veloci possibile, per lavorare “sul filo del rasoio” della capacità canale di trasmissione (immaginiamoci una vecchia radio con lo speaker che parla velocissimo per “poter dire tante cose in poco tempo occupando solo un canale”) è facile comprendere come la probabilità che qualche pezzo di informazione venga ricevuto sbagliato o disturbato è piuttosto alta. Ecco perché oggi i codici Reed Solomon (o la loro generalizzazione, i codici BCH, e altri della famiglia) sono usati in tutti gli oggetti tecnologici che ci circondano.

Questa è solo una delle decine di tecnologie rese possibili dagli studi di quel ragazzino nato in un villaggio francese più di 200 anni fa, esattamente 71527 giorni fa (e sì, 71527 è un numero primo, quindi con 71527 elementi ci si può costruire un “Campo di Galois”, per questo l’ho celebrato oggi), e morto in duello a 21 anni dopo aver scritto un pezzo della storia della matematica.

Per capire il valore delle “scienze fondamentali” occorre un po’ di visione prospettica, e ho voluto darvene un esempio; perché quando qualcuno apprende che tra le mie passioni c’è l’algebra astratta leggo spesso nello sguardo un “ah, quella roba inutile” e non ho voglia di spiegare che da qualche anno dedico domeniche, vacanze e qualche notte a cercare di trovare un adattamento ai campi finiti della trasformata di Laplace con cui affrontare il problema del list-decoding per prossimità dei codici ciclici che (nell’improbabilissimo caso in cui ci riuscissi, e fra 20 anni) potrebbe risolvere problemi come “cerchiamo i pezzi di DNA che “assomigliano” a questo.

È più semplice rispondere “sì, roba inutile, in fondo l’hai usata solo trenta secondi fa per rispondere a un commento su FaceBook”.

[1] Vedi https://en.wikipedia.org/wiki/Abel%E2%80%93Ruffini_theorem

[2] Per una introduzione più formale e completa all’argomento vedi ad esempio https://nrich.maths.org/1422

[3] Questo è davvero complicato, ma se siete coraggiosi potete iniziare da qui, trovando anche molti riferimenti: http://mathworld.wolfram.com/FiniteField.html

[4] http://www.jstor.org/stable/2098968

[5] E qui davvero non faccio esempi perché iniziamo ad avere a che fare con un tipo di matematica che spaventa anche… molti docenti di matematica. Ecco spiegato l’algoritmo di Berlekamp-Massey “in poche parole”: ftp://ftp.disi.unige.it/person/MoraF/MaterialeCTC/BerlekampMassey.pdf

[6] Questo piacerà agli ingegneri: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5390847&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F5288520%2F5390841%2F05390847.pdf%3Farnumber%3D5390847

 

Rispondi

%d blogger hanno fatto clic su Mi Piace per questo: