Reed-Solomon 代码有助于为大量信息技术提供动力。
克里斯蒂娜·阿米蒂奇/广达杂志
给定空间中的一组点，你能找到穿过所有点的某种曲线吗？这个问题——所谓插值问题的一个版本——自古以来就引起了数学家的兴趣。今年早些时候，数学家Eric Larson和Isabel Vogt 彻底解决了这个问题。
但是，虽然这项工作在纯数学家中引起了极大的兴趣，但插值具有远远超出几何领域的实际后果。插值是存储和通信电子数据、构建密码方案等的核心。这就是为什么您可以在刻录 CD 时仍能听到音乐，或者弄脏 QR 码后仍能扫描它的原因。这就是为什么像航海者计划这样的太空任务可以将清晰的数字图像发送回地球。这就是为什么即使其中一台计算机发生故障，一组计算机也可以执行复杂计算的原因。
这些应用程序都依赖于非常漂亮且概念上直接的插值使用：所谓的 Reed-Solomon 码，以及建立在它们之上的码。
逐点
假设您要发送由两个数字组成的消息：2 和 7。您正在传输的某些数据可能会丢失或损坏——例如，2 可能会翻转为 -2。因此，您可以添加额外的信息来帮助收件人识别和修复可能出现的错误，而不是简单地发送数据。这就是所谓的纠错码。
这种代码的最简单示例涉及多次传输相同的消息。为了让接收者识别是否发生错误，请发送相同的消息两次：2、7、2、7。如果相应位置的数字不匹配（例如，如果传输改为读取 2、7、-2、 7），收件人会知道其中一个是错误的——但不知道是哪一个。为了让他们弄清楚并纠正错误，请发送相同的消息三次：2、7、2、7、2、7。收件人只需进行多数表决即可找出您想要的消息。
但是这种纠正错误的方法非常低效。这是一个更聪明的方法：将消息编码为曲线，并发送足够的信息以允许接收者重建该曲线。
在我们传输 2 和 7 的简单情况下，曲线将是线y = 2 x + 7。在x的两个预定值处评估该曲线，并传输得到的y值。接收者现在有两个点，因为插值问题告诉我们两个点确定一条唯一的线，接收者只需找到穿过他们接收到的点的线。线的系数揭示了预期的信息。
美林谢尔曼/广达杂志
美林谢尔曼/广达杂志
为避免错误，您再次添加额外信息。在这里，您发送对应于另一个预定x坐标的y值。如果三个点不在同一条线上，则存在错误。为了找出错误在哪里，您只需再发送一个值——这意味着您总共发送了四个数字，而不是前一种方法所需的六个。
优势随着消息的大小而增长。假设您要发送更长的消息 – 1,000 个号码。效率较低的代码需要发送 2,000 个数字来识别错误，并需要发送 3,000 个数字来纠正错误。但是，如果您使用涉及通过给定点对多项式进行插值的代码，您只需要 1,001 个数字即可找到错误，并需要 1,002 个数字来纠正它。 （您可以添加更多点来识别和纠正更多潜在错误。）随着消息长度的增加，两个代码之间的效率差异变得更加明显。
在概念验证测试中，美国宇航局的科学家将蒙娜丽莎编码到激光束上，并将其从地球表面发送到月球航天器。 Reed-Solomon 码用于纠正地球大气层引入的传输错误。
但是 Reed-Solomon 码也有一个重要的约束。它们的构造方式使您只能在一组固定（通常相对较小）的值上评估多项式。也就是说，您只能使用一组特定的数字来编码您的消息。该集合或字母表的大小反过来又限制了您可以发送的消息的长度 – 您尝试制作的字母表越大，解码这些消息所需的计算能力就越大。
因此，数学家寻求更优化的代码。
未来代码
更通用、更强大的代码将允许您存储或发送更长的消息，而无需增加字母表的大小。为此，数学家设计了涉及通过该曲线上的给定点对函数进行插值的代码——该函数位于与更复杂曲线相关的特殊空间中。这些所谓的代数几何代码“突然出现，它们比我们知道如何制作[使用更小的字母表]的任何其他代码都要好，”Kopparty 说。 “这胜过一切。这真是一个震惊。”
只有一个问题。在实践中，实现 Reed-Solomon 代码比实现代数几何代码要容易得多。密码学家西蒙·阿伯拉德（ Simon Abelard ）说：“这是最先进的，但仍需研究才能真正变成实用的东西。” “它涉及相当抽象的数学，很难在计算机上处理这些代码。”
目前，这并不令人担忧：在实际应用中，Reed-Solomon 码和相关形式的纠错就足够了。但情况可能并非总是如此。例如，如果未来可以使用强大的量子计算机，它们将能够破解当今的密码协议。因此，研究人员一直在寻找能够抵抗量子攻击的方案。此类方案的一个顶级竞争者将需要比 Reed-Solomon 码更强大的东西。某些版本的代数几何代码可能只是工作。其他研究人员对代数几何代码在云计算中可能发挥的作用抱有希望。
但即使没有这种潜在用途，“在数学史上，有时你会发现现在真正没有应用的新事物，”荷兰埃因霍温理工大学研究代数的研究员Elena Berardini说。几何代码。 “但 50 年后，你会发现它可能对一些完全出乎意料的事情有用”——就像古老的插值问题本身一样。
原文： https://www.quantamagazine.org/how-mathematical-curves-power-cryptography-20220919/