椭圆曲线——身处红尘的世外高人

文章来源：科普最前沿

当第一次看到“椭圆曲线”这个词时，相信许多读者会和年轻时的小编（简称小小编）一样对其视而不见——椭圆不就是把圆拉长嘛，严格定义也在高中的时候就学过了；至于曲线就更简单了，连三岁小孩都会画，那椭圆曲线有什么神秘的！

不过有密码学基础的读者会发现此事并没那么简单。在当今的通信安全领域，被使用最多的两大非对称加密体系（也就是需要用到公钥和私钥两个密钥的体系），一个是 RSA 体系，而另一个就是椭圆曲线加密体系（简称 ECC，Elliptic Curve Cryptography）。令人惊奇的是，相对于依赖于对大整数进行因子分解的 RSA 体系而言，椭圆曲线加密的加密效率比 RSA 高很多——如果使用最普通的，长度 128 位的公钥（AES-128）对某段信息进行加密，RSA 的加密速度比椭圆曲线慢 10 倍，更何况这个差距还会随着公钥长度的增加而呈指数增加！

图一、RSA 和 ECC 算法及其破解方法对比，其中 c 是小于 2 的一个常数。一般说来，由于椭圆曲线选择的多样性， ECC 算法的破解难度比 RSA 更大。我们后面还会继续讨论这两种加密算法。

事实上，椭圆曲线在计算机科学中的应用其实只是小打小闹——他们对数学家们的吸引力其实远胜于计算机科学家！近百年来，众多深刻的数学定理、猜想都和椭圆曲线直接相关，比如著名的费马大定理：

定理 1（费马大定理）

当整数 n > 2 时，关于 a, b, c 的方程 无非零整数解。

再比如稍深奥些的千禧年七大数学猜想之一的 BSD 猜想（证明这个猜想就可以得到一百万美元）

猜想 1（BSD）

若 E 是一条椭圆曲线，用 N_p 表示在模掉质数 p 后，E 上有理点的个数，那么：

其中 r 叫做椭圆曲线的秩（rank），是一个和 E 有关的正整数。可以粗略理解为 E 上有理点个数的“自由度”。

此外还有许多前沿的数学定理，例如莫德尔-外尔定理（后文还会提及）、法尔廷斯定理等都和椭圆曲线直接相关，这里就不一一例举了。

我们还是先回顾一下老少咸宜的费马大定理——尽管其描述只需涉及小学数学知识，但自提出以后 300 多年来都没能被攻克，直到 1994 年才被英国数学家怀尔斯完全证明。怀尔斯也因此获得沃尔夫数学终身成就奖（本来要被颁发菲尔兹奖的，可惜当时他已经 41 岁了，超过了菲尔兹奖 40 岁的年龄上限），因而可以说，是椭圆曲线成就了怀尔斯。

那么椭圆曲线到底是何方神圣？在平平无奇外表下面，它又隐藏着怎样不为人知的秘密呢？

一、曲线上的点居然可以相加？！

话不多说，我们先来看看椭圆曲线的庐山真面吧：

椭圆曲线的图像会随着 A 和 B 变化而变化：

图二、两条不同椭圆曲线的图像：左边是连续的，右边形成了一个孤立的小岛。其判断准则是 y=0 时 x 有一个解（左图）还是三个解（右图），也就是判别式 4a^3 + 27b^2 是正还是负。图片来自文献 [1] 6.1 节

许多读者看到这里可能会大跌眼镜——这不就是个三次方程吗，我行我上，何必让人类最顶尖的数学家费那么多心思！然而这个简单的方程背后的秘密，却需要从它的有理数解开始，也就是 x 和 y 都是有理数的情况。假设我们的椭圆曲线是 E, 数学家们发现 E 上所有有理点之间都可以定义一种加法——假设 P、Q 是 E 上两个有理点，那么定义 P + Q 为直线 PQ 与 E 的交点 R 关于 x 轴的翻折 R'：

图三、R' := P + Q 的定义。图片来自文献 [1] 6.1 节

如果要把 P 和自身相加怎么办呢？没错，只需要把直线 PQ 替换为经过 P 的 直线即可：

