Den grunnleggende algebraen bak hemmelige koder og romkommunikasjon

Romutforskning krever enorm presisjon. Når du lander en rover på Mars 70 millioner miles unna nærmeste bensinstasjon, må du maksimere effektiviteten og forberede deg på det uventede. Dette gjelder alt fra romfartøydesign til dataoverføring: Disse meldingene som returnerer til Jorden som en jevn strøm av 0-er og 1-ere, er nødt til å inneholde noen feil, så du må kunne identifisere og korrigere dem uten å kaste bort dyrebar tid og energi.

Det er her matematikk kommer inn. Matematikere har funnet opp geniale måter å overføre og lagre informasjon på. En overraskende effektiv metode bruker Reed-Solomon-koder, som er bygget på den samme grunnleggende algebraen som elevene lærer på skolen. La oss ta en mattetime for å se hvordan Reed-Solomon-koder hjelper til med å overføre og sikre informasjon samtidig som de retter opp kostbare feil som dukker opp.

To elever, Art og Zeke, utveksler hemmelige meldinger i mattetimen til Al-Jabr. Art bretter ut Zekes siste notat for å avsløre tallene 57 og 99. Han vet at han må levere x-koordinater 3 og 6 for å lage punktene (3, 57) og (6, 99). Kunst kobler hvert punkt inn i den lineære ligningen y = Ax + B og produserer følgende ligningssystem:

57 = 3A + B

99 = 6A + B

For å dekode budskapet må Art løse for A og B. Han starter med å trekke den første ligningen fra den andre:

Dette eliminerer B. Å dele begge sider av denne nye ligningen med 3 forteller Art det A = 14, og deretter erstatte dette tilbake i den første ligningen, 57 = 3 × 14 + B, gir B = 15.

Kunsten vet nå at linjen som går gjennom (3, 57) og (6, 99) er beskrevet av ligningen y = 14x + 15. Men han vet også at i en Reed-Solomon-kode skjuler den hemmelige beskjeden seg i koeffisientene. Han dekoder Zekes melding ved å bruke deres enkle avtalte alfabetchiffer: 14 er "N" og 15 er "O", som forteller Art at, nei, Zeke kan ikke spille videospill etter skolen i dag.

Hemmeligheten bak denne enkle Reed-Solomon-koden starter med to grunnleggende geometrifakta. For det første, gjennom to punkter er det en unik linje. For det andre for koeffisienter A og B, hver (ikke-vertikal) linje kan skrives i skjemaet y = Ax + B. Sammen garanterer disse to fakta at hvis du kjenner to punkter på en linje kan du finne A og B, og hvis du vet A og B, du kjenner alle punktene på linjen. Kort sagt, å ha et sett med informasjon tilsvarer å kjenne linjen.

Reed-Solomon-koder utnytter disse tilsvarende settene med informasjon. Den hemmelige meldingen er kodet som koeffisientene A og B, og linjens punkter er delt opp i biter, hvorav noen blir overført offentlig, og noen holdes private. For å dekode meldingen, samler du bare bitene og setter dem sammen igjen. Og alt dette krever er en enkel algebra.

Zekes brikker var tallene 57 og 99, som han sendte til Art. Disse tallene er den offentlige delen av meldingen. Art satte disse sammen med sine egne stykker, 3 og 6, for å rekonstruere punktene (3, 57) og (6, 99). Her utgjør 3 og 6 den private delen av meldingen, som Art og Zeke ble enige om på forhånd.

De to punktene ligger på en linje, og for å dekode meldingen trenger du bare å finne den linjens ligning. Kobler hvert punkt inn i y = Ax + B gir deg et system med to ligninger om linjen som begge må være sanne. Nå er strategien grei: Løs systemet, bestem linjen og dekod meldingen.

I algebratimen lærte du sannsynligvis mange metoder for å løse likningssystemer, som å tegne grafer, gjette og sjekke, og substitusjon. Art used elimination, en metode der du manipulerer likningene algebraisk for å eliminere variablene én om gangen. Hver gang du eliminerer en variabel, blir systemet litt lettere å løse.

Som med andre krypteringssystemer, er det den smarte kombinasjonen av offentlig og privat informasjon som holder meldinger sikre. Zeke kunne rope numrene 57 og 99 over hele klasserommet, og det ville ikke sette sikkerheten til meldingen hans til Art i fare (selv om det kan få ham i problemer med Al-Jabr). Det er fordi uten den tilsvarende private informasjonen - x-koordinater 3 og 6 — det er umulig å identifisere linjens ligning. Så lenge de holder disse verdiene for seg selv, kan de trygt gi sine hemmelige meldinger offentlig.

