Adott egy pontgyűjtemény a térben, találhat-e egy bizonyos típusú görbét, amely mindegyiken áthalad? Ez a kérdés – az úgynevezett interpolációs probléma egy változata – az ókor óta foglalkoztatja a matematikusokat. Az év elején a matematikusok Eric Larson és a Isabel Vogt teljesen megoldotta.
De míg a munka sok izgalmat keltett a tiszta matematikusok körében, az interpoláció gyakorlati következményekkel jár, amelyek messze túlmutatnak a geometria területén. Az interpoláció központi szerepet játszik az elektronikus adatok tárolásában és továbbításában, kriptográfiai sémák felépítésében és még sok másban. Emiatt megkarcolhatja a CD-t, és még mindig hallhat zenét, vagy beszennyezheti a QR-kódot, és továbbra is beolvassa. Ez az oka annak, hogy az olyan űrmissziók, mint a Voyager program, tiszta digitális képeket küldhetnek vissza a Földre. Ez az oka annak, hogy egy számítógépcsoport akkor is képes összetett számítást végrehajtani, ha az egyik számítógép meghibásodik.
Ezek az alkalmazások mind az interpoláció feltűnően szép és fogalmilag egyszerű használatán alapulnak: az úgynevezett Reed-Solomon kódokon és a rájuk épülő kódokon.
Pontról Pontra
Tegyük fel, hogy két számból álló üzenetet szeretne küldeni: 2 és 7. Lehetséges, hogy a továbbított adatok egy része elveszik vagy megsérül – a 2 például –2-re vált át. Így ahelyett, hogy egyszerűen elküldené az adatokat, hozzáadhat további információkat, amelyek segítenek a címzettnek azonosítani és kijavítani az esetlegesen felmerülő hibákat. Ezt hívják hibajavító kódnak.
Az ilyen kód legegyszerűbb példája ugyanazt az üzenetet többszörösen továbbítja. Annak érdekében, hogy a címzett azonosíthassa, történt-e hiba, küldje el ugyanazt az üzenetet kétszer: 2, 7, 2, 7. Ha a megfelelő pozícióban lévő számok nem egyeznek (például ha az átvitel helyett 2, 7, -2, 7), a címzett tudni fogja, hogy az egyik téved – de azt nem, hogy melyik. Annak érdekében, hogy rájöjjenek és kijavítsák a hibát, küldje el ugyanazt az üzenetet háromszor: 2, 7, 2, 7, 2, 7. A címzettnek egyszerűen többségi szavazattal kell kitalálnia a kívánt üzenetet.
De ez a hibajavítási módszer vadul nem hatékony. Íme egy intelligensebb megközelítés: Kódolja az üzenetet görbeként, és csak annyi információt küldjön el, hogy a címzett képes legyen rekonstruálni a görbét.
A mi egyszerű esetünkben, amikor a 2-t és a 7-et adjuk, a görbe a vonal lenne y = 2x + 7. Értékelje ezt a görbét két előre meghatározott értékkel x, és továbbítsa az eredményt y-értékek. A címzettnek most két pontja van, és mivel az interpolációs probléma azt mondja, hogy két pont határoz meg egy egyedi egyenest, a címzettnek egyszerűen meg kell találnia azt az egyenest, amely átmegy a kapott pontokon. A sor együtthatói felfedik a szándékolt üzenetet.
A hibák elkerülése érdekében ismételten adjon hozzá további információkat. Tessék, elküldöd a y-érték, amely egy másik előre meghatározott értéknek felel meg x-koordináta. Ha a három pont nem esik ugyanarra az egyenesre, akkor hiba van. És hogy megtudja, hol van a hiba, csak küldjön még egy értéket – vagyis összesen négy számot küldött az előző módszer által előírt hat helyett.
Az előny az üzenet méretével nő. Tegyük fel, hogy hosszabb üzenetet szeretne küldeni – 1,000 számot. A kevésbé hatékony kódhoz 2,000 szám küldése lenne szükséges a hiba azonosításához, és 3,000 szám kijavításához. De ha azt a kódot használja, amely egy polinom adott pontokon történő interpolációját foglalja magában, akkor csak 1,001 számra van szüksége a hiba megtalálásához, és 1,002 számra a javításhoz. (További pontokat adhat hozzá a lehetséges hibák azonosításához és kijavításához.) Az üzenet hosszának növekedésével a két kód közötti hatékonyságbeli különbség nő.
A hatékonyabb kódot Reed-Solomon kódnak nevezik. 1960-as bevezetése óta a matematikusok további áttöréseket értek el, és olyan algoritmusokat fejlesztettek ki, amelyek több hibát képesek nagyobb hatékonysággal kijavítani. „Nagyon elegáns, tiszta, konkrét” – mondta Swastik Kopparty, matematikus és informatikus a Torontói Egyetemen. – Fél óra alatt meg lehet tanítani egy másodéves egyetemista.
A Reed-Solomon kódok különösen hasznosak voltak az információk elektronikus tárolására és továbbítására. Ugyanez a koncepció azonban elengedhetetlen volt a kriptográfiában és az elosztott számítástechnikában is.
Vegyük a titkos megosztást: Tegyük fel, hogy egy titkot szeretne elosztani több fél között úgy, hogy senki sem férhet hozzá a teljes titokhoz, de együtt igen. (Képzeljünk el például egy titkosítási kulcsot vagy egy rakétakilövő kódot.) Kódolja a számokat egy polinomba, kiértékeli azt a polinomot egy előre meghatározott pontkészleten, és az eredményeket kiosztja egy másik személynek.
Legutóbb a Reed-Solomon kódokat olyan területeken alkalmazták, mint a számítási felhő és a blokklánc technológia. Tegyük fel, hogy olyan számítást kell futtatnia, amely túl bonyolult a laptop számára, ezért egy nagy számítási fürttel kell futtatnia – de most ellenőriznie kell, hogy a kapott számítás helyes-e. A Reed-Solomon kódok lehetővé teszik olyan további információk kérését, amelyeket a fürt valószínűleg nem tud előállítani, ha nem végezte el megfelelően a számítást. „Ez varázslatosan működik” – mondta Jade Nardi, a franciaországi Rennes-i Matematikai Intézet tudományos munkatársa. "Ez a folyamat valóban csodálatos, és az, ahogyan [ezekre a kódokra] támaszkodik, feldobja a fejemet."
De a Reed-Solomon kódoknak van egy fontos korlátja is. Úgy vannak megszerkesztve, hogy a polinomot csak rögzített (és általában viszonylag kicsi) értékkészlettel tudja kiértékelni. Ez azt jelenti, hogy az üzenet kódolásához csak egy bizonyos számkészletet használhat. Ennek a halmaznak vagy az ábécének a mérete viszont korlátozza az elküldhető üzenetek hosszát – és minél nagyobbra próbálja összeállítani az ábécét, annál nagyobb számítási teljesítményre lesz szüksége az üzenetek dekódolásához.
Így a matematikusok egy még optimálisabb kódot kerestek.
Jövő kódjai
Egy általánosabb, erősebb kód lehetővé teszi, hogy hosszabb üzeneteket tároljon vagy küldjön anélkül, hogy növelnie kellene az ábécé méretét. Ehhez a matematikusok olyan kódokat dolgoztak ki, amelyek magukban foglalják egy függvény - amely egy bonyolultabb görbéhez kapcsolódó speciális térben él - interpolációját a görbe adott pontjain keresztül. Ezek az úgynevezett algebrai geometriai kódok „a semmiből jöttek elő, és jobbak, mint bármely más kód, amit tudunk [kisebb ábécével] készíteni” – mondta Kopparty. „Ez mindent felülmúl. Igazi sokk volt.”
Csak egy probléma van. A gyakorlatban egy Reed-Solomon kód megvalósítása sokkal, de sokkal egyszerűbb, mint egy algebrai geometriai kód megvalósítása. "Ez a legkorszerűbb, de még vizsgálat alatt áll, hogy valóban praktikussá váljon" - mondta a kriptológus. Simon Abelard. "Elég absztrakt matematikát foglal magában, és nehéz ezeket a kódokat számítógépen kezelni."
Egyelőre ez nem aggasztó: a valós alkalmazásokban a Reed-Solomon kódok és a kapcsolódó hibajavítási formák elegendőek. De lehet, hogy ez nem mindig van így. Például, ha nagy teljesítményű kvantumszámítógépek válnak elérhetővé a jövőben, képesek lesznek rá megtörni a mai kriptográfiai protokollokat. Ennek eredményeként a kutatók olyan sémákat kerestek, amelyek képesek ellenállni a kvantumtámadásoknak. Az ilyen sémák egyik legjobb versenyzőjének valami erősebbre lenne szüksége, mint a Reed-Solomon kód. Az algebrai geometriai kódok bizonyos verziói működhetnek. Más kutatók reménykednek abban, hogy az algebrai geometriai kódok milyen szerepet játszhatnak a számítási felhőben.
De még ilyen lehetséges felhasználások hiányában is „a matematika történetében néha új dolgokat fedezünk fel, amelyekre manapság már tényleg nincs alkalmazás” – mondta. Elena Berardini, a holland Eindhoveni Műszaki Egyetem kutatója, aki algebrai geometriai kódokkal dolgozik. „De aztán 50 év elteltével rájössz, hogy valami teljesen váratlan dologra hasznos lehet” – akárcsak maga az interpoláció ősi problémája.