图四、想把自己和自己相加？画一条切线就好！图片来自文献 [1] 6.1 节

可以验证，这样定义的加法满足交换律和分配率！也就是对于 P, Q, R ∈ E，有 P + Q = Q + P，且 (P + Q) + R = P + (Q + R)， 大家不妨自己动手试试看（分配率的证明计算量比较大）。此外，我们把一个点 P 的相反值 -P 定义为 P 关于 x 轴的对称，并定义 P + (-P) = O 为 “零点”，且规定对于 Q ∈ E， O + Q = Q。

这时候，有一些群论背景的读者可以看出，椭圆曲线上的所有有理点的集合在这种定义下构成了一个加法群（additive group），换言之，该集合：1) 对加法、减法封闭，2) 存在零点 O 使得对于 P ∈ E， O + P = P 且 3) 对于 P ∈ E，存在 P' （= -P） 使得 P' +P = O。更加有趣的是，英国数学家莫德尔在 1922 年证明，这个加法群是有限生成的，也就是说我们可以找到有限个点 {P1, ..., Pn}，使得 E 上所有有理点都是 {P1, ..., Pn} 的线性组合。这个定理就是著名的莫德尔定理（Modell Theorem）。

当然了，数学家们可是很有野心的，他们才不会满足于莫德尔定理的结论。他们喜欢研究更加一般性的问题——如果我们不仅考虑椭圆曲线，而考虑一般代数曲线（高次多项式方程组的解），结论会一样吗？如果不仅考虑有理点，而是考虑一般数域上的点，又会怎样呢？而这个一般化的结论，便是本文开头提到，于 1928 年被德国数学家外尔证明的的莫德尔-外尔定理。值得一提的是，尽管外尔的名字不为很多人所知，但基于他在数论、数理逻辑、微分几何、代数几何、乃至理论物理等诸多领域的贡献和影响力，小编认为他和希尔伯特、格罗腾迪克一样，可以称得上 20 世纪最伟大的数学家之一。

二、在椭圆曲线上做因数分解——一个比大整数分解还难的问题

尽管椭圆曲线是一个有趣的数学课题，但数学圈以外几乎没人知道它的存在，直到 1985 年椭圆曲线加密算法的横空出世。

想必许多读者已经听说过，现代密码学体系的安全性取决于大整数分解问题的困难性。不过具体细节如何呢？这得从 RSA 非对称加密系统说起。

密码学出现的目的在于保证安全的信息沟通，而非对称加密体系是指在加密和解密过程中需要使用不同密钥的体系。例如校花小红被众多男生暗恋，这些男生都想给小红寄情书，但他们不想让自己的情书被除了小红之外的人看到，该怎么办呢？于是小红想出了一个办法——她给所有暗恋者发出一个相同的大整数 n = pq（p 和 q 也都是差不多大小的质数）和另一个与 (p-1)*(q-1) 互质的随机整数 e，这个大整数称为公钥（public key），自己保留 p 或 q，称之为私钥或密钥（private key）。这就是 RSA 非对称加密体系的组成部件，它的主要算法如下（需要一些同余计算的知识，不感兴趣的读者可以直接跳过）：

图五、RSA 加密与解密算法。其中 m_A, m_B 表示被编码后的未加密信息，c_A, c_B 表示加密信息，e 尽管随机，但一般也会取得比较大。如果只知道 N 而不知道 p 和 q 的话，是没法算出 (p-1)*(q-1) 的，因此无法解密。

非对称加密体系的好处在于，只要知道公钥的男生，就可以通过公钥给小红发送加密情书，但只有拥有私钥的小红才能将这些加密情书解密。此外，出了小红，唯一能破解加密情书的方法就是求出大整数 n 的其中一个质因数 p 和 q——这便是 RSA 非对称加密算法的核心所在。

要使 RSA 安全，那么公钥 n 就必须特别大，而且 n 不能随便取，它必须是两个量级差不多的质数之积。这让校花小红感到有些繁琐。不过当小红读到本文第一章所提到的椭圆曲线时，突然想到一个问题：

如果给定有理数域上的一条椭圆曲线 E 和它上面的一个有理点 P，又已知 Q 是 P 的倍数，也就是 Q = P + P + ... +P （n 个 P），有没有一个方法可以计算出这个倍数 n 呢？

