Die grundlegende Algebra hinter Geheimcodes und Weltraumkommunikation

Die Erforschung des Weltraums erfordert enorme Präzision. Wenn Sie einen Rover 70 Millionen Meilen von der nächsten Tankstelle entfernt auf dem Mars landen, müssen Sie die Effizienz maximieren und sich auf das Unerwartete vorbereiten. Dies gilt für alles, vom Raumfahrzeugdesign bis zur Datenübertragung: Diese Nachrichten, die als stetiger Strom von Nullen und Einsen zur Erde zurückkehren, enthalten zwangsläufig einige Fehler, daher müssen Sie in der Lage sein, sie zu identifizieren und zu korrigieren, ohne wertvolle Zeit und Energie zu verschwenden.

Hier kommt Mathematik ins Spiel. Mathematiker haben ausgeklügelte Methoden erfunden, um Informationen zu übertragen und zu speichern. Eine überraschend effektive Methode verwendet Reed-Solomon-Codes, die auf der gleichen grundlegenden Algebra aufbauen, die Schüler in der Schule lernen. Lassen Sie uns in einem Mathematikkurs vorbeischauen, um zu sehen, wie Reed-Solomon-Codes dabei helfen, Informationen zu übertragen und zu sichern und gleichzeitig kostspielige Fehler zu korrigieren, die auftauchen.

Zwei Schüler, Art und Zeke, tauschen geheime Botschaften in Frau Al-Jabrs Mathematikunterricht aus. Art entfaltet Zekes neueste Notiz, um die Nummern 57 und 99 zu enthüllen. Er weiß, dass er die liefern muss x-Koordinaten 3 und 6, um die Punkte (3, 57) und (6, 99) zu erstellen. Art fügt jeden Punkt in die lineare Gleichung ein y = Ax + B und ergibt folgendes Gleichungssystem:

57 = 3A + B

99 = 6A + B

Um die Nachricht zu entschlüsseln, muss Art lösen A und B. Er beginnt damit, die erste Gleichung von der zweiten zu subtrahieren:

Dadurch entfällt B. Beide Seiten dieser neuen Gleichung durch 3 zu dividieren sagt Art das A = 14, und setzt dies dann wieder in die erste Gleichung ein, 57 = 3 × 14 + Bgibt B = 15.

Die Kunst weiß jetzt, dass die durch (3, 57) und (6, 99) verlaufende Gerade durch die Gleichung beschrieben wird y = 14x + 15. Er weiß aber auch, dass sich bei einem Reed-Solomon-Code die geheime Botschaft in den Koeffizienten verbirgt. Er entschlüsselt Zekes Nachricht mit ihrer einfachen, vereinbarten Alphabet-Chiffre: 14 ist „N“ und 15 ist „O“, was Art sagt, dass Zeke heute nach der Schule keine Videospiele spielen kann.

Das Geheimnis dieses einfachen Reed-Solomon-Codes beginnt mit zwei grundlegenden Tatsachen der Geometrie. Erstens gibt es durch zwei beliebige Punkte eine eindeutige Linie. Zweitens für Koeffizienten A und B, kann jede (nicht senkrechte) Linie in das Formular geschrieben werden y = Ax + B. Zusammen garantieren diese beiden Tatsachen, dass Sie zwei Punkte auf einer Linie finden können, wenn Sie sie kennen A und B, und wenn Sie wissen A und B, kennst du alle Punkte auf der Geraden. Kurz gesagt, der Besitz eines der beiden Informationssätze ist gleichbedeutend mit der Kenntnis der Linie.

Reed-Solomon-Codes nutzen diese äquivalenten Informationssätze. Die geheime Nachricht wird als Koeffizienten codiert A und B, und die Punkte der Linie werden in Stücke zerlegt, von denen einige öffentlich übertragen und einige privat gehalten werden. Um die Nachricht zu entschlüsseln, sammeln Sie einfach die Teile und setzen sie wieder zusammen. Und alles, was dies erfordert, ist etwas einfache Algebra.

