MathLabs

算术与数论

椭圆曲线

光滑三次曲线 y2=x3+ax+by^2=x^3+ax+b,其上的点在几何弦-切线法则下构成一个阿贝尔群,把经典的丢番图几何与模形式、椭圆曲线密码学以及尚未解决的 Birch 与 Swinnerton-Dyer 猜想联系在一起。

直观把点变成群的曲线

考虑一条光滑三次曲线 E:y2=x3+ax+bE: y^2 = x^3 + ax + b——它的形状看起来像一条懒洋洋的S形曲线,或者(取决于 a,ba,b)由一条波浪形分支再加上一个分离的卵形圈组成。在曲线上任取两点 PP 和 QQ。代数学中一个引人注目的事实保证:过 PP 与 QQ 的直线恰好(计重数)再与曲线多交于一点,因为把直线方程代入三次式后会剩下一个 33 次多项式,而它的三个根中已有两个被 PP 与 QQ 固定。把第三个交点记作 RR。现在把 RR 关于 xx 轴作镜像:镜像点 −R-R 被定义为和 P+QP + Q。这个纯粹几何的处方——画一条弦、找到第三个交点、把它翻转过去——就把曲线上的点变成了一个交换群,其中无穷远点 O\mathcal{O}(每条竖直线都与曲线相交于此)扮演单位元 00 的角色。

例题: 手动相加两个有理点

在曲线 E:y2=x3−36xE: y^2 = x^3 - 36x 上,验证 P=(−3,9)P = (-3, 9) 与 Q=(−2,8)Q = (-2, 8) 都是有理点,然后用弦的作图法计算 P+QP + Q。

解答

首先,(−3)3−36(−3)=−27+108=81=92(-3)^3 - 36(-3) = -27 + 108 = 81 = 9^2 且 (−2)3−36(−2)=−8+72=64=82(-2)^3-36(-2) = -8+72 = 64 = 8^2,故两点都在 EE 上(这是 n=6n=6 的同余数曲线,与面积为 66 的 33-44-55 直角三角形相关)。过 PP 与 QQ 的弦斜率为 λ=8−9−2−(−3)=−11=−1\lambda = \frac{8-9}{-2-(-3)} = \frac{-1}{1} = -1。第三个交点的坐标 xx 为 x3=λ2−xP−xQ=1−(−3)−(−2)=6x_3 = \lambda^2 - x_P - x_Q = 1 - (-3) - (-2) = 6,坐标 yy 为 y3=λ(xP−x3)−yP=(−1)(−3−6)−9=9−9=0y_3 = \lambda(x_P - x_3) - y_P = (-1)(-3-6) - 9 = 9 - 9 = 0。于是直线与 EE 的另一个交点是 (6,0)(6,0)——由于该点已经落在 xx 轴上,它自身的镜像就是它本身,故 P+Q=(6,0)P + Q = (6, 0)。验算:63−36×6=216−216=0=026^3 - 36\times 6 = 216 - 216 = 0 = 0^2,确认 (6,0)∈E(6,0) \in E。

三次函数 $y = x^3 - x + 1$ 的二维图像:一条从左下方延伸到右上方的单一S形曲线,在 $x=-0.6$ 附近有一个局部极大值,在 $x=0.6$ 附近有一个局部极小值,在 $x \approx -1.32$ 附近与 $x$ 轴恰好相交一次。
此图仅绘制了魏尔斯特拉斯方程 y2=x3−x+1y^2 = x^3 - x + 1 右端的三次多项式 y=x3−x+1y = x^3 - x + 1——而非椭圆曲线本身。由于这个三次多项式只有一个实根且没有重根,实际曲线 y2=x3−x+1y^2 = x^3-x+1 只有一条无界的波浪形分支(没有分离的卵形圈),并且是非奇异的。

大学魏尔斯特拉斯形式、判别式与非奇异性

定义: 椭圆曲线(短魏尔斯特拉斯形式)

