Põhialgebra salakoodide ja kosmosekommunikatsiooni taga

Kosmoseuuringud nõuavad tohutut täpsust. Kui maandute kulguriga Marsile 70 miljoni miili kaugusel lähimast teenindusjaamast, peate maksimeerima tõhusust ja valmistuma ootamatusteks. See kehtib kõige kohta alates kosmoseaparaadi projekteerimisest kuni andmeedastuseni: need sõnumid, mis naasevad Maale 0-de ja 1-de pideva voona, sisaldavad kindlasti mõningaid vigu, seega peate suutma need tuvastada ja parandada ilma väärtuslikku aega ja energiat raiskamata.

Siin tulebki mängu matemaatika. Matemaatikud on leiutanud leidlikke viise teabe edastamiseks ja salvestamiseks. Kasutatakse üht üllatavalt tõhusat meetodit Reed-Saalomoni koodid, mis on üles ehitatud samale algebrale, mida õpilased koolis õpivad. Lähme matemaatikatundi, et näha, kuidas Reed-Solomoni koodid aitavad teavet edastada ja kaitsta, parandades samal ajal ilmnevaid kulukaid vigu.

Kaks õpilast, Art ja Zeke, vahetavad pr Al-Jabri matemaatikatunnis salasõnumeid. Art avab Zeke'i viimase noodi, et paljastada numbrid 57 ja 99. Ta teab, et peab andma x-koordinaadid 3 ja 6 punktide (3, 57) ja (6, 99) loomiseks. Kunst ühendab iga punkti lineaarsesse võrrandisse y = Ax + B ja loob järgmise võrrandisüsteemi:

57 = 3A + B

99 = 6A + B

Sõnumi dekodeerimiseks peab Kunst lahendama A ja B. Ta alustab esimese võrrandi lahutamisega teisest:

See välistab B. Selle uue võrrandi mõlema poole jagamine 3-ga näitab Artile seda A = 14 ja seejärel asendades selle tagasi esimese võrrandiga, 57 = 3 × 14 + B, annab B = 15.

Kunst teab nüüd, et joont, mis läbib (3, 57) ja (6, 99), kirjeldatakse võrrandiga y = 14x + 15. Kuid ta teab ka, et Reed-Saalomoni koodis on salasõnum peidus koefitsientide sees. Ta dekodeerib Zeke'i sõnumi, kasutades nende lihtsat kokkulepitud tähestiku šifrit: 14 on "N" ja 15 on "O", mis ütleb Artile, et ei, Zeke ei saa täna pärast kooli videomänge mängida.

Selle lihtsa Reed-Solomoni koodi saladus algab kahest geomeetria põhitõest. Esiteks, mis tahes kahe punkti kaudu kulgeb kordumatu joon. Teiseks koefitsientide jaoks A ja B, vormi saab kirjutada iga (mittevertikaalse) rea y = Ax + B. Need kaks fakti koos tagavad, et kui teate joone kahte punkti, võite leida A ja B, ja kui tead A ja B, teate kõiki joone punkte. Lühidalt, kummagi teabekogumi omamine on samaväärne rea tundmisega.

Reed-Solomoni koodid kasutavad neid samaväärseid teabekogumeid. Salasõnum on kodeeritud koefitsientidena A ja B, ja liini punktid jagatakse tükkideks, millest osa edastatakse avalikult ja osa jääb privaatseks. Sõnumi dekodeerimiseks koguge tükid kokku ja pange need uuesti kokku. Ja kõik, mida see nõuab, on lihtne algebra.

Zeke tükid olid numbrid 57 ja 99, mille ta saatis Art. Need numbrid on sõnumi avalik osa. Kunst pani need kokku oma tükkidega 3 ja 6, et rekonstrueerida punktid (3, 57) ja (6, 99). Siin moodustavad 3 ja 6 sõnumi privaatse osa, mille Art ja Zeke eelnevalt kokku leppisid.

Need kaks punkti asuvad joonel ja sõnumi dekodeerimiseks peate lihtsalt leidma selle joone võrrandi. Iga punkti ühendamine y = Ax + B annab teile sirge kohta kahe võrrandi süsteemi, mis mõlemad peavad olema tõesed. Nüüd on strateegia sirgjooneline: lahendage süsteem, määrake rida ja dekodeerige sõnum.

Algebra tunnis õppisite ilmselt paljusid võrrandisüsteemide lahendamise meetodeid, nagu graafiku koostamine, arvamine ja kontrollimine ning asendamine. Kunstis kasutati elimineerimist, meetodit, mille käigus manipuleerite võrranditega algebraliselt, et muutujad ükshaaval kõrvaldada. Iga kord, kui muutuja kõrvaldate, muutub süsteemi lahendamine veidi lihtsamaks.

