密码和空间通信背后的基本代数

太空探索需要极高的精度。 当您在距离最近的服务站 70 万英里外的火星上着陆时，您需要最大限度地提高效率并为意外情况做好准备。 这适用于从航天器设计到数据传输的方方面面：那些以 0 和 1 的稳定流形式返回地球的消息必然包含一些错误，因此您需要能够识别并纠正它们，而不会浪费宝贵的时间和精力。

这就是数学的用武之地。数学家发明了巧妙的方法来传输和存储信息。 一种出乎意料的有效方法是使用 里德-所罗门码，它们建立在学生在学校学习的相同基础代数之上。 让我们顺便上一堂数学课，看看 Reed-Solomon 代码如何帮助传输和保护信息，同时纠正弹出的任何代价高昂的错误。

两个学生，Art 和 Zeke，正在 Al-Jabr 女士的数学课上交换秘密信息。 Art 展开 Zeke 的最新笔记以显示数字 57 和 99。他知道他必须提供 x-坐标 3 和 6 以创建点 (3, 57) 和 (6, 99)。 艺术将每个点插入线性方程 y = Ax + B 并产生以下方程组：

57 = 3A + B

99 = 6A + B

为了解码消息，艺术必须解决 A 和 B. 他首先从第二个方程中减去第一个方程：

这消除了 B. 将这个新等式的两边除以 3 告诉 Art A = 14，然后将其代回第一个方程，57 = 3 × 14 + B，给出 B = 15。

Art 现在知道通过 (3, 57) 和 (6, 99) 的线由等式描述 y = 14x + 15. 但他也知道在 Reed-Solomon 密码中，秘密信息隐藏在系数中。 他使用他们商定的简单字母密码破译了 Zeke 的信息：14 是“N”，15 是“O”，这告诉 Art，不，Zeke 今天放学后不能玩电子游戏。

这个简单的 Reed-Solomon 代码的秘密始于两个基本的几何事实。 首先，通过任何两点都有一条唯一的线。 二、对于系数 A 和 B，每条（非垂直）线都可以写成以下形式 y = Ax + B. 这两个事实共同保证，如果您知道一条直线上的两点，您就可以找到 A 和 B, 如果你知道 A 和 B，你知道直线上的所有点。 简而言之，拥有任何一组信息就相当于知道这条线。

Reed-Solomon 代码利用这些等价的信息集。 秘密消息被编码为系数 A 和 B, 并且线路的点被分解成多个部分，其中一些是公开传输的，一些是保密的。 要解码消息，您只需收集碎片并将它们放回原处。 而这所需要的只是一些简单的代数。

Zeke 的作品是数字 57 和 99，他将它们寄给了 Art。 这些数字是消息的公共部分。 Art 将这些与他自己的作品 3 和 6 放在一起，以重建点 (3, 57) 和 (6, 99)。 在这里，3 和 6 构成消息的隐私部分，这是 Art 和 Zeke 事先商定的。

这两点位于一条直线上，要解码消息，您只需找到该直线的方程式即可。 将每个点插入 y = Ax + B 给你一个关于直线的两个方程组，它们都必须为真。 现在的策略很简单：解决系统问题，确定线路并解码消息。

在代数课上，您可能学到了许多求解方程组的方法，例如作图、猜测和检查以及代入。 Art 使用消元法，这是一种通过代数方式操作方程式以一次消去一个变量的方法。 每消除一个变量，系统就会变得更容易求解。

与其他加密方案一样，它是公共信息和私人信息的巧妙组合，可以确保消息的安全。 Zeke 可以在教室里大喊他的号码 57 和 99，这不会危及他给 Art 的信息的安全性（尽管这可能会让他与 Al-Jabr 女士发生麻烦）。 那是因为没有相应的私人信息—— x-坐标 3 和 6 — 无法确定直线的方程。 只要他们自己保留这些价值观，他们就可以安全地公开传递他们的秘密信息。

线 y = 14x + 15 可以传输两个字母的单词“no”，但如果学生想分享更长的秘密怎么办？ 这就是代数、几何和线性方程组的全部力量发挥作用的地方。