在特征 ≠2,3\neq 2, 3 的域上(例如 Q\mathbb{Q}、R\mathbb{R},或 p>3p > 3 的有限域 Fp\mathbb{F}_p),任意具有有理点的光滑平面三次曲线都可以化为短魏尔斯特拉斯形式 E:y2=x3+ax+bE: y^2 = x^3 + ax + b(其中 a,ba, b 是该域中的某些常数)。椭圆曲线是这样一条曲线再加上无穷远处的额外点 O\mathcal{O},并要求它非奇异:曲线上不存在使 F(x,y)=y2−x3−ax−bF(x,y) = y^2 - x^3 - ax - b 的两个偏导数同时为零的点(奇异点会是自相交的结点或尖点,在那里弦-切线的构造法则会失效)。

Δ=−16(4a3+27b2)\Delta = -16(4a^3 + 27b^2)

曲线 E:y2=x3+ax+bE: y^2 = x^3+ax+b 非奇异当且仅当判别式 Δ=−16(4a3+27b2)\Delta = -16(4a^3+27b^2) 不为零,而这又等价于三次多项式 x3+ax+bx^3+ax+b(在代数闭包中)有三个互异的根。

为什么成立?

三次多项式出现重根的点 (x0,0)(x_0, 0) 恰好就是曲线收缩成尖点或自相交的地方,因为那里切线方向不确定——这正是会破坏弦-切线群律的几何缺陷。

证明

点 (x0,y0)(x_0,y_0) 是奇异点当且仅当 F=y2−x3−ax−b=0F=y^2-x^3-ax-b=0、∂F/∂y=2y0=0\partial F/\partial y = 2y_0 = 0、∂F/∂x=−3x02−a=0\partial F/\partial x = -3x_0^2-a=0 同时成立。第二式迫使 y0=0y_0=0,故 x0x_0 必须是 x3+ax+bx^3+ax+b 的根;第三式迫使 3x02+a=03x_0^2+a=0,即 x0x_0 也是导数 3x2+a3x^2+a 的根。一个多项式与其导数有公共根,恰好发生在该多项式的重根处,故 EE 奇异当且仅当 x3+ax+bx^3+ax+b 有重根。既约三次式 x3+ax+bx^3+ax+b 的经典判别式为 −4a3−27b2-4a^3-27b^2,恰好在三次式有重根时为零;乘以规范化常数 −16-16 得 Δ=−16(4a3+27b2)\Delta = -16(4a^3+27b^2),所以 EE 非奇异当且仅当 Δ≠0\Delta \neq 0。

几何上的弦-切线处方转化为明确的代数公式。对于满足 x1≠x2x_1 \neq x_2 的相异两点 P=(x1,y1)P=(x_1,y_1)、Q=(x2,y2)Q=(x_2,y_2),弦的斜率为 λ=y2−y1x2−x1\lambda = \frac{y_2-y_1}{x_2-x_1};对于加倍一点 P=(x1,y1)P=(x_1,y_1)(其中 y1≠0y_1 \neq 0),PP 处切线的斜率为 λ=3x12+a2y1\lambda = \frac{3x_1^2+a}{2y_1}(由 y2=x3+ax+by^2=x^3+ax+b 隐函数求导得到)。这两种情形下,和的坐标都由下面同样的两个公式给出。若把 P=(x1,y1)P=(x_1,y_1) 与 −P=(x1,−y1)-P=(x_1,-y_1) 相加,过它们的竖直线只在 O\mathcal{O} 处与 EE 相交,故 P+(−P)=OP+(-P)=\mathcal{O},这与群的单位元公理相符。

x3=λ2−x1−x2,y3=λ(x1−x3)−y1,P+Q:=(x3,−y3)x_3 = \lambda^2 - x_1 - x_2, \qquad y_3 = \lambda(x_1-x_3) - y_1, \qquad P+Q := (x_3, -y_3)

由于当 p>3p>3 时 Fp\mathbb{F}_p 的特征为 ≠2,3\neq 2,3,当 EE 模素数 pp 约化后,同样的加法与加倍公式原封不动地适用,使约化后的曲线 E(Fp)={(x,y)∈Fp2:y2=x3+ax+b}∪{O}E(\mathbb{F}_p) = \{(x,y) \in \mathbb{F}_p^2 : y^2=x^3+ax+b\} \cup \{\mathcal{O}\} 具有有限阿贝尔群的结构。这正是椭圆曲线密码学始终使用的场景,由此产生一个显然的问题:#E(Fp)\#E(\mathbb{F}_p) 到底有多大?

定理: 哈塞界