Zekes Stücke waren die Nummern 57 und 99, die er an Art schickte. Diese Nummern sind der öffentliche Teil der Nachricht. Art setzte diese mit seinen eigenen Stücken 3 und 6 zusammen, um die Punkte (3, 57) und (6, 99) zu rekonstruieren. Hier bilden die 3 und die 6 den privaten Teil der Nachricht, auf den sich Art und Zeke vorher geeinigt haben.

Die beiden Punkte liegen auf einer Linie, und um die Nachricht zu entschlüsseln, müssen Sie nur die Gleichung dieser Linie finden. Stecken Sie jeden Punkt in y = Ax + B gibt Ihnen ein System von zwei Gleichungen über die Linie, die beide wahr sein müssen. Jetzt ist die Strategie einfach: Lösen Sie das System, bestimmen Sie die Linie und entschlüsseln Sie die Nachricht.

Im Algebra-Unterricht haben Sie wahrscheinlich viele Methoden zum Lösen von Gleichungssystemen gelernt, wie z. Art verwendet Eliminierung, eine Methode, bei der Sie die Gleichungen algebraisch manipulieren, um die Variablen einzeln zu eliminieren. Jedes Mal, wenn Sie eine Variable eliminieren, wird das System ein wenig einfacher zu lösen.

Wie bei anderen Verschlüsselungsschemata ist es die clevere Kombination aus öffentlichen und privaten Informationen, die die Nachrichten sicher hält. Zeke könnte seine Nummern 57 und 99 durch das Klassenzimmer rufen und es würde die Sicherheit seiner Nachricht an Art nicht gefährden (obwohl er dadurch Ärger mit Frau Al-Jabr bekommen könnte). Das liegt daran, dass ohne die entsprechenden privaten Informationen – die x-Koordinaten 3 und 6 — es ist unmöglich, die Gleichung der Linie zu identifizieren. Solange sie diese Werte für sich behalten, können sie ihre geheimen Botschaften sicher an die Öffentlichkeit weitergeben.

Die Linie y = 14x + 15 ist in Ordnung, um das aus zwei Buchstaben bestehende Wort „nein“ zu übermitteln, aber was ist, wenn die Schüler ein längeres Geheimnis teilen möchten? Hier kommt die volle Kraft von Algebra, Geometrie und linearen Gleichungssystemen ins Spiel.

Angenommen, Zeke möchte wissen, wie Art denkt, dass er im morgigen Englischtest abschneiden wird. Art wandelt seine aus drei Buchstaben bestehende Antwort in die Zahlen 14, 59 und 82 um und gibt diese an Zeke weiter. Die Schüler waren sich vorher einig, dass bei Verwendung von Reed-Solomon-Codes der Länge 3 ihre Privatzahlen 2, 5 und 6 sind, also fügt Zeke die Teile zusammen, um die Punkte (2, 14), (5, 59) und (6, 82).

Nun gibt es keine lineare Funktion, die durch diese drei Punkte geht. Aber es gibt eine einzigartige quadratische Funktion, die das tut. Und da jede quadratische Funktion in der Form geschrieben werden kann y = Ax² + Bx + C, kann das gleiche allgemeine Verfahren angewendet werden. Der einzige Unterschied besteht in der Größe des Systems.

Stecken Sie jeden Punkt in y = Ax² + Bx + C ergibt eine Gleichung, also erzeugen die drei Punkte das folgende System von drei Gleichungen:

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

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

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

Ein System aus drei Gleichungen mit drei Unbekannten erfordert etwas mehr Arbeit zum Lösen als ein System aus zwei Gleichungen mit zwei Unbekannten, aber das Ziel ist dasselbe: Gleichungspaare geschickt kombinieren, um Variablen zu eliminieren.

Wenn Sie beispielsweise die erste Gleichung von der zweiten subtrahieren, erhalten Sie die neue Gleichung 45 = 21A + 3B. Ebenso erhält man 23 = 11, wenn man die zweite Gleichung von der dritten subtrahiertA + B. Diese algebraischen Manipulationen erzeugen ein neues System:

45 = 21A + 3B

23 = 11A + B

Jetzt haben Sie ein „Zwei-mal-zwei“-System: zwei Gleichungen mit zwei Unbekannten. Um es zu lösen, können Sie die zweite Gleichung mit −3 multiplizieren und zur ersten Gleichung hinzufügen:

