Algebra de bază din spatele codurilor secrete și al comunicării spațiale

Explorarea spațiului necesită o precizie extraordinară. Când aterizați un rover pe Marte la 70 de milioane de mile distanță de cea mai apropiată stație de service, trebuie să maximizați eficiența și să vă pregătiți pentru neașteptat. Acest lucru se aplică tuturor, de la proiectarea navelor spațiale până la transmisia de date: acele mesaje care se întorc pe Pământ ca un flux constant de 0 și 1 trebuie să conțină unele erori, așa că trebuie să le puteți identifica și corecta fără a pierde timp și energie prețioasă.

Aici intervine matematica. Matematicienii au inventat modalități ingenioase de a transmite și stoca informații. O metodă surprinzător de eficientă folosește Codurile Reed-Solomon, care sunt construite pe aceeași algebră de bază pe care o învață elevii la școală. Să trecem la un curs de matematică pentru a vedea cum codurile Reed-Solomon ajută la transmiterea și securizarea informațiilor, corectând în același timp orice erori costisitoare care apar.

Doi studenți, Art și Zeke, fac schimb de mesaje secrete la ora de matematică a doamnei Al-Jabr. Art dezvăluie ultima notă a lui Zeke pentru a dezvălui numerele 57 și 99. El știe că trebuie să furnizeze x-coordonatele 3 și 6 pentru a crea punctele (3, 57) și (6, 99). Art conectează fiecare punct în ecuația liniară y = Ax + B și produce următorul sistem de ecuații:

57 = 3A + B

99 = 6A + B

Pentru a decoda mesajul, Art trebuie să rezolve A și B. El începe prin a scădea prima ecuație din a doua:

Aceasta elimină B. Împărțirea ambelor părți ale acestei noi ecuații la 3 îi spune lui Art că A = 14, iar apoi înlocuind aceasta înapoi în prima ecuație, 57 = 3 × 14 + B, dă B = 15.

Art știe acum că linia care trece prin (3, 57) și (6, 99) este descrisă de ecuația y = 14x + 15. Dar mai știe că într-un cod Reed-Solomon, mesajul secret se ascunde în coeficienți. El decodifică mesajul lui Zeke folosind cifrul lor alfabetic simplu convenit: 14 este „N” și 15 este „O”, ceea ce îi spune lui Art că, nu, Zeke nu poate juca jocuri video astăzi după școală.

Secretul acestui cod simplu Reed-Solomon începe cu două fapte de bază ale geometriei. În primul rând, prin oricare două puncte există o linie unică. În al doilea rând, pentru coeficienți A și B, fiecare linie (neverticală) poate fi scrisă sub formă y = Ax + B. Împreună, aceste două fapte garantează că dacă știi două puncte pe o linie poți găsi A și B, și dacă știi A și B, știi toate punctele de pe linie. Pe scurt, deținerea oricărui set de informații echivalează cu cunoașterea liniei.

Codurile Reed-Solomon folosesc aceste seturi echivalente de informații. Mesajul secret este codificat ca coeficienți A și B, iar punctele liniei sunt rupte în bucăți, dintre care unele sunt transmise public, iar altele sunt păstrate private. Pentru a decoda mesajul, trebuie doar să colectați piesele și să le puneți la loc. Și tot ceea ce necesită acest lucru este o simplă algebră.

Piesele lui Zeke erau numerele 57 și 99, pe care le-a trimis la Art. Aceste numere sunt partea publică a mesajului. Arta le-a pus împreună cu propriile sale piese, 3 și 6, pentru a reconstrui punctele (3, 57) și (6, 99). Aici, 3 și 6 constituie partea privată a mesajului, despre care Art și Zeke au convenit în prealabil.

Cele două puncte se află pe o linie, iar pentru a decoda mesajul, trebuie doar să găsiți ecuația acelei linii. Conectarea fiecărui punct la y = Ax + B vă oferă un sistem de două ecuații despre linie care trebuie să fie ambele adevărate. Acum strategia este simplă: rezolvați sistemul, determinați linia și decodați mesajul.

La ora de algebră probabil ați învățat multe metode de rezolvare a sistemelor de ecuații, cum ar fi reprezentarea grafică, ghicitul și verificarea și înlocuirea. Art a folosit eliminarea, o metodă în care manipulezi ecuațiile algebric pentru a elimina variabilele pe rând. De fiecare dată când elimini o variabilă, sistemul devine puțin mai ușor de rezolvat.