Linjen y = 14x + 15 er greit for å overføre ordet «nei» på to bokstaver, men hva om elevene vil dele en lengre hemmelighet? Det er her den fulle kraften til algebra, geometri og systemer av lineære ligninger kommer inn i bildet.

Anta at Zeke vil vite hvordan Art tror han vil klare seg på morgendagens engelskprøve. Art konverterer svaret på tre bokstaver til tallene 14, 59 og 82 og gir dem videre til Zeke. Elevene var på forhånd enige om at når de bruker Reed-Solomon-koder med lengde 3, er deres private tall 2, 5 og 6, så Zeke setter sammen bitene for å rekonstruere punktene (2, 14), (5, 59) og (6, 82).

Nå er det ingen lineær funksjon som går gjennom disse tre punktene. Men det er en unik kvadratisk funksjon som gjør det. Og siden hver andregradsfunksjon kan skrives i formen y = Ax² + Bx + C, kan den samme generelle metoden brukes. Den eneste forskjellen er størrelsen på systemet.

Kobler hvert punkt inn i y = Ax² + Bx + C gir én ligning, så de tre punktene produserer følgende system med tre ligninger:

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

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

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

Et system med tre ligninger med tre ukjente krever litt mer arbeid å løse enn et system med to ligninger med to ukjente, men målet er det samme: Kombiner ligningspar på smart måte for å eliminere variabler.

For eksempel, hvis du trekker den første ligningen fra den andre, får du den nye ligningen 45 = 21A + 3B. På samme måte, hvis du trekker den andre ligningen fra den tredje, får du 23 = 11A + B. Disse algebraiske manipulasjonene produserer et nytt system:

45 = 21A + 3B

23 = 11A + B

Nå har du et "to-og-to"-system: to ligninger med to ukjente. For å løse det, kan du multiplisere den andre ligningen med −3 og legge den til den første ligningen:

Legg merke til hvordan gjentatt eliminering har gjort det opprinnelige systemet med tre ligninger til en enkelt ligning som enkelt kan løses: A = 2. Arbeider du bakover, kan du plugge A = 2 inn i en av ligningene i to-til-to-systemet for å finne B = 1, og plugg deretter begge verdiene inn i en av de opprinnelige ligningene for å få C = 4. Etter å ha brukt det enkle alfabetchifferet på 2, 1 og 4, vet Zeke at Art kommer til å gjøre "BAD" på morgendagens engelskprøve. Han får i det minste mye algebratrening.

Takket være et spesielt faktum om polynomfunksjoner, kan du overføre en melding av hvilken som helst lengde ved å bruke Reed-Solomon-koder. Nøkkelen er dette: Gitt noen n punkter i flyet med forskjellige x-koordinater, er det et unikt polynom av "grad" n − 1 som går gjennom dem. Graden av et polynom er den høyeste potensen til en variabel i uttrykket, så en kvadratisk funksjon som Ax² + Bx + C har grad 2, siden den høyeste kraften på x er 2. Og en lineær funksjon har grad 1, siden i ligningen y = Ax + B, den høyeste kraften til x er 1.

I det første eksemplet brukte vi det faktum at to punkter bestemmer et unikt lineært, eller grad-1, polynom. I den andre stolte vi på det faktum at tre punkter bestemmer et unikt grad-2, eller kvadratisk, polynom. Og hvis du ønsker å sende en melding med lengde 10, bare kode meldingen som de 10 koeffisientene til en grad-9 polynomfunksjon. Når du har fått funksjonen din, beregner du de 10 offentlige y-verdier ved å evaluere funksjonen på tidligere avtalte 10 private x-verdier. Når du har gjort det, kan du trygt passere dem y-koordinater offentlig for mottakeren å dekode. I praksis er Reed-Solomon-koder litt mer komplekse enn dette, og bruker mer sofistikerte typer koeffisienter og oversettelsesskjemaer, men den grunnleggende ideen er den samme.

I tillegg til å holde meldingen din sikker, tilbyr Reed-Solomon-koder også enkle og effektive måter å fange opp og til og med korrigere feil. Dette er viktig når som helst data overføres eller lagres, siden det alltid er en sjanse for at noe av informasjonen går tapt eller blir ødelagt.

