作者 | Jordana Cepelewicz
译者 | 万物有数
原载于 | Quanta Magazine
引言
给定空间中的一组点, 你能找到一条经过所有点的曲线吗？这个问题是数学中插值问题的一个版本, 几千年来一直吸引着数学家的注意力. 2022年, 数学家埃里克·拉尔森（Eric Larson）和伊莎贝尔·沃格特（Isabel Vogt）彻底解决了这个问题 [1].
然而, 尽管这项工作在纯数学家当中引起了极大的轰动, 但插值的实际影响却远远超出了几何学的范畴. 插值在存储和传输电子数据、构建密码方案等方面都起着关键作用. 为什么你刮花了一张 CD 仍然能听到音乐, 弄脏了二维码仍然能扫描？ 为什么像“旅行者”计划这样的太空任务能够将清晰的数字图像传回地球？ 为什么即使其中一台计算机发生故障, 一组计算机也能执行复杂的计算?
这些应用全都依赖于一种极其优美且概念简单的插值方法：Reed-Solomon 码, 以及在此基础上构建的其他编码.
Reed-Solomon 码
假设你要发送一条由两个数字组成的消息：
这种编码最简单的例子是多次传输同一条消息. 为了让接收者识别是否发生了错误, 可以将相同的消息传输两次：
但这种纠正错误的方法效率极低. 这里有一个更聪明的方法：将信息编码为曲线, 并发送足够的信息让接收者重建该曲线.
在我们传输
为了避免错误, 你再次添加了额外的信息. 在这里, 你发送与另一个预定的
信息量越大, 优势就越大. 假设你要发送一条较长的信息——
更高效的编码方式就称为 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说道, “但在
脚注
- 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/ ⬅
- 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/ ⬅
- 原文发布于 Quanta Magazine