对于有限域 Fp\mathbb{F}_p(pp 为素数)上的椭圆曲线 EE,其点数满足 ∣#E(Fp)−(p+1)∣≤2p|\#E(\mathbb{F}_p) - (p+1)| \le 2\sqrt{p}。

为什么成立?

量 ap:=p+1−#E(Fp)a_p := p+1-\#E(\mathbb{F}_p) 度量了朴素猜测(随机三次式应有约 pp 个解再加上无穷远点)的“误差项”;哈塞界表明这个误差绝不会超过约 2p2\sqrt{p},相比大小为 pp 的平凡界,这是一个惊人地小的偏差,也正因如此 #E(Fp)\#E(\mathbb{F}_p) 才能作为密码学构造中可靠、可预测的群阶使用。

证明

考虑弗罗贝尼乌斯自同态 φ:E(Fp‾)→E(Fp‾)\varphi: E(\overline{\mathbb{F}_p}) \to E(\overline{\mathbb{F}_p}),φ(x,y)=(xp,yp)\varphi(x,y) = (x^p, y^p)。它的不动点恰好是 E(Fp)E(\mathbb{F}_p),并且可以证明 #E(Fp)=deg⁡(φ−1)=p+1−t\#E(\mathbb{F}_p) = \deg(\varphi - 1) = p+1-t,其中 t=φ+φ^t = \varphi + \hat\varphi 是弗罗贝尼乌斯作用在自同态环上的迹。EE 的自同态上的次数映射是一个正定的整值二次型(对一切整数 m,nm,n 满足 deg⁡(mφ+n)≥0\deg(m\varphi+n) \ge 0,且仅当 mφ+n=0m\varphi+n=0 时取等),而 deg⁡φ=p\deg\varphi = p。将 deg⁡(mφ+n)=m2p+mnt+n2≥0\deg(m\varphi+n) = m^2 p + mnt + n^2 \ge 0 作为关于 m,nm,n 的二次型展开,其判别式必须非正:t2−4p≤0t^2 - 4p \le 0,即 ∣t∣≤2p|t|\le 2\sqrt p。由于 #E(Fp)−(p+1)=−t\#E(\mathbb{F}_p) - (p+1) = -t,这正是所要证明的界。

ap:=p+1−#E(Fp),∣ap∣≤2pa_p := p + 1 - \#E(\mathbb{F}_p), \qquad |a_p| \le 2\sqrt{p}
一个圆周上均匀分布着编号从 $0$ 到 $16$ 的 $17$ 个点,用直线弦把每个点 $x$ 与点 $3x \bmod 17$ 相连,形成相互交叉线段构成的星形图案。
此小工具并非椭圆曲线的图像;它展示的是 E(F17)E(\mathbb{F}_{17}) 上点坐标所处的模 1717 环境算术,在圆周上画出 1717 个点,并绘出映射 x↦3x mod 17x \mapsto 3x \bmod 17 的弦。E(F17)E(\mathbb{F}_{17}) 上任意一点的 xx 坐标和 yy 坐标都是这 1717 个剩余之一。

例题: 计算小有限域上曲线的点数

设 F5\mathbb{F}_5 上的曲线 E:y2=x3+x+1E: y^2 = x^3+x+1。通过直接枚举计算 #E(F5)\#E(\mathbb{F}_5),并验证它满足哈塞界。

解答

对每个 x∈{0,1,2,3,4}x \in \{0,1,2,3,4\},计算 x3+x+1 mod 5x^3+x+1 \bmod 5 并检查它是否为模 55 的平方数(模 55 的平方数集合为 {0,1,4}\{0,1,4\},因为 02=0,12=1,22=4,32=4,42=10^2=0,1^2=1,2^2=4,3^2=4,4^2=1):x=0⇒1x=0 \Rightarrow 1(平方数,y=±1y=\pm 1,22 个点);x=1⇒3x=1 \Rightarrow 3(非平方数,00 个点);x=2⇒11≡1x=2 \Rightarrow 11\equiv 1(平方数,y=±1y=\pm 1,22 个点);x=3⇒31≡1x=3 \Rightarrow 31\equiv 1(平方数,y=±1y=\pm 1,22 个点);x=4⇒69≡4x=4 \Rightarrow 69\equiv 4(平方数,y=±2y=\pm 2,22 个点)。由此得到 2+0+2+2+2=82+0+2+2+2=8 个仿射点,再加上无穷远点,故 #E(F5)=9\#E(\mathbb{F}_5) = 9。验证哈塞界:∣9−(5+1)∣=∣9−6∣=3|9-(5+1)| = |9-6| = 3,而 25≈4.472\sqrt{5}\approx 4.47,故 3≤4.473 \le 4.47 成立。

