作者 | Jordana Cepelewicz

译者 | 万物有数

原载于 | Quanta Magazine

引言

给定空间中的一组点, 你能找到一条经过所有点的曲线吗？这个问题是数学中插值问题的一个版本, 几千年来一直吸引着数学家的注意力. 2022年, 数学家埃里克·拉尔森（Eric Larson）和伊莎贝尔·沃格特（Isabel Vogt）彻底解决了这个问题^[1].

然而, 尽管这项工作在纯数学家当中引起了极大的轰动, 但插值的实际影响却远远超出了几何学的范畴. 插值在存储和传输电子数据、构建密码方案等方面都起着关键作用. 为什么你刮花了一张 CD 仍然能听到音乐, 弄脏了二维码仍然能扫描？为什么像“旅行者”计划这样的太空任务能够将清晰的数字图像传回地球？为什么即使其中一台计算机发生故障, 一组计算机也能执行复杂的计算?

这些应用全都依赖于一种极其优美且概念简单的插值方法：Reed-Solomon 码, 以及在此基础上构建的其他编码.

Reed-Solomon 码

假设你要发送一条由两个数字组成的消息： 和 . 你传输的某些数据可能会丢失或损坏. 例如, 可能会翻转为 . 因此, 除了简单地发送数据之外, 你还可以添加额外信息来帮助接收者识别和修复可能出现的错误. 这就是所谓的纠错码.

这种编码最简单的例子是多次传输同一条消息. 为了让接收者识别是否发生了错误, 可以将相同的消息传输两次：. 如果相应位置的数字不匹配（例如传输结果是 ）, 接收者会知道其中一个是错误的, 但不知道是哪一个. 为了让他们弄清楚并纠正错误, 消息可以传输三次：. 接收者只需采取多数票就可以推断出你想要传达的信息.

但这种纠正错误的方法效率极低. 这里有一个更聪明的方法：将信息编码为曲线, 并发送足够的信息让接收者重建该曲线.

在我们传输 和 的简单例子中, 曲线可以是直线 . 在两个预先确定的x值处计算此曲线, 并传输得到的值. 接收者现在有两个点, 由于插值问题告诉我们两个点确定一条唯一的直线, 因此接收者只需找到经过他们接收到的点的直线即可. 这条直线的系数就是要传达的消息.

为了避免错误, 你再次添加了额外的信息. 在这里, 你发送与另一个预定的坐标相对应的值. 如果三个点不在同一条直线上, 则会出现错误. 要找出错误所在, 你只需再发送一个值 —— 这意味着你总共发送了四个数字, 而不是之前方法所需的六个数字.

信息量越大, 优势就越大. 假设你要发送一条较长的信息—— 个数字. 效率较低的编码需要发送 个数字才能识别错误, 发送 个数字才能纠正错误. 但是, 如果你使用经过给定点的多项式插值方法, 你只需要 个数字就能查找错误, 发送 个数字就能纠正错误. （你可以添加更多点来识别和纠正更多潜在错误. ）随着信息长度的增加, 两种编码之间的效率差异变得越来越明显.

更高效的编码方式就称为 Reed-Solomon 编码. 自 1960 年推出以来, 数学家取得了很大的突破, 开发出了能够更高效地纠正更多错误的算法. “这非常优雅、简洁、具体, ”多伦多大学的数学家兼计算机科学家 Swastik Kopparty 说. “可以在半小时内教给二年级的本科生. ”

Reed-Solomon 码在电子存储和传输信息方面特别有用. 但同样的概念在密码学和分布式计算中也至关重要.

以秘密共享为例：假设你想在多方之间分发一个秘密, 这样任何一方都无法访问整个秘密, 但各方可以一起访问（比如加密密钥或导弹发射编码）. 你将数字编码到多项式中, 在预先确定的一组点上计算该多项式, 并将每个结果分发给不同的人.

最近, Reed-Solomon 编码已应用于云计算和区块链技术等领域. 假设你需要执行一个对你的笔记本来说过于复杂的计算, 因此你使用大型计算集群来运行它——但你现在需要验证返回的计算结果是否正确. 如果集群没有正确执行计算, 它很可能无法提供这些信息. 但Reed-Solomon 码允许你请求额外的信息, “这就像魔法一样, ”法国雷恩数学研究所的研究员 Jade Nardi 说. “这个过程真的非常奇妙, 它依赖于这些编码的方式让人惊叹. ”

但是Reed-Solomon编码也有一个重要的限制. 它们的构造方式使得你只能在一组固定（通常相对较小）的值上评估多项式. 也就是说, 你只能使用一组特定的数字来编码你的消息. 该集合的大小, 或称为字母表的大小, 反过来限制了你可以发送消息的长度——而且, 字母表越大, 解码这些消息所需的计算能力就越高.

因此, 数学家们开始寻找一种更优的编码方式.

未来编码

一种更通用、更强大的编码方式将允许你在不增加字母表大小的情况下存储或发送更长的消息. 为此, 数学家们设计了涉及通过给定点插值函数的编码方式——这个函数位于一个与更复杂曲线相关的特殊空间中. 这种所谓的代数几何编码“突然出现, 并且它们比我们知道的任何其他 [使用较小字母表] 编码都要好, ”Kopparty 说道, “这种方法打败了所有现有方法, 这真是个巨大的惊喜. ”

只是有一个问题. 实际上, 实现 Reed-Solomon 码比实现代数几何编码要容易得多. 密码学家Simon Abelard说：“代数几何编码是最先进的技术, 但仍在研究中, 无法真正将其变成实用的东西. 它涉及相当抽象的数学, 很难在计算机上处理这些编码. ”

目前, 这并不令人担忧：在现实应用中, Reed-Solomon 码及其相关形式的纠错已经足够. 但未来可能并非如此. 例如, 如果未来出现强大的量子计算机, 它们将能够破解现有的加密协议^[2]. 因此, 研究人员一直在寻找能够抵御量子攻击的方案. 其中一个最有力的竞争者将需要比 Reed-Solomon 码更强的编码. 某些版本的代数几何码可能正好能起作用. 其他研究人员对代数几何码在云计算中的作用也充满希望.

但即使没有这些潜在的应用, “在数学史上, 有时你会发现一些现在没有应用的新事物, ”荷兰埃因霍芬理工大学研究代数几何码的研究员Elena Berardini说道, “但在年后, 你会发现它可能对某些完全意想不到的事情有用”——就像插值这个古老的问题本身一样.

注释

1. [1]Jordana Cepelewicz. Old Problem About Mathematical Curves Falls to Young Couple. https://www.quantamagazine.org/old-problem-about-algebraic-curves-falls-to-young-mathematicians-20220825/  

2. [2]Jordana Cepelewicz. ‘Post-Quantum’ Cryptography Scheme Is Cracked on a Laptop.https://www.quantamagazine.org/post-quantum-cryptography-scheme-is-cracked-on-a-laptop-20220824/  

3. [3]原文发布于 Quanta Magazine