Ca și în cazul altor scheme de criptare, este combinația inteligentă de informații publice și private care păstrează mesajele în siguranță. Zeke și-ar putea striga numerele 57 și 99 în toată sala de clasă și nu ar pune în pericol securitatea mesajului său către Art (deși ar putea să-i facă probleme cu doamna Al-Jabr). Asta pentru că fără informațiile private corespunzătoare — x-coordonatele 3 și 6 — este imposibil de identificat ecuația dreptei. Atâta timp cât păstrează acele valori pentru ei înșiși, își pot transmite în siguranță mesajele secrete în public.

Linia y = 14x + 15 este bine pentru a transmite cuvântul de două litere „nu”, dar ce se întâmplă dacă elevii doresc să împărtășească un secret mai lung? Aici intră în joc întreaga putere a algebrei, geometriei și sistemelor de ecuații liniare.

Să presupunem că Zeke vrea să știe cum crede Art că se va descurca la testul de engleză de mâine. Art își transformă răspunsul de trei litere în numerele 14, 59 și 82 și le transmite lui Zeke. Elevii au convenit în prealabil că, atunci când folosesc coduri Reed-Solomon de lungime 3, numerele lor private sunt 2, 5 și 6, așa că Zeke pune piesele împreună pentru a reconstrui punctele (2, 14), (5, 59) și (6, 82).

Acum, nu există nicio funcție liniară care să treacă prin aceste trei puncte. Dar există o funcție pătratică unică care o face. Și deoarece fiecare funcție pătratică poate fi scrisă sub forma y = Ax² + Bx + C, se poate aplica aceeași metodă generală. Singura diferență este dimensiunea sistemului.

Conectarea fiecărui punct la y = Ax² + Bx + C dă o ecuație, astfel încât cele trei puncte produc următorul sistem de trei ecuații:

(2, 14): 14 = 4A + 2B + C

(5, 59): 59 = 25A + 5B + C

(6, 82): 82 = 36A + 6B + C

Un sistem de trei ecuații cu trei necunoscute necesită puțin mai multă muncă de rezolvat decât un sistem de două ecuații cu două necunoscute, dar scopul este același: combinați inteligent perechi de ecuații pentru a elimina variabilele.

De exemplu, dacă scadeți prima ecuație din a doua, obțineți noua ecuație 45 = 21A + 3B. La fel, dacă scădeți a doua ecuație din a treia, obțineți 23 = 11A + B. Aceste manipulări algebrice produc un nou sistem:

45 = 21A + 3B

23 = 11A + B

Acum aveți un sistem „două câte doi”: două ecuații cu două necunoscute. Pentru a o rezolva, puteți înmulți a doua ecuație cu −3 și adăugați-o la prima ecuație:

Observați cum eliminarea repetată a transformat sistemul original de trei ecuații într-o singură ecuație care poate fi rezolvată cu ușurință: A = 2. Lucrând înapoi, puteți conecta A = 2 într-una dintre ecuațiile din sistemul doi câte doi pentru a găsi B = 1, apoi introduceți ambele valori într-una dintre ecuațiile originale pentru a obține C = 4. După ce a folosit cifrul alfabetic simplu pe 2, 1 și 4, Zeke știe că Art va face „RAU” la testul de engleză de mâine. Cel puțin, el primește multă practică de algebră.

Datorită unui fapt special despre funcțiile polinomiale, puteți transmite un mesaj de orice lungime folosind codurile Reed-Solomon. Cheia este aceasta: Dat oricare n puncte din plan cu diferite x-coordonate, există un polinom unic de „grad” n − 1 care trece prin ele. Gradul unui polinom este cea mai mare putere a unei variabile din expresie, deci o funcție pătratică ca Ax² + Bx + C are gradul 2, deoarece puterea cea mai mare de x este 2. Și o funcție liniară are gradul 1, deoarece în ecuație y = Ax + B, cea mai mare putere a x este 1.

În primul exemplu am folosit faptul că două puncte determină un polinom liniar unic, sau de gradul 1. În al doilea, ne-am bazat pe faptul că trei puncte determină un polinom unic de grad 2, sau pătratic. Și dacă doriți să trimiteți un mesaj cu lungimea 10, codificați mesajul ca cei 10 coeficienți ai unei funcții polinomiale de gradul 9. Odată ce ai funcția ta, calculează cele 10 publice y-valori prin evaluarea functiei la cele 10 private convenite anterior x-valori. Odată ce faci asta, le poți trece în siguranță y-coordonate în public pentru ca receptorul dvs. să le decode. În practică, codurile Reed-Solomon sunt puțin mai complexe decât aceasta, utilizând tipuri mai sofisticate de coeficienți și scheme de traducere, dar ideea fundamentală este aceeași.

