Podstawowa algebra kryjąca się za tajnymi kodami i komunikacją kosmiczną

Eksploracja kosmosu wymaga ogromnej precyzji. Kiedy lądujesz łazikiem na Marsie 70 milionów mil od najbliższej stacji paliw, musisz zmaksymalizować wydajność i przygotować się na nieoczekiwane. Dotyczy to wszystkiego, od projektu statku kosmicznego po transmisję danych: wiadomości powracające na Ziemię w postaci ciągłego strumienia zer i jedynek z pewnością zawierają pewne błędy, więc musisz być w stanie je zidentyfikować i poprawić bez marnowania cennego czasu i energii.

I tu wkracza matematyka. Matematycy wymyślili genialne sposoby przesyłania i przechowywania informacji. Stosuje się jedną zaskakująco skuteczną metodę Kody Reeda-Solomona, które są zbudowane na tej samej podstawowej algebrze, której uczniowie uczą się w szkole. Wpadnijmy na zajęcia z matematyki, aby zobaczyć, jak kody Reeda-Solomona pomagają przesyłać i zabezpieczać informacje, jednocześnie korygując pojawiające się kosztowne błędy.

Dwóch uczniów, Art i Zeke, wymienia tajne wiadomości na zajęciach z matematyki pani Al-Jabr. Art rozwija ostatnią notatkę Zeke'a, aby ujawnić liczby 57 i 99. Wie, że musi dostarczyć x-współrzędne 3 i 6 tworzą punkty (3, 57) i (6, 99). Art podłącza każdy punkt do równania liniowego y = Ax + B i daje następujący układ równań:

57 = 3A + B

99 = 6A + B

Aby rozszyfrować wiadomość, Art musi rozwiązać problem A i B. Zaczyna od odjęcia pierwszego równania od drugiego:

To eliminuje B. Dzielenie obu stron tego nowego równania przez 3 mówi Artowi, że A = 14, a następnie podstawiając to z powrotem do pierwszego równania, 57 = 3 × 14 + B, daje B = 15.

Sztuka wie teraz, że prosta przechodząca przez (3, 57) i (6, 99) jest opisana równaniem y = 14x + 15. Ale wie też, że w kodzie Reeda-Solomona tajna wiadomość jest ukryta we współczynnikach. Dekoduje wiadomość Zeke'a za pomocą ich prostego, uzgodnionego szyfru alfabetycznego: 14 to „N”, a 15 to „O”, co mówi Artowi, że nie, Zeke nie może dzisiaj grać w gry wideo po szkole.

Sekret tego prostego kodu Reeda-Solomona zaczyna się od dwóch podstawowych faktów geometrii. Po pierwsze, przez dowolne dwa punkty przechodzi niepowtarzalna linia. Po drugie, dla współczynników A i B, każda (niepionowa) linia może być zapisana w postaci y = Ax + B. Razem te dwa fakty gwarantują, że jeśli znasz dwa punkty na linii, możesz je znaleźć A i B, a jeśli wiesz A i B, znasz wszystkie punkty na prostej. Krótko mówiąc, posiadanie któregokolwiek zestawu informacji jest równoznaczne ze znajomością linii.

Kody Reeda-Solomona wykorzystują te równoważne zestawy informacji. Tajna wiadomość jest zakodowana jako współczynniki A i B, a punkty linii są podzielone na części, z których część jest przekazywana publicznie, a część jest prywatna. Aby odszyfrować wiadomość, po prostu zbierasz elementy i składasz je z powrotem. Wszystko, czego to wymaga, to prosta algebra.

Kawałki Zeke'a to numery 57 i 99, które wysłał do Art. Numery te stanowią publiczną część wiadomości. Art połączył je ze swoimi własnymi elementami, 3 i 6, aby zrekonstruować punkty (3, 57) i (6, 99). Tutaj 3 i 6 stanowią prywatną część wiadomości, którą Art i Zeke uzgodnili wcześniej.

Dwa punkty leżą na linii, a aby zdekodować wiadomość, wystarczy znaleźć równanie tej linii. Podłączanie każdego punktu y = Ax + B daje układ dwóch równań dotyczących prostej, które muszą być prawdziwe. Teraz strategia jest prosta: rozwiąż system, określ linię i zdekoduj wiadomość.

Na zajęciach z algebry prawdopodobnie poznałeś wiele metod rozwiązywania układów równań, takich jak tworzenie wykresów, zgadywanie i sprawdzanie oraz podstawianie. Art wykorzystał eliminację, metodę, w której algebraicznie manipuluje się równaniami w celu wyeliminowania zmiennych pojedynczo. Za każdym razem, gdy eliminujesz zmienną, system staje się trochę łatwiejszy do rozwiązania.

