Базовая алгебра секретных кодов и космической связи

Исследование космоса требует огромной точности. При посадке марсохода на расстоянии 70 миллионов миль от ближайшей сервисной станции вам необходимо максимально эффективно действовать и быть готовым к неожиданностям. Это относится ко всему, от конструкции космического корабля до передачи данных: сообщения, возвращающиеся на Землю в виде непрерывного потока нулей и единиц, обязательно будут содержать некоторые ошибки, поэтому вам нужно уметь идентифицировать и исправлять их, не теряя драгоценного времени и энергии.

Вот где на помощь приходит математика. Математики изобрели оригинальные способы передачи и хранения информации. Один удивительно эффективный метод использует Коды Рида-Соломона, которые построены на той же базовой алгебре, которую ученики изучают в школе. Давайте заглянем на урок математики, чтобы узнать, как коды Рида-Соломона помогают передавать и защищать информацию, исправляя любые всплывающие дорогостоящие ошибки.

Два ученика, Арт и Зик, обмениваются секретными сообщениями на уроке математики у мисс Аль-Джабр. Арт разворачивает последнюю записку Зика, чтобы увидеть числа 57 и 99. Он знает, что должен предоставить x-координаты 3 и 6 для создания точек (3, 57) и (6, 99). Искусство включает каждую точку в линейное уравнение y = Ax + B и дает следующую систему уравнений:

57 = 3A + B

99 = 6A + B

Чтобы расшифровать сообщение, Искусство должно решить для A и B. Он начинает с вычитания первого уравнения из второго:

Это устраняет B. Разделение обеих частей этого нового уравнения на 3 говорит Арту, что A = 14, а затем подставив это обратно в первое уравнение, 57 = 3 × 14 + Bдает B = 15.

Искусство теперь знает, что линия, проходящая через (3, 57) и (6, 99), описывается уравнением y = 14x + 15. Но он также знает, что в коде Рида-Соломона секретное сообщение скрывается в коэффициентах. Он расшифровывает сообщение Зика, используя их простой согласованный алфавитный шифр: 14 — это «N», а 15 — это «O», что говорит Арту, что нет, Зик не может сегодня играть в видеоигры после школы.

Секрет этого простого кода Рида-Соломона начинается с двух основных фактов геометрии. Во-первых, через любые две точки проходит единственная прямая. Во-вторых, для коэффициентов A и B, каждую (не вертикальную) строку можно записать в виде y = Ax + B. Вместе эти два факта гарантируют, что если вам известны две точки на прямой, вы можете найти A и B, и если вы знаете A и B, вы знаете все точки на линии. Короче говоря, обладание любым набором информации эквивалентно знанию линии.

Коды Рида-Соломона используют эти эквивалентные наборы информации. Секретное сообщение кодируется как коэффициенты A и B, а точки линии разбиты на части, некоторые из которых передаются публично, а некоторые остаются в тайне. Чтобы расшифровать сообщение, вы просто собираете кусочки и соединяете их вместе. И все, что для этого требуется, — это нехитрая алгебра.

Фигурками Зика были номера 57 и 99, которые он отправил в Арт. Эти номера являются общедоступной частью сообщения. Арт соединил их со своими фигурами 3 и 6, чтобы реконструировать точки (3, 57) и (6, 99). Здесь цифры 3 и 6 составляют личную часть сообщения, о чем Арт и Зик договорились заранее.

Две точки лежат на линии, и чтобы расшифровать сообщение, вам просто нужно найти уравнение этой линии. Подключив каждую точку к y = Ax + B дает вам систему двух уравнений относительно линии, которые оба должны быть истинными. Теперь стратегия проста: решить систему, определить строку и расшифровать сообщение.

На уроках алгебры вы, вероятно, изучили многие методы решения систем уравнений, такие как построение графиков, угадывание и проверка, а также подстановка. Искусство использовало исключение, метод, при котором вы алгебраически манипулируете уравнениями, чтобы исключить переменные по одной за раз. Каждый раз, когда вы исключаете переменную, решение системы становится немного проще.