Beachten Sie, wie die wiederholte Eliminierung das ursprüngliche System von drei Gleichungen in eine einzige Gleichung verwandelt hat, die leicht gelöst werden kann: A = 2. Wenn Sie rückwärts arbeiten, können Sie einstecken A = 2 in eine der Gleichungen im Zwei-mal-Zwei-System zu finden B = 1, und setzen Sie dann beide Werte in eine der ursprünglichen Gleichungen ein, um zu erhalten C = 4. Nachdem Zeke die einfache Alphabetchiffre bei 2, 1 und 4 verwendet hat, weiß er, dass Art im morgigen Englischtest „SCHLECHT“ abschneiden wird. Wenigstens bekommt er viel Algebra-Übung.

Dank einer Besonderheit bei Polynomfunktionen können Sie mit Reed-Solomon-Codes eine Nachricht beliebiger Länge übertragen. Der Schlüssel ist folgender: Gegeben beliebig n Punkte in der Ebene mit unterschiedlichen x-Koordinaten gibt es ein eindeutiges Polynom von „Grad“ n − 1, die durch sie hindurchgeht. Der Grad eines Polynoms ist die höchste Potenz einer Variablen im Ausdruck, also eine quadratische Funktion wie Ax² + Bx + C hat Grad 2, da die höchste Potenz von x ist 2. Und eine lineare Funktion hat Grad 1, da in der Gleichung y = Ax + B, die höchste Macht von x ist 1.

Im ersten Beispiel haben wir die Tatsache verwendet, dass zwei Punkte ein eindeutiges lineares Polynom oder Grad-1-Polynom bestimmen. Im zweiten haben wir uns auf die Tatsache verlassen, dass drei Punkte ein eindeutiges Grad-2- oder quadratisches Polynom bestimmen. Und wenn Sie eine Nachricht der Länge 10 senden möchten, codieren Sie die Nachricht einfach als die 10 Koeffizienten einer Polynomfunktion 9. Grades. Sobald Sie Ihre Funktion haben, berechnen Sie die 10 Öffentlichkeit y-Werte durch Auswertung der Funktion bei den zuvor vereinbarten 10 Privaten x-Werte. Sobald Sie das getan haben, können Sie diese sicher passieren y-Koordinaten in der Öffentlichkeit, damit Ihr Empfänger sie entschlüsseln kann. In der Praxis sind Reed-Solomon-Codes etwas komplexer als diese und verwenden anspruchsvollere Arten von Koeffizienten und Übersetzungsschemata, aber die grundlegende Idee ist die gleiche.

Reed-Solomon-Codes schützen nicht nur Ihre Nachricht, sondern bieten auch einfache und effiziente Möglichkeiten, Fehler zu erkennen und sogar zu korrigieren. Dies ist immer dann wichtig, wenn Daten übertragen oder gespeichert werden, da immer die Möglichkeit besteht, dass einige der Informationen verloren gehen oder beschädigt werden.

Eine Lösung für dieses Problem wäre, einfach zusätzliche Kopien der Daten zu senden. Zum Beispiel kann Zeke die Nachricht [14, 14, 14, 15, 15, 15] statt [14, 15] senden. Solange Art weiß, dass jeder Teil der Nachricht dreifach gesendet wird, kann er die Nachricht entschlüsseln und auf Fehler überprüfen. Wenn er Fehler findet, hat er sogar gute Chancen, sie zu korrigieren. Wenn Art [14, 14, 24, 15, 15, 15] erhält, macht ihn die Tatsache, dass die ersten drei Zahlen unterschiedlich sind, auf einen Fehler aufmerksam, und da zwei von ihnen 14 sind, kann er vermuten, dass die 24 wahrscheinlich a sein sollte 14 auch. Anstatt das erneute Senden der Nachricht zu verlangen, kann Art mit seiner Entschlüsselung fortfahren. Dies ist eine effektive, aber kostspielige Strategie. Unabhängig davon, wie viel Zeit, Energie und Mühe zum Senden erforderlich sind n Informationen benötigt man dreimal so viel.