Nagu ka teiste krüpteerimisskeemide puhul, on see avaliku ja privaatse teabe nutikas kombinatsioon, mis hoiab sõnumid turvalisena. Zeke võiks karjuda oma numbreid 57 ja 99 üle klassiruumi ning see ei ohustaks tema Artile saadetud sõnumi turvalisust (kuigi see võib teda pr. Al-Jabriga segadusse ajada). Seda seetõttu, et ilma vastava privaatse teabeta x-koordinaadid 3 ja 6 — sirge võrrandit on võimatu tuvastada. Kuni nad hoiavad neid väärtusi enda teada, võivad nad oma salasõnumeid julgelt avalikult edastada.

Rida y = 14x + 15 sobib kahetähelise sõna "ei" edastamiseks, aga mis siis, kui õpilased tahavad pikemat saladust jagada? Siin tuleb mängu algebra, geomeetria ja lineaarvõrrandisüsteemide kogu võimsus.

Oletame, et Zeke tahab teada, kuidas Art arvab, et tal läheb homsel inglise keele testil. Art teisendab oma kolmetähelise vastuse numbriteks 14, 59 ja 82 ning edastab need Zekele. Õpilased leppisid eelnevalt kokku, et kui kasutada Reed-Solomoni koode pikkusega 3, on nende privaatnumbrid 2, 5 ja 6, mistõttu Zeke paneb tükid kokku, et rekonstrueerida punktid (2, 14), (5, 59) ja (6, 82).

Nüüd ei ole ühtegi lineaarset funktsiooni, mis läbiks neid kolme punkti. Kuid on olemas ainulaadne ruutfunktsioon, mis seda teeb. Ja kuna iga ruutfunktsiooni saab vormile kirjutada y = Ax² + Bx + C, saab rakendada sama üldist meetodit. Ainus erinevus on süsteemi suuruses.

Iga punkti ühendamine y = Ax² + Bx + C annab ühe võrrandi, nii et kolm punkti annavad järgmise kolme võrrandi süsteemi:

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

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

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

Kolmest võrrandist koosneva kolme tundmatuga võrrandisüsteemi lahendamiseks on vaja veidi rohkem tööd kui kahe tundmatuga võrrandisüsteemi puhul, kuid eesmärk on sama: muutujate kõrvaldamiseks kombineerige nutikalt võrrandipaare.

Näiteks kui lahutate esimese võrrandi teisest, saate uue võrrandi 45 = 21A + 3B. Samamoodi, kui lahutate teise võrrandi kolmandast, saate 23 = 11A + B. Need algebralised manipulatsioonid loovad uue süsteemi:

45 = 21A + 3B

23 = 11A + B

Nüüd on teil süsteem "kaks-kaks": kaks võrrandit kahe tundmatuga. Selle lahendamiseks saate korrutada teise võrrandi -3-ga ja lisada selle esimesele võrrandile:

Pange tähele, kuidas korduv elimineerimine on muutnud algse kolme võrrandi süsteemi üheks võrrandiks, mida saab hõlpsasti lahendada: A = 2. Tagurpidi töötades saate ühendada A = 2 ühte süsteemi kaks korda kahe võrrandisse, et leida B = 1 ja seejärel ühendage mõlemad väärtused saamiseks ühte algvõrranditest C = 4. Pärast lihtsa tähestiku šifri kasutamist numbrite 2, 1 ja 4 juures teab Zeke, et Art teeb homses inglise keele testis "HALB"-i. Vähemalt saab ta palju algebrat harjutada.

Tänu polünoomfunktsioonide erilisele faktile saate Reed-Solomoni koodide abil edastada mis tahes pikkusega teate. Võti on järgmine: arvestades mis tahes n punktid tasapinnas erinevate x-koordinaadid, on ainulaadne "kraadi" polünoom n − 1, mis neid läbib. Polünoomi aste on avaldises oleva muutuja suurim võimsus, seega ruutfunktsiooni moodi Ax² + Bx + C on aste 2, kuna kõrgeim võimsus x on 2. Ja lineaarfunktsiooni aste on 1, kuna võrrandis y = Ax + B, suurim võimsus x on 1.

Esimeses näites kasutasime asjaolu, et kaks punkti määravad unikaalse lineaarse ehk 1. astme polünoomi. Teises toetusime asjaolule, et kolm punkti määravad unikaalse 2. astme ehk ruutpolünoomi. Ja kui soovite saata sõnumi pikkusega 10, siis lihtsalt kodeerige sõnum 10-kraadise polünoomifunktsiooni 9 koefitsiendina. Kui olete oma funktsiooni saanud, arvutage 10 avalikkust y-väärtused, hinnates funktsiooni eelnevalt kokkulepitud 10 privaatsel x-väärtused. Kui olete seda teinud, saate neist ohutult mööda minna y-koordinaadid avalikult, et teie vastuvõtja saaks dekodeerida. Praktikas on Reed-Solomoni koodid sellest pisut keerukamad, kasutades keerukamaid koefitsiente ja tõlkeskeeme, kuid põhiidee on sama.