事实上，上面这个问题就是椭圆曲线上的离散对数问题（The elliptic curve discrete logarithm problem，简称 ECDLP），这个问题正是椭圆曲线加密（ECC）算法的核心所在。不过在密码学领域，由于所有信息都被编码成了（二进制）整数，我们使椭圆曲线上的点的坐标都变成整数，因此人们不再使用有理数域上的椭圆曲线，而使用有限域（Finite Field）上的椭圆曲线 E_p。这里的有限域 F_p 由 p 个元素构成，我们可以单纯理解为任何一个质数 p 的同余类集合，也就是任一整数除以 p 后的余数集合 {0, 1, 2, ..., p-1}。

另一个使用有限域 F_p 代替有理数域的原因是，一旦 p 确定以后，椭圆曲线 E_p 上点（注意此时椭圆曲线在 F_p 上定义，所以 x, y 取值都在 F_p 中）的个数都满足一个条件：

定理 2（Hasse，文献 [2] 定理 2.5.11）：

如果 N_p 表示椭圆曲线 E_p 上点的个数，那么 。

上面这个定理告诉我们，当质数 p 比较大时，E_p 上点的个数不会太少也不会太多，因此我们不需要太担心如何选取 p 的问题。下面是椭圆曲线加密算法的主要步骤（可直接跳过，不影响阅读）：

图六、RSA 加密与解密算法。

由于在椭圆加密算法中，p 取值并不需要太大就能保证良好的安全性，它生成的公钥长度比同安全级别的 RSA 算法短很多，因此加密效率也会高很多。不过椭圆曲线加密的缺点在于，由于涉及到比较高深的数学知识，实现起来比较复杂。

正如本文开头所述，在常规（非量子）计算机上，破解 RSA 和椭圆曲线加密的速度至少都是随着公钥长度呈亚指数级别增加的。破解 RSA 的最快方法是筛法（这里的筛法和陈景润的哥德巴赫猜想 2+1 情形不一样，注意不要弄混了），有本科数论背景的读者可以参考文献 [3]；破解椭圆加密算法的最快方法是指标算数法（index calculus），不过此前还需要运用算数代数几何里的技术进行化简，故此处略去，有兴趣的读者可以参考文献 [1] 的 6.7 - 6.9 节。

三、数学分支间的伯乐相马——椭圆曲线和复变函数

尽管到此为止，我们已经对椭圆曲线的数学性质和实际应用有不少了解了，但也许好奇心重的你还会有一个疑问——为什么椭圆曲线这种看起来只需要初中数学知识就能理解的学科，直到 20 世纪之后才受到人们的重视呢？答案只有一个：椭圆曲线原本只是一匹才美不外现的千里马，是复变函数这个伯乐把它挖掘了出来。

例如费马大定理的最终获证，很关键的一步在于发现，方程 a^n + b^n = c^n （n 是奇质数）的解如果存在，那么椭圆曲线 y^2 = x(x-a^n)(x+b^n) 便无法与具有某种不变性的复变函数产生对应（该结论在 1987 年被法国数学家，菲尔兹、沃尔夫、阿贝尔三奖得主塞尔证明）。但另一方面，英国数学家怀尔斯在 1994 年证明很多椭圆曲线（包括 y^2 = x(x-a^n)(x+b^n)）都可以和这种具有不变性的复变函数产生对应，故而证明了椭圆曲线 y^2 = x(x-a^n)(x+b^n) 不存在（图像是空集），从而 a^n + b^n = c^n （n 是奇质数）无解。

上面我们提到的“具有某种不变性的复变函数”，就是在数论领域大名鼎鼎的的模函数（Modular Function）。模函数定义很简单，它的定义域是复数域的上半平面（虚部大于 0），并且它满足的不变性是：

而怀尔斯之所以能得沃尔夫奖，并不仅仅在于他证明了费马大定理，还在于他证明了一个困扰人们近百年猜想的重要特例，费马大定理只是这个特例的推论而已。而这个猜想就是著名的谷山志村猜想（Taniyama–Shimura conjecture） ——

猜想 2：