Aber die Mathematik hinter den Reed-Solomon-Codes bietet eine effiziente Alternative. Anstatt mehrere Kopien von jedem Datenelement zu senden, können Sie einfach einen zusätzlichen Punkt senden! Wenn dieser zusätzliche Punkt zu Ihrem Polynom passt, sind die Informationen korrekt. Ist dies nicht der Fall, liegt ein Fehler vor.

Um zu sehen, wie das funktioniert, nehmen Sie an, Sie möchten die Meldung „NEIN“ im ersten Beispiel überprüfen. Zeke kann einfach die zusätzlichen senden y-Koordinate 155. Angenommen, er und Art einigten sich auf einen dritten Gefreiten x-vorher koordinieren, sagen wir x = 10, Art kann diesen dritten Punkt mit der von ihm entschlüsselten Zeile vergleichen. Wenn er einsteckt x = 10 hinein y = 14x + 15 und sieht, dass das Ergebnis 155 ist, weiß er, dass es keine Fehler bei der Übertragung gab.

Dies funktioniert nicht nur für Linien. Damit Zeke im zweiten Beispiel „BAD“ überprüfen kann, kann Art senden y = 25. Wenn sie sich darauf geeinigt haben, dass 3 das Extra Private ist x-koordinieren, Zeke kann stecken x = 3 in seine quadratische Funktion y = 2x² + x + 4 und überprüfen Sie, ob der Punkt (3, 25) passt, und bestätigen Sie erneut eine fehlerfreie Übertragung mit nur einem weiteren Punkt.

Und dieser zusätzliche Punkt kann möglicherweise auch Fehler korrigieren. Wenn ein Fehler erkannt wird und der Empfänger die Polynomfunktion, die die Nachricht enthält, nicht konstruieren kann, kann er stattdessen das „am besten passende“ Polynom unter Verwendung von Regressionstechniken konstruieren. Wie eine Gerade im Statistikunterricht ist dies die Polynomfunktion, die mathematisch so bestimmt wird, dass sie am besten zu den gegebenen Punkten passt, auch wenn sie nicht durch alle geht. Abhängig von der Struktur der Nachricht und wie viele zusätzliche Informationen Sie senden, kann Ihnen dieses am besten passende Polynom helfen, das richtige Polynom – und damit die richtige Nachricht – selbst aus beschädigten Informationen zu rekonstruieren.

Diese Effizienz bei der Übertragung und Korrektur von Nachrichten erklärt, warum die NASA bei ihren Missionen zum Mond und zum Mars Reed-Solomon-Codes verwendet hat. Und es gibt Ihnen etwas zum Nachdenken, wenn Sie Ihr nächstes Gleichungssystem lösen. Während Sie raten, überprüfen oder eliminieren Sie Ihren Weg zur Lösung, denken Sie an die Kraft und Eleganz von Reed-Solomon-Codes und all die Geheimnisse, die Ihr System offenbaren könnte.

Übungen

1. Unter Verwendung des gleichen Schemas, das sie im Unterricht verwendet haben, veröffentlicht Art die öffentlichen Nummern 33 und 57, damit Zeke sie entschlüsseln kann. Was ist die Nachricht?

2. Wie können Art und Zeke sicher sein, dass das Gleichungssystem, das sich aus ihren privaten Zahlen ergibt x = 3 und x = 6 wird immer eine Lösung haben?

3. Als Antwort auf die Nachricht von Art „SCHLECHT“ über den Englischtest schickt Zeke zurück [90, 387, 534]. Angenommen, sie verwenden dasselbe Schema wie im Unterricht, was ist seine Botschaft?

4. Lola sendet Ihnen eine Zwei-Buchstaben-Nachricht plus eine Fehlerprüfnummer unter Verwendung eines Reed-Solomon-Codes und der gleichen einfachen Alphabetchiffre, die von Art und Zeke verwendet wird. Sie haben sich heimlich darauf geeinigt x-koordiniert 1, 3 und 10 im Voraus, und Lola übermittelt die öffentlichen Nummern [27, 43, 90]. Enthält die Nachricht einen Fehler?