Lisaks sõnumi turvalisusele pakuvad Reed-Solomoni koodid ka lihtsaid ja tõhusaid viise vigade tabamiseks ja isegi parandamiseks. See on oluline igal ajal, kui andmeid edastatakse või salvestatakse, kuna alati on võimalus, et osa teabest läheb kaotsi või rikutakse.

Üks lahendus sellele probleemile oleks lihtsalt andmete lisakoopiate saatmine. Näiteks võib Zeke saata sõnumi [14, 14, 14, 15, 15, 15], mitte [14, 15]. Kuni Art teab, et iga sõnumi osa saadetakse kolmes eksemplaris, saab ta sõnumi dekodeerida ja vigu kontrollida. Tegelikult, kui ta leiab vigu, on tal hea võimalus need parandada. Kui Art saab [14, 14, 24, 15, 15, 15], hoiatab asjaolu, et kolm esimest numbrit on erinevad, teda veast ja kuna kaks neist on 14, võib ta arvata, et 24 peaks tõenäoliselt olema 14 samuti. Selle asemel, et paluda sõnumi tagasisaatmist, võib Art jätkata oma dekodeerimist. See on tõhus, kuid kulukas strateegia. Ükskõik, mis aega, energiat ja vaeva saatmine nõuab n osa teabest, nõuab see kolm korda rohkem.

Kuid Reed-Solomoni koodide taga olev matemaatika pakub tõhusat alternatiivi. Selle asemel, et saata igast andmetest mitu koopiat, võite saata lihtsalt ühe lisapunkti! Kui see lisapunkt sobib teie polünoomiga, on teave õige. Kui ei, siis on tekkinud viga.

Et näha, kuidas see toimib, oletame, et soovite kontrollida esimeses näites olevat teadet "EI". Zeke saab lihtsalt lisa saata y-koordinaat 155. Eeldades, et tema ja Art leppisid kokku kolmandas reamehes x-koordineerige eelnevalt, ütleme x = 10, Art saab seda kolmandat punkti kontrollida reaga, mille ta dekodeeris. Kui ta ühendab x = 10 sisse y = 14x + 15 ja näeb, et tulemus on 155, ta teab, et edastusvigu ei olnud.

See ei tööta ainult liinide puhul. Et Zeke saaks teises näites „BAD” kontrollida, saab Art saata y = 25. Kui nad on kokku leppinud, et 3 on ekstra privaatne x-koordinaat, Zeke saab ühendada x = 3 tema ruutfunktsiooni y = 2x² + x + 4 ja veenduge, et punkt (3, 25) sobib, kinnitades taas veavaba edastuse vaid ühe punktiga.

Ja see lisapunkt võib potentsiaalselt parandada ka vigu. Kui tuvastatakse viga ja vastuvõtja ei saa konstrueerida sõnumit sisaldavat polünoomifunktsiooni, saab ta selle asemel regressioonitehnikaid kasutades konstrueerida „kõige sobivama” polünoomi. Nagu statistikaklassis kõige paremini sobiv rida, on see polünoomfunktsioon, mis on matemaatiliselt määratud nii, et see sobiks antud punktidega kõige paremini, isegi kui see ei läbi neid kõiki. Olenevalt sõnumi struktuurist ja sellest, kui palju lisateavet saadate, võib see kõige sobivam polünoom aidata teil rekonstrueerida õige polünoomi – ja seega ka õige sõnumi – isegi rikutud teabe põhjal.

See side edastamise ja parandamise tõhusus selgitab, miks NASA on kasutanud Reed-Solomoni koode oma missioonidel Kuule ja Marsile. Ja see annab teile, mille üle järele mõelda, kui lahendate oma järgmise võrrandisüsteemi. Kui arvate, kontrollige või kõrvaldage oma tee lahenduseni, mõelge Reed-Solomoni koodide jõule ja elegantsile ning kõikidele saladustele, mida teie süsteem võib paljastada.

Harjutused

1. Kasutades sama skeemi, mida nad klassis kasutasid, postitab Art Zeke'ile dekodeerimiseks avalikud numbrid 33 ja 57. Mis on sõnum?

2. Kuidas saavad Art ja Zeke olla kindlad, et võrrandisüsteem, mis tuleneb nende privaatarvudest x = 3 ja x = 6-l on alati lahendus?

3. Vastuseks Arti sõnumile “BAD” inglise keele testi kohta saadab Zeke tagasi [90, 387, 534]. Kui eeldada, et nad kasutavad sama skeemi, mida nad klassis kasutasid, siis milline on tema sõnum?

4. Lola saadab sulle kahetähelise sõnumi pluss ühe veakontrolli numbri, kasutades Reed-Solomoni koodi ja sama lihtsat tähestiku šifrit, mida kasutavad Art ja Zeke. Olete salaja kokku leppinud x-koordinaadid 1, 3 ja 10 ette ning Lola edastab avalikud numbrid [27, 43, 90]. Kas teade sisaldab viga?