Как и в случае с другими схемами шифрования, это разумное сочетание общедоступной и частной информации обеспечивает безопасность сообщений. Зик мог выкрикнуть свои числа 57 и 99 через класс, и это не поставило бы под угрозу безопасность его послания Арту (хотя из-за этого у него могли возникнуть проблемы с мисс Аль-Джабр). Это потому, что без соответствующей личной информации — x-координаты 3 и 6 — невозможно определить уравнение прямой. Пока они хранят эти ценности при себе, они могут безопасно передавать свои секретные сообщения публично.

Линия y = 14x + 15 подходит для передачи двухбуквенного слова «нет», но что, если ученики хотят поделиться более длинным секретом? Вот где в игру вступает вся мощь алгебры, геометрии и систем линейных уравнений.

Предположим, Зик хочет знать, как, по мнению Арта, он справится с завтрашним тестом по английскому языку. Арт преобразует свой трехбуквенный ответ в числа 14, 59 и 82 и передает их Зику. Студенты заранее договорились, что при использовании кодов Рида-Соломона длины 3 их частные числа будут 2, 5 и 6, поэтому Зик складывает кусочки вместе, чтобы восстановить точки (2, 14), (5, 59) и (6, 82).

Теперь не существует линейной функции, проходящей через эти три точки. Но есть уникальная квадратичная функция, которая это делает. А так как любую квадратичную функцию можно записать в виде y = Ax² + Bx + C, можно применить тот же общий метод. Разница только в размере системы.

Подключив каждую точку к y = Ax² + Bx + C дает одно уравнение, поэтому три точки дают следующую систему из трех уравнений:

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

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

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

Для решения системы из трех уравнений с тремя неизвестными требуется немного больше усилий, чем для решения системы из двух уравнений с двумя неизвестными, но цель одна и та же: ловко комбинировать пары уравнений, чтобы исключить переменные.

Например, если вычесть первое уравнение из второго, вы получите новое уравнение 45 = 21.A + 3B. Точно так же, если вычесть второе уравнение из третьего, вы получите 23 = 11.A + B. Эти алгебраические манипуляции дают новую систему:

45 = 21A + 3B

23 = 11A + B

Теперь у вас есть система «два на два»: два уравнения с двумя неизвестными. Чтобы решить его, вы можете умножить второе уравнение на -3 и добавить его к первому уравнению:

Обратите внимание, как многократное исключение превратило исходную систему из трех уравнений в одно уравнение, которое можно легко решить: A = 2. Работая в обратном направлении, можно подключить A = 2 в одно из уравнений системы два на два, чтобы найти B = 1, а затем подставьте оба значения в одно из исходных уравнений, чтобы получить C = 4. После использования простого алфавитного шифра на 2, 1 и 4 Зик знает, что Арт собирается получить «ПЛОХО» на завтрашнем тесте по английскому языку. По крайней мере, он много занимается алгеброй.

Благодаря особому факту о полиномиальных функциях вы можете передавать сообщения любой длины, используя коды Рида-Соломона. Ключ вот в чем: при любом n точки на плоскости с разными x-координат, существует единственный полином «степени» n − 1, который проходит через них. Степень полинома — это наивысшая степень переменной в выражении, поэтому квадратичная функция вида Ax² + Bx + C имеет степень 2, так как высшая степень x равно 2. А линейная функция имеет степень 1, так как в уравнении y = Ax + B, наивысшая мощность x это 1.

В первом примере мы использовали тот факт, что две точки определяют уникальный линейный многочлен или полином степени 1. Во втором мы полагались на тот факт, что три точки определяют уникальный полином второй степени, или квадратичный. И если вы хотите отправить сообщение длиной 2, просто закодируйте сообщение как 10 коэффициентов полиномиальной функции степени 10. Когда у вас есть функция, вычислите 9 общедоступных y-значения путем оценки функции на предварительно согласованных 10 частных x-значения. Как только вы это сделаете, вы можете безопасно пройти эти y-координаты публично для вашего приемника для декодирования. На практике коды Рида-Соломона немного сложнее, в них используются более сложные виды коэффициентов и схем перевода, но основная идея остается той же.