Podobnie jak w przypadku innych schematów szyfrowania, sprytne połączenie informacji publicznych i prywatnych zapewnia bezpieczeństwo wiadomości. Zeke mógłby wykrzyczeć swoje numery 57 i 99 w całej klasie i nie zagroziłoby to bezpieczeństwu jego wiadomości do Arta (chociaż mogłoby to wpędzić go w kłopoty z panią Al-Jabr). To dlatego, że bez odpowiednich informacji prywatnych — x-współrzędne 3 i 6 — nie można określić równania prostej. Tak długo, jak zachowują te wartości dla siebie, mogą bezpiecznie przekazywać swoje tajne wiadomości publicznie.

Linia y = 14x + 15 wystarczy do przekazania dwuliterowego słowa „nie”, ale co zrobić, jeśli uczniowie chcą podzielić się dłuższą tajemnicą? Tutaj do gry wchodzi pełna moc algebry, geometrii i układów równań liniowych.

Załóżmy, że Zeke chce wiedzieć, jak według Arta wypadnie jutrzejszy sprawdzian z angielskiego. Art zamienia swoją trzyliterową odpowiedź na liczby 14, 59 i 82 i przekazuje je Zeke. Uczniowie ustalili wcześniej, że używając kodów Reeda-Solomona o długości 3, ich liczbami prywatnymi są 2, 5 i 6, więc Zeke łączy elementy, aby zrekonstruować punkty (2, 14), (5, 59) i (6, 82).

Teraz nie ma funkcji liniowej, która przechodzi przez te trzy punkty. Ale istnieje wyjątkowa funkcja kwadratowa, która to robi. A ponieważ każdą funkcję kwadratową można zapisać w postaci y = Ax² + Bx + Cmożna zastosować tę samą ogólną metodę. Jedyną różnicą jest rozmiar systemu.

Podłączanie każdego punktu y = Ax² + Bx + C daje jedno równanie, więc trzy punkty tworzą następujący układ trzech równań:

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

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

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

Układ trzech równań z trzema niewiadomymi wymaga nieco więcej pracy niż układ dwóch równań z dwiema niewiadomymi, ale cel jest ten sam: sprytnie połączyć pary równań, aby wyeliminować zmienne.

Na przykład, jeśli odejmiesz pierwsze równanie od drugiego, otrzymasz nowe równanie 45 = 21A + 3B. Podobnie, jeśli odejmiesz drugie równanie od trzeciego, otrzymasz 23 = 11A + B. Te algebraiczne manipulacje tworzą nowy system:

45 = 21A + 3B

23 = 11A + B

Teraz masz system „dwa na dwa”: dwa równania z dwiema niewiadomymi. Aby go rozwiązać, możesz pomnożyć drugie równanie przez −3 i dodać je do pierwszego równania:

Zauważ, jak wielokrotne eliminacje zmieniły pierwotny układ trzech równań w jedno równanie, które można łatwo rozwiązać: A = 2. Działając wstecz, możesz podłączyć A = 2 do jednego z równań w systemie dwa na dwa, aby znaleźć B = 1, a następnie wstaw obie wartości do jednego z oryginalnych równań, aby otrzymać C = 4. Po użyciu prostego szyfru alfabetycznego na liczbach 2, 1 i 4 Zeke wie, że Art wypadnie „ŹLE” na jutrzejszym teście z angielskiego. Przynajmniej ma dużo ćwiczeń z algebry.

Dzięki szczególnemu faktowi dotyczącemu funkcji wielomianowych, możesz przesłać wiadomość o dowolnej długości za pomocą kodów Reeda-Solomona. Kluczem jest to: biorąc pod uwagę dowolny n punkty na płaszczyźnie z różnymi x-współrzędnych, istnieje unikalny wielomian „stopień” n − 1, która przez nie przechodzi. Stopień wielomianu jest najwyższą potęgą zmiennej w wyrażeniu, a więc funkcją kwadratową Ax² + Bx + C ma stopień 2, ponieważ najwyższa potęga x wynosi 2. A funkcja liniowa ma stopień 1, ponieważ w równaniu y = Ax + B, najwyższa potęga x to 1.

W pierwszym przykładzie wykorzystaliśmy fakt, że dwa punkty wyznaczają unikalny wielomian liniowy, czyli wielomian stopnia 1. W drugim opieraliśmy się na fakcie, że trzy punkty określają unikalny wielomian stopnia 2 lub kwadratowy. A jeśli chcesz wysłać wiadomość o długości 10, po prostu zakoduj wiadomość jako 10 współczynników funkcji wielomianu stopnia 9. Gdy masz swoją funkcję, oblicz 10 public y-wartości oceniając funkcję na wcześniej uzgodnionych 10 prywatnych x-wartości. Gdy to zrobisz, możesz bezpiecznie je przekazać y-współrzędne publicznie, aby odbiornik mógł je zdekodować. W praktyce kody Reeda-Solomona są nieco bardziej złożone i wykorzystują bardziej wyrafinowane rodzaje współczynników i schematów translacji, ale podstawowa idea jest taka sama.

Oprócz zapewnienia bezpieczeństwa wiadomości, kody Reeda-Solomona oferują również proste i skuteczne sposoby wychwytywania, a nawet poprawiania błędów. Jest to ważne za każdym razem, gdy dane są przesyłane lub przechowywane, ponieważ zawsze istnieje ryzyko, że niektóre informacje zostaną utracone lub uszkodzone.