进阶秩、挠元与 E(Q)E(\mathbb{Q}) 的结构

在 Q\mathbb{Q} 上,只要群 E(Q)E(\mathbb{Q}) 含有一个无限阶的点,它就是无限群;亨利·庞加莱在1901年的论文中首次提出:需要多少个有理点才能通过弦与切线生成所有其他点?路易·莫德尔在1922年借助改进的费马无穷递降法回答了这个问题,而安德烈·韦伊在其1929年的博士论文中把该结果推广到了任意数域上的阿贝尔簇。

对于 Q\mathbb{Q} 上的椭圆曲线 EE,有理点群 E(Q)E(\mathbb{Q}) 是有限生成的:E(Q)≅Zr⊕E(Q)torsE(\mathbb{Q}) \cong \mathbb{Z}^r \oplus E(\mathbb{Q})_{\mathrm{tors}},其中某个整数 r≥0r \ge 0 称为秩,而 E(Q)torsE(\mathbb{Q})_{\mathrm{tors}} 是一个有限阿贝尔群。

为什么成立?

这个定理是群律带来的算术成果:无论有理点集合看起来多么复杂,它总是由有限多个“种子”点——一个有限生成集——所控制,从这些点出发反复用弦-切线加法就能得到每一个其他的有理点。

证明

证明结合了两个要素。弱莫德尔–韦伊定理:证明 E(Q)/2E(Q)E(\mathbb{Q})/2E(\mathbb{Q}) 是有限群,方法是(通过伽罗瓦上同调,利用三次式的根 eie_i 对应的 22-下降映射 P↦(x(P)−e1,x(P)−e2,x(P)−e3)P \mapsto (x(P)-e_1, x(P)-e_2, x(P)-e_3))把它嵌入由相关数域的理想类群与单位群构造出的群中,而这两者都是已知有限的。高度下降:给每个点赋予一个典范高度 h^(P)≥0\hat h(P) \ge 0,这是度量算术复杂度的实数值量,满足 h^(2P)=4h^(P)\hat h(2P) = 4\hat h(P),且高度低于任何给定界的点只有有限多个。把 E(Q)/2E(Q)E(\mathbb{Q})/2E(\mathbb{Q}) 的有限个陪集代表元,与(通过高度的平行四边形法则)反复把任意点的高度减半最终会落入有界高度区域这一事实结合起来,就说明每个点都是有限个代表元与有限个有界高度点的 Z\mathbb{Z} 组合——因此 E(Q)E(\mathbb{Q}) 是有限生成的。

对于 Q\mathbb{Q} 上的椭圆曲线 EE,其挠子群 E(Q)torsE(\mathbb{Q})_{\mathrm{tors}} 恰好同构于以下 1515 个群之一:循环群 Z/NZ\mathbb{Z}/N\mathbb{Z}(N=1,…,10N=1,\dots,10 或 N=12N=12),或者群 Z/2Z⊕Z/2NZ\mathbb{Z}/2\mathbb{Z}\oplus\mathbb{Z}/2N\mathbb{Z}(N=1,2,3,4N=1,2,3,4);不会出现其他有限阿贝尔群。

为什么成立?

这是一个引人注目的刚性论断:在抽象上可能存在无穷多种有限阿贝尔群之中,作为有理椭圆曲线挠元实际出现的却只有这 1515 种——比如阶为 1111 或 1616 的挠子群根本不可能出现。

证明