Помимо обеспечения безопасности вашего сообщения, коды Рида-Соломона также предлагают простые и эффективные способы обнаружения и даже исправления ошибок. Это важно каждый раз, когда данные передаются или сохраняются, так как всегда есть вероятность того, что часть информации будет потеряна или повреждена.

Одним из решений этой проблемы может быть просто отправка дополнительных копий данных. Например, Зик может отправить сообщение [14, 14, 14, 15, 15, 15] вместо [14, 15]. Пока Арт знает, что каждая часть сообщения отправляется в трех экземплярах, он может расшифровать сообщение и проверить на наличие ошибок. На самом деле, если он находит какие-либо ошибки, у него есть хорошие шансы их исправить. Если Арт получает [14, 14, 24, 15, 15, 15], тот факт, что первые три числа различны, предупреждает его об ошибке, а поскольку два из них равны 14, он может догадаться, что 24, вероятно, должно быть 14 тоже. Вместо того, чтобы просить повторно отправить сообщение, Арт может продолжить расшифровку. Это эффективная, но затратная стратегия. Какое бы время, энергия и усилия ни потребовались для отправки n единиц информации, для этого требуется в три раза больше.

Но математика, лежащая в основе кодов Рида-Соломона, предлагает эффективную альтернативу. Вместо того, чтобы отправлять несколько копий каждого фрагмента данных, вы можете просто отправить один дополнительный балл! Если эта дополнительная точка соответствует вашему многочлену, то информация верна. Если это не так, произошла ошибка.

Чтобы увидеть, как это работает, предположим, что вы хотите проверить сообщение «НЕТ» в первом примере. Зик может просто отправить дополнительный y-координата 155. Предположим, что он и Арт договорились о третьем приватном x- согласовывать заранее, скажем x = 10, Арт может сверить эту третью точку с линией, которую он расшифровал. когда он подключает x = 10 в y = 14x +15 и видит, что результат 155, он знает, что ошибок при передаче не было.

Это работает не только для линий. Чтобы позволить Зику проверить «ПЛОХО» во втором примере, Арт может отправить y = 25. Если они договорились, что 3 — это дополнительное личное x-координация, Зик может подключить x = 3 в его квадратичную функцию y = 2x² + x + 4 и убедитесь, что точка (3, 25) подходит, еще раз подтвердив безошибочную передачу еще одной точкой.

И эта дополнительная точка может потенциально исправить ошибки. Если обнаружена ошибка и получатель не может построить полиномиальную функцию, содержащую сообщение, он может вместо этого построить «наилучший» полином, используя методы регрессии. Подобно линии наилучшего соответствия в классе статистики, это полиномиальная функция, которая математически определяется как наиболее точно соответствующая заданным точкам, даже если она не проходит через все из них. В зависимости от структуры сообщения и количества дополнительной информации, которую вы отправляете, этот наиболее подходящий полином может помочь вам восстановить правильный полином — и, следовательно, правильное сообщение — даже из искаженной информации.

Эта эффективность передачи и исправления сообщений объясняет, почему НАСА использовало коды Рида-Соломона в своих полетах на Луну и на Марс. И это дает вам пищу для размышлений, когда вы решаете следующую систему уравнений. Как вы догадываетесь, проверьте или исключите свой путь к решению, подумайте о силе и элегантности кодов Рида-Соломона и обо всех секретах, которые может раскрыть ваша система.

Упражнения

1. Используя ту же схему, что и в классе, Арт публикует публичные номера 33 и 57, чтобы Зик расшифровал их. Какое сообщение?

2. Как Арт и Зик могут быть уверены, что система уравнений, вытекающая из их личных чисел x = 3 и x = 6 всегда будет иметь решение?

3. В ответ на сообщение Арта «ПЛОХО» о тесте по английскому Зик отправляет обратно [90, 387, 534]. Предполагая, что они используют ту же схему, что и в классе, каков его посыл?

4. Лола отправляет вам двухбуквенное сообщение плюс один номер для проверки ошибок, используя код Рида-Соломона и тот же самый простой алфавитный шифр, который использовали Арт и Зик. Вы тайно договорились о x-координаты 1, 3 и 10 заранее, а Лола передает публичные номера [27, 43, 90]. Сообщение содержит ошибку?