对于每一条有理数域上的椭圆曲线 y^2 = x^3 + Ax +B, 存在相同等级（这个概念定义相对繁琐，可参考 [2] 定义 4.2.1）的模函数 f(z) 和 g(z)，使得 f(z)^2 = g(z)^3 + A*g(z) + B。

值得一提的是，怀尔斯证明的只是谷山志村猜想的一个特例。谷山志村猜想的完整版直到 2001 年才被完全证明，因此谷山志村猜想已经变成了谷山志村定理，又名可模化定理（Modularity theorem）。此外，可模化定理又只是另一个数学界中“大统一理论”的特例，当今众多著名数学家，包括许多菲尔兹奖得主的主要研究目标就是这个它。这个大统一理论就是朗兰兹纲领（Langlands program），它在数学界的地位就好比理论物理学中，一个能够一统量子力学和广义相对论的理论的地位。

图七、可模化定理（谷山志村定理）只是朗兰兹纲领的一个特例

尽管朗兰兹纲领不属于千禧年七大难题，但它得到的关注丝毫不亚于本文开头提到的 BSD 猜想。最近几年这两个猜想的研究都在年轻数学家的推动下取得了很大的进展——关于 BSD 猜想，2014 年菲尔兹奖得主，印度裔数学家巴尔加瓦与中国数学家张伟等人合作证明该猜想对至少 66% 椭圆曲线成立 [4]；关于朗兰兹纲领，2018 年菲尔兹奖得主，德国数学家舒尔茨和合作者于今年把局部版本的"朗兰兹纲领“”和几何实例联系了起来，有望开创该领域的一个新研究方向 [5]。

图八、三位 40 岁上下的数学家——巴尔加瓦、张伟和舒尔茨（从左到右）

四、总结

在这篇文章里，小编粗略地介绍了许多关于椭圆曲线的硬核知识，包括它的基本定义、一些有趣的性质、同前沿数学领域的联系、以及在密码学领域的应用等等。我们可以看到，尽管椭圆曲线是一个中学生都能理解的概念，但整个 20 世纪尤其是 1950 年以后的数学发展，都受到了它的强力推动，这种推动甚至延续至今。

许多人认为数学是一门很难的学科，然而小编一直有个信念——数学的本质一定是简单而优美的。这种本质可以被很多简单而优美的事物激发出来，比如本文中的椭圆曲线与密码学，比如近几十年来组合数学领域涌现的各种有趣问题，再比如小编以前提过的群论与对称性、微分方程与化学反应、动力系统与太阳系的稳定性、代数拓扑与地球的形状等等。如果只是为了刻意解决一些本已复杂的人造问题，而去创造更加抽象晦涩的概念，小编认为这样的数学不是我们应该追求的数学。

最后我们再来谈谈椭圆曲线在密码学里的地位。尽管椭圆曲线加密算法自提出后就受到了非常多的关注，相关理论也被堆积地越来越多，但它和 RSA 算法一样存在一个缺陷——可以被量子计算机破解（基于一种叫做 “量子傅里叶变换” 的方法，具体细节跳过）。因此上世纪 90 年代开始，基于格的加密算法（Lattice-based encryption）开始受到重视。虽然直到今天，并没有已知量子算法能够破解基于格的加密算法，但该算法却不为许多数学家所知，这也许是因为它的数学基础是比椭圆曲线理论更简单的组合数学，多数数学家对它看不上眼（关于该算法的更多信息，可参考文献 [1] 的第七章）。这个例子再次证明，复杂的理论和概念并不见得是最好的，从最简单和优美的身边现象入手，或许我们的科学发展会更加迅速。

参考文献：

[1] Hoffstein, J., Pipher, J.C., Silverman, J.H., 2014. An introduction to mathematical cryptography, New York: Springer.

[2] Lozano-Robledo, A. 2015. Elliptic curves, modular forms, and their l-functions. Providence, RI: American Mathematical Society.

[3] Pomerance, C. 2009. A Tale of Two Sieves. Biscuits of Number Theory, 85-104. doi:10.1090/dol/034/15

[4] https://arxiv.org/abs/1407.1826

[5] https://arxiv.org/abs/2102.13459

编辑：南方的猫