Jednym z rozwiązań tego problemu byłoby po prostu wysłanie dodatkowych kopii danych. Na przykład Zeke może wysłać wiadomość [14, 14, 14, 15, 15, 15] zamiast [14, 15]. Dopóki Art wie, że każda część wiadomości jest wysyłana w trzech egzemplarzach, może ją odszyfrować i sprawdzić, czy nie ma błędów. W rzeczywistości, jeśli znajdzie jakieś błędy, ma duże szanse na ich poprawienie. Jeśli Art otrzyma [14, 14, 24, 15, 15, 15], fakt, że pierwsze trzy liczby są różne, ostrzega go o błędzie, a ponieważ dwie z nich to 14, może odgadnąć, że 24 powinno być prawdopodobnie 14 również. Zamiast prosić o ponowne wysłanie wiadomości, Art może kontynuować dekodowanie. To skuteczna, ale kosztowna strategia. Niezależnie od tego, ile czasu, energii i wysiłku wymaga wysłanie n fragmentów informacji, wymaga to trzy razy więcej.

Ale matematyka kryjąca się za kodami Reeda-Solomona oferuje skuteczną alternatywę. Zamiast wysyłać wiele kopii każdego fragmentu danych, możesz po prostu wysłać jeden dodatkowy punkt! Jeśli ten dodatkowy punkt pasuje do twojego wielomianu, informacja jest poprawna. Jeśli nie, wystąpił błąd.

Aby zobaczyć, jak to działa, załóżmy, że chcesz sprawdzić komunikat „NIE” w pierwszym przykładzie. Zeke może po prostu wysłać dodatkowe y-współrzędna 155. Zakładając, że on i Art zgodzili się na trzeciego szeregowego x-skoordynuj wcześniej, powiedzmy x = 10, Art może porównać ten trzeci punkt z linią, którą zdekodował. Kiedy się zatyka x = 10 do y = 14x + 15 i widzi, że wynik to 155, wie, że nie było błędów w transmisji.

To działa nie tylko w przypadku linii. Aby Zeke mógł sprawdzić „ZŁE” w drugim przykładzie, Art może wysłać y = 25. Jeśli zgodzili się, że 3 to dodatkowe prywatne x-współrzędne, Zeke może podłączyć x = 3 do jego funkcji kwadratowej y = 2x² + x + 4 i sprawdź, czy punkt (3, 25) pasuje, ponownie potwierdzając bezbłędną transmisję tylko jednym punktem więcej.

Ten dodatkowy punkt może również potencjalnie poprawić błędy. Jeśli zostanie wykryty błąd, a odbiorca nie może skonstruować funkcji wielomianu zawierającej wiadomość, może zamiast tego skonstruować „najlepiej dopasowany” wielomian przy użyciu technik regresji. Podobnie jak linia najlepszego dopasowania w klasie statystyki, jest to funkcja wielomianu, która jest matematycznie określona tak, aby jak najlepiej pasowała do danych punktów, nawet jeśli nie przechodzi przez nie wszystkie. W zależności od struktury wiadomości i ilości dodatkowych informacji, które wyślesz, ten najlepiej dopasowany wielomian może pomóc w zrekonstruowaniu prawidłowego wielomianu — a tym samym prawidłowej wiadomości — nawet na podstawie uszkodzonych informacji.

Ta skuteczność w przekazywaniu i korygowaniu komunikacji wyjaśnia, dlaczego NASA używała kodów Reeda-Solomona w swoich misjach na Księżyc i Marsa. I daje ci coś do rozważenia podczas rozwiązywania następnego układu równań. Jak zgadniesz, sprawdź lub wyeliminuj swoją drogę do rozwiązania, pomyśl o potędze i elegancji kodów Reeda-Solomona oraz o wszystkich tajemnicach, które może ujawnić Twój system.

ćwiczenia

1. Korzystając z tego samego schematu, którego używali w klasie, Art umieszcza publiczne numery 33 i 57, aby Zeke mógł je rozszyfrować. Jaka jest wiadomość?

2. Skąd Art i Zeke mogą być pewni, że układ równań wynikający z ich liczb prywatnych x = 3 i x = 6 zawsze będzie miało rozwiązanie?

3. W odpowiedzi na wiadomość Arta „ZŁE” o teście z angielskiego, Zeke odsyła [90, 387, 534]. Zakładając, że użyją tego samego schematu, którego używali na zajęciach, jakie jest jego przesłanie?

4. Lola wysyła ci dwuliterową wiadomość plus jeden numer sprawdzania błędów, używając kodu Reeda-Solomona i tego samego prostego szyfru alfabetycznego, którego używali Art i Zeke. Potajemnie zgodziłeś się na x-z góry koordynuje współrzędne 1, 3 i 10, a Lola podaje numery publiczne [27, 43, 90]. Czy wiadomość zawiera błąd?