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

这消除了B 。将这个新等式的两边除以 3 告诉阿特A = 14，然后将其代回第一个等式 57 = 3 × 14 + B ，得到B = 15。

Art 现在知道通过 (3, 57) 和 (6, 99) 的线由方程y = 14 x + 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 = 14 x + 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 = 4 A + 2 B + C

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

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

具有三个未知数的三个方程组比具有两个未知数的两个方程组需要更多的工作来求解，但目标是相同的：巧妙地组合方程对以消除变量。

例如，如果您从第二个方程中减去第一个方程，您将得到新方程 45 = 21 A + 3 B 。同样，如果从第三个等式中减去第二个等式，则会得到 23 = 11 A + B。这些代数运算产生了一个新系统：

45 = 21 A + 3 B

23 = 11 A + 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 次多项式的事实。在第二个中，我们依赖于三个点确定唯一的二次多项式或二次多项式这一事实。如果要发送长度为 10 的消息，只需将消息编码为 9 次多项式函数的 10 个系数。获得函数后，通过在先前商定的 10 个私有x值处评估函数来计算 10 个公共y值。一旦你这样做了，你就可以安全地公开传递那些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坐标 155。假设他和 Art 事先就第三个私有x坐标达成一致，比如x = 10，Art 可以根据他解码的行检查这第三个点。当他将x = 10 代入y = 14 x + 15 并看到结果为 155 时，他知道传输没有错误。

这不仅适用于线路。为了让 Zeke 在第二个例子中检查“BAD”，Art 可以发送y = 25。如果他们同意 3 是额外的私有x坐标，Zeke 可以将x = 3 代入他的二次函数y = 2 x ² + 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】。消息是否包含错误？