Mając zbiór punktów w przestrzeni, czy możesz znaleźć pewien rodzaj krzywej, która przechodzi przez wszystkie z nich? To pytanie — wersja tego, co nazywamy problemem interpolacji — interesuje matematyków od starożytności. Na początku tego roku matematycy Erica Larsona i Izabela Vogt rozwiązałem to całkowicie.
Ale chociaż praca ta wywołała wiele emocji wśród czystych matematyków, interpolacja ma praktyczne konsekwencje, które wykraczają daleko poza dziedzinę geometrii. Interpolacja ma kluczowe znaczenie dla przechowywania i przesyłania danych elektronicznych, konstruowania schematów kryptograficznych i nie tylko. Dlatego możesz zdrapać płytę CD i nadal słuchać muzyki lub zabrudzić kod QR i nadal go skanować. To dlatego misje kosmiczne, takie jak program Voyager, mogą wysyłać na Ziemię wyraźne obrazy cyfrowe. Dlatego klaster komputerów może wykonywać złożone obliczenia, nawet jeśli jeden z tych komputerów działa nieprawidłowo.
Wszystkie te aplikacje opierają się na uderzająco pięknym i koncepcyjnie prostym użyciu interpolacji: tak zwanych kodach Reeda-Solomona i kodach, które na nich bazują.
Punkt po punkcie
Załóżmy, że chcesz wysłać wiadomość składającą się z dwóch cyfr: 2 i 7. Możliwe, że niektóre przesyłane dane zostaną utracone lub uszkodzone — na przykład cyfra 2 może zmienić się na -2. Więc zamiast po prostu wysyłać dane, możesz dodać dodatkowe informacje, które pomogą odbiorcy zidentyfikować i naprawić błędy, które mogą się pojawić. To się nazywa kod korygujący błędy.
Najprostszy przykład takiego kodu polega na wielokrotnym przesyłaniu tej samej wiadomości. Aby umożliwić odbiorcy zidentyfikowanie, czy wystąpił błąd, wyślij tę samą wiadomość dwa razy: 2, 7, 2, 7. Jeśli liczby na odpowiednich pozycjach nie zgadzają się (powiedzmy, jeśli zamiast tego transmisja brzmi 2, 7, -2, 7), odbiorca będzie wiedział, że jeden z nich jest błędny — ale nie który. Aby pozwolić im to rozgryźć i poprawić błąd, wyślij tę samą wiadomość trzy razy: 2, 7, 2, 7, 2, 7. Odbiorca musi po prostu wziąć większość głosów, aby dowiedzieć się, zamierzoną wiadomość.
Ale ten sposób poprawiania błędów jest szalenie nieefektywny. Oto mądrzejsze podejście: zakoduj wiadomość jako krzywą i wyślij tylko tyle informacji, aby odbiorca mógł zrekonstruować tę krzywą.
W naszym prostym przypadku przesyłania 2 i 7 krzywa byłaby linią y = 2x + 7. Oceń tę krzywą przy dwóch z góry określonych wartościach x, i przekaż wynikowy y-wartości. Odbiorca ma teraz dwa punkty, a ponieważ problem interpolacji mówi nam, że dwa punkty określają unikalną linię, odbiorca musi po prostu znaleźć linię, która przechodzi przez otrzymane punkty. Współczynniki linii ujawniają zamierzony komunikat.
Aby uniknąć błędów, ponownie dodajesz dodatkowe informacje. Tutaj wysyłasz y-wartość, która odpowiada innej z góry określonej x-koordynować. Jeśli trzy punkty nie leżą na tej samej linii, wystąpił błąd. Aby dowiedzieć się, gdzie jest błąd, po prostu wysyłasz jeszcze jedną wartość — co oznacza, że wysłałeś łącznie cztery liczby, a nie sześć wymaganych przez poprzednią metodę.
Przewaga rośnie wraz z rozmiarem wiadomości. Załóżmy, że chcesz wysłać dłuższą wiadomość — 1,000 numerów. Mniej wydajny kod wymagałby wysłania 2,000 numerów w celu zidentyfikowania błędu i 3,000 w celu jego poprawienia. Ale jeśli użyjesz kodu, który polega na interpolacji wielomianu przez podane punkty, potrzebujesz tylko 1,001 liczb, aby znaleźć błąd i 1,002, aby go poprawić. (Możesz dodać więcej punktów, aby zidentyfikować i poprawić więcej potencjalnych błędów). Wraz ze wzrostem długości wiadomości różnica w wydajności między dwoma kodami staje się coraz bardziej wyraźna.
Bardziej wydajny kod nazywa się kodem Reeda-Solomona. Od czasu jego wprowadzenia w 1960 r. matematycy dokonali kolejnych przełomów, opracowując algorytmy, które mogą korygować więcej błędów z większą wydajnością. „Jest bardzo elegancki, czysty, betonowy” – powiedział Swastyk Kopparty, matematyk i informatyk na Uniwersytecie w Toronto. „Można go nauczyć studenta drugiego roku w pół godziny”.
Kody Reed-Solomon są szczególnie przydatne do przechowywania i przesyłania informacji drogą elektroniczną. Ale ta sama koncepcja była również niezbędna w kryptografii i obliczeniach rozproszonych.
Weź udział w udostępnianiu sekretu: Załóżmy, że chcesz rozdzielić sekret wśród kilku stron, tak aby żadna osoba nie miała dostępu do całego sekretu, ale razem mogą. (Wyobraźmy sobie na przykład klucz szyfrujący lub kod wystrzelenia rakiety). Kodujesz liczby w wielomianu, oceniasz ten wielomian we wcześniej określonym zestawie punktów i przekazujesz każdy z wyników innej osobie.
Ostatnio kody Reed-Solomon zostały wykorzystane w obszarach takich jak przetwarzanie w chmurze i technologia blockchain. Załóżmy, że musisz wykonać obliczenia, które są zbyt skomplikowane dla twojego laptopa, więc masz duży klaster obliczeniowy, aby je uruchomić — ale teraz musisz sprawdzić, czy otrzymane obliczenia są poprawne. Kody Reeda-Solomona pozwalają poprosić o dodatkowe informacje, których klaster prawdopodobnie nie będzie w stanie wygenerować, jeśli nie wykona poprawnie obliczeń. „To działa magicznie” – powiedział Jadeit Nardi, pracownik naukowy w Instytucie Matematyki w Rennes we Francji. „Ten proces jest naprawdę wspaniały, a sposób, w jaki opiera się na [tych kodach], oszałamia mnie”.
Ale kodeksy Reeda-Solomona mają również ważne ograniczenie. Są one skonstruowane w taki sposób, że możesz ocenić swój wielomian tylko przy ustalonym (i zwykle stosunkowo małym) zestawie wartości. Oznacza to, że do zakodowania wiadomości możesz używać określonego zestawu cyfr. Rozmiar tego zestawu lub alfabetu z kolei ogranicza długość wiadomości, które możesz wysłać – a im większy spróbujesz stworzyć swój alfabet, tym więcej mocy obliczeniowej będziesz potrzebować do odszyfrowania tych wiadomości.
Dlatego matematycy szukali jeszcze bardziej optymalnego kodu.
Przyszłe kody
Bardziej ogólny, potężniejszy kod umożliwiłby przechowywanie lub wysyłanie dłuższych wiadomości bez konieczności zwiększania rozmiaru alfabetu. W tym celu matematycy opracowali kody, które polegają na interpolacji funkcji — która żyje w specjalnej przestrzeni związanej z bardziej skomplikowaną krzywą — przez określone punkty na tej krzywej. Te tak zwane kody geometrii algebraicznej „powstały znikąd i są lepsze niż jakikolwiek inny kod, który znamy [przy użyciu mniejszego alfabetu]”, powiedział Kopparty. „To bije na głowę wszystko. To był prawdziwy szok”.
Jest tylko jeden problem. W praktyce implementacja kodu Reeda-Solomona jest o wiele łatwiejsza niż implementacja kodu geometrii algebraicznej. „Jest to najnowocześniejszy, ale wciąż trwają badania, aby naprawdę przekształcić się w coś praktycznego” – powiedział kryptolog Szymon Abelard. „Zawiera dość abstrakcyjną matematykę i trudno jest obsługiwać te kody na komputerze”.
Na razie nie jest to niepokojące: w rzeczywistych zastosowaniach wystarczą kody Reed-Solomon i powiązane formy korekcji błędów. Ale nie zawsze tak jest. Na przykład, jeśli w przyszłości pojawią się potężne komputery kwantowe, będą mogły: złamać dzisiejsze protokoły kryptograficzne. W rezultacie naukowcy szukali schematów, które mogą oprzeć się atakom kwantowym. Jeden z czołowych pretendentów do takich systemów wymagałby czegoś silniejszego niż kody Reeda-Solomona. Niektóre wersje kodów geometrii algebraicznej mogą po prostu działać. Inni badacze mają nadzieję, że kody geometrii algebraicznej mogą odgrywać rolę w przetwarzaniu w chmurze.
Ale nawet przy braku takich potencjalnych zastosowań „w historii matematyki czasami odkrywa się nowe rzeczy, które w dzisiejszych czasach tak naprawdę nie mają zastosowania” – powiedział. Elena Berardini, naukowiec z Eindhoven University of Technology w Holandii, który pracuje nad kodami geometrii algebraicznej. „Ale potem po 50 latach okazuje się, że może to być przydatne w czymś zupełnie nieoczekiwanym” — tak jak starożytny problem samej interpolacji.