En løsning på dette problemet ville være å ganske enkelt sende ekstra kopier av dataene. For eksempel kan Zeke sende meldingen [14, 14, 14, 15, 15, 15] i stedet for [14, 15]. Så lenge Art vet at hver del av meldingen sendes i tre eksemplarer, kan han dekode meldingen og se etter feil. Faktisk, hvis han finner noen feil, har han en god sjanse til å rette dem. Hvis Art mottar [14, 14, 24, 15, 15, 15], varsler det faktum at de tre første tallene er forskjellige ham om en feil, og siden to av dem er 14, kan han gjette at de 24 sannsynligvis bør være en 14 også. I stedet for å be om at budskapet sendes på nytt, kan Art fortsette med avkodingen. Dette er en effektiv, men kostbar strategi. Uansett hvilken tid, energi og innsats som kreves for å sende n informasjon, krever dette tre ganger så mye.

Men matematikken bak Reed-Solomon-koder tilbyr et effektivt alternativ. I stedet for å sende flere kopier av hver del av data, kan du bare sende ett ekstra poeng! Hvis det ekstra punktet passer til polynomet ditt, er informasjonen korrekt. Hvis den ikke gjør det, har det oppstått en feil.

For å se hvordan dette fungerer, anta at du vil sjekke meldingen "NO" i det første eksemplet. Zeke kan bare sende tillegget y-koordinat 155. Forutsatt at han og Art ble enige om en tredje menig x-koordinere på forhånd, si x = 10, Art kan sjekke dette tredje punktet mot linjen han dekodet. Når han plugger x = 10 inn y = 14x + 15 og ser at resultatet er 155, han vet at det ikke var noen feil i overføringen.

Dette fungerer ikke bare for linjer. For å gjøre det mulig for Zeke å sjekke "BAD" i det andre eksemplet, kan Art sende y = 25. Hvis de har blitt enige om at 3 er den ekstra private x-koordinere, Zeke kan plugge x = 3 inn i sin kvadratiske funksjon y = 2x² + x + 4 og verifiser at punktet (3, 25) passer, bekrefter igjen en feilfri overføring med bare ett punkt til.

Og det ekstra poenget kan potensielt korrigere feil også. Hvis det oppdages en feil og mottakeren ikke kan konstruere polynomfunksjonen som inneholder meldingen, kan de i stedet konstruere det "best-tilpassede" polynomet ved hjelp av regresjonsteknikker. Som en linje med beste tilpasning i statistikkklassen, er dette polynomfunksjonen som er matematisk bestemt til å passe best til de gitte punktene, selv om den ikke passerer gjennom alle. Avhengig av strukturen til meldingen og hvor mye ekstra informasjon du sender, kan dette best passende polynomet hjelpe deg å rekonstruere det riktige polynomet – og dermed den riktige meldingen – selv fra korrupt informasjon.

Denne effektiviteten i å overføre og korrigere kommunikasjon forklarer hvorfor NASA har brukt Reed-Solomon-koder på sine oppdrag til månen og til Mars. Og det gir deg noe å tenke på når du løser ditt neste ligningssystem. Mens du gjetter, sjekk eller eliminer veien til løsningen, tenk på kraften og elegansen til Reed-Solomon-koder og alle hemmelighetene systemet ditt kan avsløre.

Øvelser

1. Ved å bruke samme opplegg som de brukte i klassen, legger Art ut de offentlige tallene 33 og 57 for Zeke å dekode. Hva er meldingen?

2. Hvordan kan Art og Zeke være sikre på at systemet av ligninger som er et resultat av deres private tall x = 3 og x = 6 vil alltid ha en løsning?

3. Som svar på Arts melding om "DÅRLIG" om engelskprøven, sender Zeke tilbake [90, 387, 534]. Forutsatt at de bruker det samme opplegget som de brukte i klassen, hva er budskapet hans?

4. Lola sender deg en melding på to bokstaver pluss ett feilkontrollnummer ved hjelp av en Reed-Solomon-kode og det samme enkle alfabetchifferet som brukes av Art og Zeke. Du har i all hemmelighet blitt enige om x-koordinater 1, 3 og 10 på forhånd, og Lola sender de offentlige numrene [27, 43, 90]. Inneholder meldingen en feil?