Pe lângă faptul că vă păstrează mesajul în siguranță, codurile Reed-Solomon oferă și modalități simple și eficiente de a capta și chiar de a corecta erorile. Acest lucru este important oricând datele sunt transmise sau stocate, deoarece există întotdeauna șansa ca unele dintre informații să se piardă sau să fie corupte.

O soluție la această problemă ar fi să trimiteți pur și simplu copii suplimentare ale datelor. De exemplu, Zeke poate trimite mesajul [14, 14, 14, 15, 15, 15] în loc de [14, 15]. Atâta timp cât Art știe că fiecare parte a mesajului este trimisă în trei exemplare, el poate decoda mesajul și poate verifica erorile. De fapt, dacă găsește erori, are șanse mari să le corecteze. Dacă Art primește [14, 14, 24, 15, 15, 15], faptul că primele trei numere sunt diferite îl avertizează asupra unei erori și, deoarece două dintre ele sunt 14, el poate ghici că 24 ar trebui să fie probabil un 14 de asemenea. În loc să ceară ca mesajul să fie retrimis, Art poate continua cu decodarea. Aceasta este o strategie eficientă, dar costisitoare. Indiferent de timp, energie și efort sunt necesare pentru a trimite n informații, aceasta necesită de trei ori mai mult.

Dar matematica din spatele codurilor Reed-Solomon oferă o alternativă eficientă. În loc să trimiteți mai multe copii ale fiecărei date, puteți trimite doar un punct în plus! Dacă acel punct suplimentar se potrivește cu polinomul tău, atunci informațiile sunt corecte. Dacă nu, a apărut o eroare.

Pentru a vedea cum funcționează, să presupunem că doriți să verificați mesajul „NU” din primul exemplu. Zeke poate trimite doar suplimentar y-coordonată 155. Presupunând că el și Art au convenit asupra unui al treilea privat x-coordonează în prealabil, să zicem x = 10, Art poate verifica acest al treilea punct cu linia pe care a decodat-o. Când conectează x = 10 în y = 14x + 15 și vede că rezultatul este 155, știe că nu au fost erori de transmisie.

Acest lucru nu funcționează doar pentru linii. Pentru a-i permite lui Zeke să bifeze „RAU” în al doilea exemplu, Art poate trimite y = 25. Dacă au fost de acord că 3 este extra privat x-coordonate, Zeke poate conecta x = 3 în funcția sa pătratică y = 2x² + x + 4 și verificați dacă punctul (3, 25) se potrivește, confirmând din nou o transmisie fără erori cu doar un singur punct.

Și acest punct suplimentar poate corecta și erorile. Dacă este detectată o eroare și receptorul nu poate construi funcția polinomială care conține mesajul, el poate construi polinomul „cel mai potrivit” folosind tehnici de regresie. Ca o linie de cea mai bună potrivire în clasa de statistică, aceasta este funcția polinomială care este determinată matematic să se potrivească cel mai bine punctelor date, chiar dacă nu trece prin toate. În funcție de structura mesajului și de câte informații suplimentare trimiteți, acest polinom cel mai potrivit vă poate ajuta să reconstruiți polinomul corect - și, prin urmare, mesajul corect - chiar și din informații corupte.

Această eficiență în transmiterea și corectarea comunicațiilor explică de ce NASA a folosit coduri Reed-Solomon în misiunile sale pe Lună și pe Marte. Și îți oferă ceva la care să te gândești în timp ce rezolvi următorul sistem de ecuații. Pe măsură ce ghiciți, verificați sau eliminați calea către soluție, gândiți-vă la puterea și eleganța codurilor Reed-Solomon și la toate secretele pe care sistemul dumneavoastră le-ar putea dezvălui.

Exerciții

1. Folosind aceeași schemă pe care a folosit-o la clasă, Art postează numerele publice 33 și 57 pentru ca Zeke să le decodeze. Care este mesajul?

2. Cum pot Art și Zeke să fie siguri că sistemul de ecuații care rezultă din numerele lor private x = 3 și x = 6 va avea întotdeauna o soluție?

3. Ca răspuns la mesajul lui Art de „RAU” despre testul de engleză, Zeke trimite înapoi [90, 387, 534]. Presupunând că folosesc aceeași schemă pe care au folosit-o în clasă, care este mesajul lui?

4. Lola îți trimite un mesaj din două litere plus un număr de verificare a erorilor folosind un cod Reed-Solomon și același cifru alfabetic simplu folosit de Art și Zeke. Ați convenit în secret cu privire la x-coordonatele 1, 3 si 10 in avans, iar Lola transmite numerele publice [27, 43, 90]. Mesajul contine o eroare?