假设 Zeke 想知道 Art 认为他明天的英语考试成绩如何。 Art 将他的三个字母的答案转换为数字 14、59 和 82，并将它们传递给 Zeke。 学生们事先约定，当使用长度为 3 的 Reed-Solomon 码时，他们的私有数是 2、5 和 6，所以 Zeke 将这些碎片拼在一起重构点 (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 = 21A + 3B. 同样，如果用第三个方程减去第二个方程，你会得到 23 = 11A + B. 这些代数运算产生了一个新系统：

45 = 21A + 3B

23 = 11A + B

现在你有了一个“二乘二”系统：两个方程和两个未知数。 要解决它，您可以将第二个方程乘以 −3 并将其添加到第一个方程：

请注意重复消除如何将原来的三个方程组变成一个可以轻松求解的方程： A = 2.逆向工作，你可以插入 A = 2 到二乘二系统中的一个方程中找到 B = 1，然后将这两个值代入其中一个原始方程得到 C = 4. 在对 2、1 和 4 使用简单的字母密码后，Zeke 知道 Art 将在明天的英语考试中做“BAD”。 至少他得到了大量的代数练习。

由于有关多项式函数的一个特殊事实，您可以使用 Reed-Solomon 代码传输任意长度的消息。 关键是：给定任何 n 平面上的点不同 x-坐标，有一个唯一的“度”多项式 n − 1 穿过它们。 多项式的次数是表达式中变量的最高次幂，因此二次函数如 Ax² + Bx + C 度数为 2，因为 x 是 2。线性函数的次数为 1，因为在等式中 y = Ax + B, 的最高功率 x 是1。

在第一个示例中，我们使用了两个点确定唯一线性或 1 次多项式的事实。 在第二个中，我们依赖于三个点确定唯一的二次多项式或二次多项式这一事实。 如果要发送长度为 2 的消息，只需将消息编码为 10 次多项式函数的 10 个系数。 一旦你有你的功能，计算 9 public y-通过评估先前商定的 10 私有函数的值 x-价值观。 一旦你这样做了，你就可以安全地通过那些 y-公开坐标供您的接收器解码。 实际上，Reed-Solomon 代码比这复杂一点，使用更复杂的系数和转换方案，但基本思想是相同的。

除了确保您的消息安全之外，Reed-Solomon 代码还提供了简单有效的方法来捕获甚至更正错误。 这在任何时候传输或存储数据时都很重要，因为某些信息总是有可能丢失或损坏。

解决此问题的一种方法是简单地发送额外的数据副本。 例如，Zeke 可以发送消息 [14, 14, 14, 15, 15, 15] 而不是 [14, 15]。 只要 Art 知道消息的每一部分都一式三份发送，他就可以解码消息并检查错误。 事实上，如果他发现任何错误，他有很大的机会纠正它们。 如果 Art 收到 [14, 14, 24, 15, 15, 15]，前三个数字不同的事实提醒他一个错误，因为其中两个是 14，他可以猜测 24 应该是一个14也是。 Art 可以继续他的解码，而不是要求重新发送消息。 这是一种有效但代价高昂的策略。 无论需要什么时间、精力和努力去发送 n 件信息，这需要三倍的量。

但 Reed-Solomon 代码背后的数学原理提供了一种有效的替代方案。 无需发送每条数据的多个副本，您可以只发送一个额外的点！ 如果该附加点符合您的多项式，则信息正确。 如果没有，则出现错误。

要查看其工作原理，假设您要检查第一个示例中的消息“NO”。 Zeke 可以发送额外的 y-coordinate 155. 假设他和 Art 同意第三个人 x- 事先协调，说 x = 10，Art 可以根据他解码的行检查这第三个点。 当他插上 x = 10 成 y = 14x + 15 并看到结果是 155，他知道传输没有错误。

这不仅适用于线路。 为了让 Zeke 在第二个例子中检查“BAD”，Art 可以发送 y = 25. 如果他们同意 3 是额外的私有 x-坐标，Zeke 可以插入 x = 3 进入他的二次函数 y = 2x² + x + 4 并验证点 (3, 25) 是否适合，再次确认无错误传输仅需一个点。

那个额外的点也可以潜在地纠正错误。 如果检测到错误并且接收方无法构建包含消息的多项式函数，则他们可以使用回归技术构建“最佳拟合”多项式。 就像统计类中的一条最佳拟合线一样，这是数学上确定的最接近给定点的多项式函数，即使它没有通过所有这些点。 根据消息的结构和您发送的额外信息量，这个最佳多项式可以帮助您重建正确的多项式——从而重建正确的消息——即使是从损坏的信息中。

这种传输和纠正通信的效率解释了为什么 NASA 在其登月和火星任务中使用 Reed-Solomon 代码。 当你求解下一个方程组时，它会给你一些思考的机会。 当您猜测、检查或消除您的解决方案时，请考虑 Reed-Solomon 代码的强大和优雅以及您的系统可能揭示的所有秘密。

演习

1. Art用上课时的方案，发公众号33和57给Zeke解码。 消息是什么？

2. Art 和 Zeke 如何确定由他们的私人数字得出的方程组 x = 3和 x = 6 总有办法解决？

3. 为响应 Art 关于英语测试的“BAD”消息，Zeke 发回 [90, 387, 534]。 假设他们使用他们在课堂上使用的相同方案，他的信息是什么？

4. Lola 使用 Reed-Solomon 代码和 Art 和 Zeke 使用的相同简单字母密码向您发送一条包含两个字母的消息和一个错误检查号码。 你暗暗约定 x-提前坐标1、3、10，萝拉转发公众号【27、43、90】。 消息是否包含错误？