马祖尔在1977年的证明把 EE 上存在阶恰为 NN 的有理点这一事实,转化为在模曲线 X1(N)X_1(N)(它对 PP 的阶为 NN 的对 (E,P)(E, P) 进行分类)上存在非尖点有理点。该策略研究相关模曲线 X0(N)X_0(N) 的雅可比簇 J0(N)J_0(N),以及作用其上的爱森斯坦理想 I\mathcal{I}——即由素数 ℓ∤N\ell \nmid N 对应的 Tℓ−ℓ−1T_\ell - \ell - 1 在 Hecke 代数中生成的理想。通过分析 J0(N)J_0(N) 的爱森斯坦商及其模辅助素数的约化,马祖尔证明:对于不在允许列表中的 NN,X1(N)(Q)X_1(N)(\mathbb{Q}) 只由尖点组成,因此 Q\mathbb{Q} 上任何椭圆曲线都不可能有阶恰为该值的有理点;而显式构造(例如利用曲线 y2=x3+axy^2=x^3+ax 与 y2=x3+by^2=x^3+b)则给出了实现全部 1515 个允许群的例子。

定义: jj-不变量

对于 E:y2=x3+ax+bE: y^2=x^3+ax+b,**jj-不变量**为 j(E)=1728⋅4a34a3+27b2j(E) = 1728\cdot\frac{4a^3}{4a^3+27b^2}。代数闭域上两条椭圆曲线同构当且仅当它们具有相同的 jj-不变量,因此 j(E)j(E) 是曲线形状的完整分类不变量,与用来表示它的魏尔斯特拉斯方程无关(在 Q\mathbb{Q} 上共享同一 jj-不变量但在 Q\mathbb{Q} 上不同构的曲线互称为彼此的扭曲(twist))。

由于 E(Fp)E(\mathbb{F}_p) 中的运算正向计算很快,但(对于精心选择的曲线)反向计算却极其缓慢,椭圆曲线支撑起了当今大部分公钥密码学。固定一个公开的基点 P∈E(Fp)P \in E(\mathbb{F}_p);计算 kPkP(把 PP 自身相加 kk 次,通过反复加倍可高效完成)很容易,但仅从 PP 与 Q=kPQ=kP 恢复秘密整数 kk——即椭圆曲线离散对数问题(ECDLP)——据信对于已知最好的经典算法大约需要 p\sqrt{p} 次运算,且尚未发现更快的方法。这使得 ECDSA、ECDH 等协议在相同安全强度下能使用比 RSA 短得多的密钥。

例题: 一个玩具级离散对数计算

在 F17\mathbb{F}_{17} 上的 E:y2=x3+2x+2E: y^2=x^3+2x+2 中,验证 P=(5,1)P=(5,1) 在 EE 上,然后用加倍公式计算 2P2P,以玩具规模展示椭圆曲线离散对数问题背后的运算。

解答

首先,53+2(5)+2=125+10+2=137≡1(mod17)5^3+2(5)+2 = 125+10+2=137 \equiv 1 \pmod{17},且 12=11^2=1,故 P=(5,1)∈EP=(5,1) \in E。要将 PP 加倍,切线斜率为 λ=3(5)2+22(1)=772≡92(mod17)\lambda = \frac{3(5)^2+2}{2(1)} = \frac{77}{2} \equiv \frac{9}{2} \pmod{17};由于 2×9=18≡12\times 9=18\equiv 1,22 模 1717 的逆元是 99,故 λ≡9×9=81≡13(mod17)\lambda \equiv 9\times 9 = 81 \equiv 13 \pmod{17}。接着 x3=λ2−2x1≡132−10=169−10=159≡6(mod17)x_3 = \lambda^2-2x_1 \equiv 13^2-10 = 169-10=159\equiv 6 \pmod{17},y3=λ(x1−x3)−y1≡13(5−6)−1=−14≡3(mod17)y_3 = \lambda(x_1-x_3)-y_1 \equiv 13(5-6)-1=-14\equiv 3\pmod{17},故 2P=(x3,−y3)=(6,−3)≡(6,14)(mod17)2P = (x_3,-y_3) = (6, -3) \equiv (6,14)\pmod{17}。验算:63+2(6)+2=216+12+2=230≡9(mod17)6^3+2(6)+2 = 216+12+2=230\equiv 9\pmod{17},142=196≡9(mod17)14^2=196\equiv 9\pmod{17} ✓。在这条只有 1717 个可能 xx 值的玩具曲线上,攻击者可以手动搜索 PP 的每个倍数;而实际的 ECC 使用约 256256 位的素数 pp,使得类似的搜索(≈p≈2128\approx\sqrt{p}\approx 2^{128} 步)彻底不可行。

进阶通往模形式与费马大定理的桥梁

椭圆曲线还活在另一个世界里:模形式的世界,即上半平面上高度对称的全纯函数。为 EE 赋予其哈塞–韦伊 LL-函数 L(E,s)=∏p(1−app−s+p1−2s)−1L(E,s) = \prod_p (1-a_p p^{-s}+p^{1-2s})^{-1}(由哈塞界中出现的同一个 ap=p+1−#E(Fp)a_p = p+1-\#E(\mathbb{F}_p) 构造而成),模性定理(谷山–志村–韦伊猜想)断言 L(E,s)L(E,s) 总是与某个权为 22 的模形式的 LL-函数一致。等价地,EE 通过一个在 Q\mathbb{Q} 上定义的非常值映射被模曲线 X0(N)X_0(N) 所覆盖,其中 NN 是 EE 的导子。这把每个素数 pp 处纯算术的数据 #E(Fp)\#E(\mathbb{F}_p),与单一一个高度结构化函数的傅里叶系数联系了起来——这是数学中两个乍看毫不相干的领域之间一座非凡的桥梁。EE 的 ℓ\ell-adic Tate 模上相伴的伽罗瓦表示(由埃瓦里斯特·伽罗瓦开创的群论思想构造而成)正是这一“模性”所断言的对象。

Q\mathbb{Q} 上任意椭圆曲线 EE 都是模的:存在一个在 Q\mathbb{Q} 上定义的非常值态射 X0(N)→EX_0(N) \to E,其中 NN 是 EE 的导子;等价地,L(E,s)L(E,s) 等于 Γ0(N)\Gamma_0(N) 上某个权为 22 的新形式的 LL-函数。

为什么成立?

模性把每一条椭圆曲线都变成了乔装的模形式,将模形式可用的强大解析工具(解析延拓、函数方程)转移到椭圆曲线上;而对费马大定理而言至关重要的是,这意味着不可能是模的曲线根本不存在。

证明

怀尔斯于1994–95年证明了 Q\mathbb{Q} 上半稳定椭圆曲线的模性(最后一步——变形环与 Hecke 代数之间同构的一个数值判据,即“R=TR=T 定理”——是与理查德·泰勒共同确立的)。该策略证明了 EE 的 ℓ\ell-adic Tate 模上的伽罗瓦表示,与某个候选模形式相伴的表示,都落在同一个形变空间中;证明形变环 RR 与作用于模形式上的 Hecke 代数 TT 相重合,就迫使每一个被允许的伽罗瓦表示——尤其是 EE 的表示——都来自某个模形式。由于任何半稳定曲线就足以排除费马方程的反例(任何解 an+bn=cna^n+b^n=c^n 都会产生一条半稳定的 Frey 曲线 y2=x(x−an)(x+bn)y^2=x(x-a^n)(x+b^n),而肯尼斯·里贝特通过其1990年对 ε\varepsilon-猜想的证明已表明该曲线不可能是模的),这就证明了费马大定理。半稳定性这一限制后来被克里斯托夫·布勒伊、布赖恩·康拉德、弗雷德·戴蒙德与理查德·泰勒于2001年彻底去除,将模性推广到了 Q\mathbb{Q} 上所有椭圆曲线。

研究未解决问题:Birch 与 Swinnerton-Dyer 猜想及后量子密码学

下列魏尔斯特拉斯方程中,哪一个是奇异的(即不能定义椭圆曲线)?

对于有限域 F101\mathbb{F}_{101} 上的任意椭圆曲线 EE,下列哪个论断必然成立?

根据马祖尔挠元分类定理,下列哪一个不可能是 Q\mathbb{Q} 上椭圆曲线的挠子群 E(Q)torsE(\mathbb{Q})_{\mathrm{tors}}?

怀尔斯(与泰勒合作)在1994–95年为半稳定椭圆曲线证明的模性定理,是解决下列哪个经典问题的关键要素?

参考文献

  1. Joseph H. Silverman (2009). The Arithmetic of Elliptic Curves · DOI:10.1007/978-0-387-09494-6
  2. Andrew Wiles (1995). Modular elliptic curves and Fermat's Last Theorem · DOI:10.2307/2118559
  3. Andrew Wiles / Clay Mathematics Institute (2000). The Birch and Swinnerton-Dyer Conjecture (official Millennium Problem description)
  4. Wouter Castryck, Thomas Decru (2022). An efficient key recovery attack on SIDH