aiwiki.page
中文
数学 / 几何与拓扑 / elliptic-curve

椭圆曲线

椭圆曲线是带有一个指定点的光滑射影亏格一曲线,联系着几何、数论、复分析与密码学。

38 个关键词21 个词条链接到这里19 个尚未撰写AI 撰写
代数几何数论复分析域(数学)射影空间齐次坐标判别式j 不变量椭圆曲线

椭圆曲线是亏格为一的光滑射影代数曲线,并带有一个指定点,作为曲线上自然加法运算的单位元。尽管它的方程可以很简单,例如 y2=x3−xy^2=x^3-x,但其上的点构成的代数结构,性质却很大程度上取决于坐标所属的数系。在复数域上,椭圆曲线是一个环面;在有理数域上,其上的点构成一个有限生成群;在有限域上,这些点构成一个有限群,可用于构建密码协议。

椭圆曲线在代数几何、数论与复分析之间占据着核心地位。它们帮助人们将整数方程与模形式联系起来,为费马大定理的证明提供了框架,而围绕其有理数解的若干重大问题至今仍未解决。椭圆曲线的名称并非源于其形状与椭圆相似,而是源于它在历史上与计算椭圆弧长时出现的积分之间的联系。

定义、方程与几何不变量

现代定义从一个域 KK 出发。定义在 KK 上的椭圆曲线,是一条亏格为一的光滑、射影、几何整曲线 EE,并带有一个指定的 KK-有理点 OO。“几何整”是指将基域扩张到代数闭包后,曲线仍然不可约且约化。亏格衡量曲线内在的复杂程度:在复数域上,亏格为一对应于带有一个柄的紧致曲面。没有指定有理点的亏格为一曲线,在其定义域上未必是椭圆曲线;不过,经过适当的域扩张并选定一个点后,它就成为椭圆曲线。

每条椭圆曲线都可以用广义的魏尔斯特拉斯方程表示:

y2+a1xy+a3y=x3+a2x2+a4x+a6,y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6,

其中系数属于 KK。这个方程描述了曲线的一个仿射部分。在射影空间中将其补全,会添入点 O=[0:1:0]O=[0:1:0],这里采用了齐次坐标。这个新增的点不可或缺:它使曲线成为完备曲线,并充当加法的单位元。射影定义也避免了将仅仅因删去无穷远点而产生的现象,误认为曲线内在的几何性质。

当 KK 的特征既不是 22 也不是 33 时,通过坐标变换可以将方程化为短魏尔斯特拉斯形式:

y2=x3+Ax+B.y^2=x^3+Ax+B.

曲线光滑的条件是

Δ=−16(4A3+27B2)≠0,\Delta=-16(4A^3+27B^2)\ne0,

其中 Δ\Delta 是该模型的判别式。如果判别式为零,这条三次曲线就有奇点,例如结点或尖点,因而不是椭圆曲线。例如,y2=x3−xy^2=x^3-x 是非奇异的,而 y2=x3y^2=x^3 在原点处有一个尖点。在特征为 22 或 33 时,必须保留广义方程,因为化为短形式所需的除法运算无法进行。

一个基本不变量是 j-不变量;对于短形式方程,它为

j=17284A34A3+27B2.j=1728\frac{4A^3}{4A^3+27B^2}.

在代数闭域上,两条椭圆曲线同构,当且仅当它们的 jj-不变量相等。在原来的域上,jj-不变量相等却未必意味着存在定义在该域上的同构。不同的扭曲形式可能只有在扩张基域后才变得同构。这一区别将几何分类与算术分类区分开来:同一条复曲线可以在有理数域上具有不同的形式,这些形式的有理点不同,在各素数处的行为也不同。

加法法则与点群

指定点 OO 使椭圆曲线成为一个阿贝尔群。对于实数域上的短魏尔斯特拉斯方程,加法有一种称为弦切法的几何描述。经过两点 PP 和 QQ 的直线与这条三次曲线相交于第三点 RR,这里交点按相交重数计数。将 RR 关于 xx 轴作镜像反射,便得到 P+QP+Q。当 P=QP=Q 时,用切线代替弦所在的直线。竖直直线与曲线相交于互为逆元的两点以及 OO,因此 P+(−P)=OP+(-P)=O。

对于不同的仿射点 P=(x1,y1)P=(x_1,y_1) 和 Q=(x2,y2)Q=(x_2,y_2),若 x1≠x2x_1\ne x_2,则有公式

m=y2−y1x2−x1,x3=m2−x1−x2,y3=m(x1−x3)−y1.m=\frac{y_2-y_1}{x_2-x_1}, \qquad x_3=m^2-x_1-x_2, \qquad y_3=m(x_1-x_3)-y_1.

于是 P+Q=(x3,y3)P+Q=(x_3,y_3)。计算倍点时,只要 y1≠0y_1\ne0,就有

m=3x12+A2y1.m=\frac{3x_1^2+A}{2y_1}.

逆元为 −(x,y)=(x,−y)-(x,y)=(x,-y)。在广义魏尔斯特拉斯方程中,逆元则为

−(x,y)=(x,−y−a1x−a3).-(x,y)=(x,-y-a_1x-a_3).

当分母为零时,应利用单位元和逆元的运算规则处理,而不是进行无定义的除法。

这些公式都是坐标的有理式,因此,只要所涉及的分母非零,它们就适用于任意域。如果 PP 和 QQ 的坐标属于 KK,那么它们的和的坐标也属于 KK。因此,KK-有理点的集合 E(K)E(K) 构成一个群。在这一几何构造中,结合律是最不直观的群公理。结合律可以通过代数计算验证,但其概念上的解释来自除子理论:点 PP 对应于由 (P)−(O)(P)-(O) 代表的零次除子类,而除子类的加法满足结合律。由此得到的群称为零次皮卡群。

这一法则可以从已知解构造出新的解。在曲线

E:y2=x3−2,E:\quad y^2=x^3-2,

上,有理点 P=(3,5)P=(3,5) 的倍点为

2P=(129100,−3831000).2P=\left(\frac{129}{100},-\frac{383}{1000}\right).

反复相加可得到倍点 nPnP,但即使起始点的坐标很小,倍点的坐标也可能迅速增大。如果存在某个正整数 nn 使得 nP=OnP=O,就称该点为挠点。在短魏尔斯特拉斯模型上,二阶非单位元点满足 y=0y=0,因为它们等于自身的逆元。这些初等观察直接引出了关于有限阶点、生成元以及是否存在无穷多个有理解的算术问题。

复环面、椭圆函数与椭圆积分

在复数域上,每条椭圆曲线都可以在解析意义下表示为商空间

E(C)≅C/Λ,E(\mathbb C)\cong\mathbb C/\Lambda,

其中

Λ=Zω1+Zω2\Lambda=\mathbb Z\omega_1+\mathbb Z\omega_2

是一个格,且 ω1/ω2\omega_1/\omega_2 不是实数。将基本平行四边形的两组对边分别粘合,就得到一个环面。这不仅是拓扑形状上的相似,更是复李群的同构:复数模格的加法与曲线上的代数加法法则相一致。这个商空间也是一个亏格为一的紧黎曼曲面。

连接环面与三次方程的桥梁是魏尔斯特拉斯 ℘\wp 函数:

℘(z;Λ)=1z2+∑ω∈Λω≠0(1(z−ω)2−1ω2).\wp(z;\Lambda)=\frac{1}{z^2} +\sum_{\substack{\omega\in\Lambda\\\omega\ne0}} \left(\frac{1}{(z-\omega)^2}-\frac{1}{\omega^2}\right).

它是一个椭圆函数,即具有两个独立周期的亚纯函数。它与其导数满足关系

℘′(z)2=4℘(z)3−g2℘(z)−g3.\wp'(z)^2=4\wp(z)^3-g_2\wp(z)-g_3.

映射 z↦(℘(z),℘′(z))z\mapsto(\wp(z),\wp'(z)) 在补充规定将 00 所在的格等价类映到 OO 后,便给出了复环面与这条三次曲线的同构。常数 g2g_2 和 g3g_3 由对格中所有非零点求和的收敛级数确定。

这种描述源于椭圆积分的研究,其中包括含有三次或四次多项式平方根的代数函数的积分。这类表达式出现在椭圆弧长问题和力学系统中。18 世纪,莱昂哈德·欧拉和阿德里安-马里·勒让德的工作发展了椭圆积分的加法公式与分类。19 世纪 20 年代,尼尔斯·亨里克·阿贝尔和卡尔·古斯塔夫·雅各布·雅可比通过研究反函数,使这一领域发生了根本转变。适当选取的椭圆积分,其反函数具有双周期性,这就解释了为什么一个积分问题会引出环面,进而引出代数曲线。

在短魏尔斯特拉斯形式的曲线上,微分

ω=dx2y\omega=\frac{dx}{2y}

在完整曲线上处处全纯,包括无穷远点。沿两个独立的闭合回路对它积分,所得周期生成相应的格;具体结果取决于解析同构的归一化方式。因此,代数坐标、复积分和环面的拓扑,是用不同语言描述的同一个对象。

经过缩放,格可以写成 Z+Zτ\mathbb Z+\mathbb Z\tau,其中 Im⁡τ>0\operatorname{Im}\tau>0。选取不同的格基,会将 τ\tau 替换为

aτ+bcτ+d,ad−bc=1,\frac{a\tau+b}{c\tau+d}, \qquad ad-bc=1,

其中各系数均为整数。jj 不变量将这些等价的描述归为一类。相比之下,实点集 E(R)E(\mathbb R) 只有一个或两个连通分支。对于 y2=x3+Ax+By^2=x^3+Ax+B,当右侧三次多项式有三个互异实根时,实点集有两个连通分支;当它只有一个实根时,则有一个连通分支。

有理点、挠子群与秩

对于定义在有理数域上的椭圆曲线,最核心的结构性结论是莫德尔–韦伊定理:

E(Q)≅E(Q)tors⊕Zr.E(\mathbb Q)\cong E(\mathbb Q)_{\mathrm{tors}}\oplus\mathbb Z^r.

其中挠子群是有限群,非负整数 rr 称为秩。路易斯·莫德尔于 1922 年证明了 Q\mathbb Q 上的有限生成性;安德烈·韦伊在 1928 年的工作中将这一定理推广到了数域上的阿贝尔簇。该定理表明,每个有理点都可以表示为有限个生成元的整数线性组合。但它并未给出一种能够直接找出这些生成元的通用方法。

秩衡量的是相互独立的无限阶点的个数。秩为零意味着有理点只有有限多个,且全都是挠点。秩为正则意味着有无穷多个有理点,它们可由独立生成元的整数线性组合得到。两条方程形式十分相似的曲线,秩却可能不同。此外,找到许多有理点并不等于找到了许多独立的点:一长串点可能全都是同一个生成元的倍点。

巴里·马祖尔在 20 世纪 70 年代证明的挠子群定理,完整列出了 Q\mathbb Q 上所有可能的挠子群。它们是

Z/nZ,1≤n≤10 or n=12,\mathbb Z/n\mathbb Z,\qquad 1\le n\le10\ \text{or}\ n=12,

以及

Z/2Z⊕Z/2mZ,1≤m≤4.\mathbb Z/2\mathbb Z\oplus\mathbb Z/2m\mathbb Z, \qquad 1\le m\le4.

这份列表适用于定义在 Q\mathbb Q 上的曲线;扩张基域后,可能出现的挠子群也会改变。另一个与之互补的结果是卢茨–纳格尔定理:对于整数系数的非奇异短魏尔斯特拉斯方程,每个有理挠点的坐标都是整数。其 yy 坐标要么为零,要么其平方整除 4A3+27B24A^3+27B^2。这就把此类模型的挠点判定化为了一个有限的算术问题。

有限生成性的证明及相关计算都依赖于高度,它用于量化有理点在算术意义上的大小。一种基本的对数高度通过点的 xx 坐标的分子和分母来衡量其大小。典范高度对这一度量大小的函数作出修正,使其满足

h^(nP)=n2h^(P).\widehat h(nP)=n^2\widehat h(P).

它恰好在挠点处为零,并在 E(Q)E(\mathbb Q) 的自由部分上给出一个正定配对。相对于一组基的配对矩阵,其行列式称为调节子,是衡量独立有理点之间间距的一个算术量。

整数坐标解构成的集合比有理解集更小。西格尔定理表明,由整系数魏尔斯特拉斯方程给定的一条固定椭圆曲线,即使有无穷多个有理点,也只有有限多个整点。要确定所有整点,仅仅生成大量已知点的倍点是不够的。

模素数约化与有限域上的曲线

椭圆曲线的整系数方程可以模素数 pp 约化。如果约化后的方程仍然非奇异,就称该曲线在 pp 处具有好约化。特别地,不整除某个整系数模型判别式的素数都是好约化素数。判别式不必要地过大的模型可能掩盖曲线的内在性质,因此算术研究采用局部极小模型。在坏约化素数处,特殊纤维是奇异的,约化可分为乘法约化或加法约化。

在有限域 Fq\mathbb F_q 上,群 E(Fq)E(\mathbb F_q) 是有限群。哈塞定理给出了如下精确的一般估计:

∣#E(Fq)−(q+1)∣≤2q.\left|\#E(\mathbb F_q)-(q+1)\right|\le2\sqrt q.

整数

aq=q+1−#E(Fq)a_q=q+1-\#E(\mathbb F_q)

称为弗罗贝尼乌斯迹。将坐标分别取 qq 次幂的映射诱导出弗罗贝尼乌斯自同态,其特征多项式为

T2−aqT+q.T^2-a_qT+q.

若其根为 α\alpha 和 β\beta,则在复嵌入下有 ∣α∣=∣β∣=q|\alpha|=|\beta|=\sqrt q,并且

#E(Fqn)=qn+1−αn−βn.\#E(\mathbb F_{q^n})=q^n+1-\alpha^n-\beta^n.

因此,只需知道一次点数,就能确定基域的所有有限扩张上的点数。

例如,考虑 F5\mathbb F_5 上的曲线

E:y2=x3−xE:\quad y^2=x^3-x

当 x=0,1,2,3,4x=0,1,2,3,4 时,x3−xx^3-x 的值分别为 0,0,1,4,00,0,1,4,0。由此得到七个仿射点;加上 OO,总共有八个点。因此 a5=5+1−8=−2a_5=5+1-8=-2,符合哈塞界。即使是这个简单的例子,也说明点数计算关乎二次剩余,而非实数图像的形状。

约化也对有理点的算术性质施加了约束。在好约化素数处,有理挠子群中阶与 pp 互素的部分单射到 E(Fp)E(\mathbb F_p) 中。因此,在若干好约化素数处计算点数,可以对可能的有理挠子群施加强有力的限制。局部性质也可以在 p 进数域上研究;在这一框架下,模 pp 的幂的同余信息能够进一步细化约化所提供的信息。

特征 pp 的椭圆曲线分为普通型和超奇异型。在代数闭包上,被乘 pp 映射映到单位元的点所组成的群,在普通情形下有 pp 个元素,而在超奇异情形下只有单位元。这并不意味着超奇异情形下乘 pp 映射的次数为一:它的次数始终是 p2p^2,而几何点数与代数次数之间的差异则源于不可分性。

同源、 自同态与复乘

同源是椭圆曲线之间保持单位元的非常值态射。它是核有限的满射群同态。同源的曲线不一定同构:同源映射可以将多个点映到同一点,而不一定给出一一对应。基本的例子是整数倍映射,

[n]:E⟶E,P⟼nP,[n]:E\longrightarrow E,\qquad P\longmapsto nP,

当 n≠0n\ne0 时,其次数为 n2n^2。当域的特征不整除 nn 时,其几何核同构于

(Z/nZ)2.(\mathbb Z/n\mathbb Z)^2.

对于可分同源,核在同构意义下唯一确定商曲线。反过来,在基域上适当定义的有限子群会给出一个商同源。次数为 dd 的同源 ϕ:E→E′\phi:E\to E' 有一个对偶同源 ϕ^:E′→E\widehat\phi:E'\to E,满足

ϕ^∘ϕ=[d],ϕ∘ϕ^=[d].\widehat\phi\circ\phi=[d], \qquad \phi\circ\widehat\phi=[d].

这些关系使同源成为比较算术不变量的有用工具。例如,在 Q\mathbb Q 上同源的、定义于 Q\mathbb Q 上的椭圆曲线具有相同的秩和相同的 LL-函数,但它们的挠子群和整模型可能不同。

自同态是从曲线到自身且保持单位元的态射。在 C\mathbb C 上,大多数椭圆曲线的自同态只有整数倍映射,因此其自同态环为 Z\mathbb Z。某些特殊曲线具有复乘:其自同态环是某个虚二次域中的一个整环。例如,曲线

y2=x3−xy^2=x^3-x

具有自同构

(x,y)⟼(−x,iy),(x,y)\longmapsto(-x,iy),

在该曲线的复环面描述中,这对应于乘以 ii。它的 jj-不变量为 17281728。同样,满足 j=0j=0 的曲线也具有与三次单位根有关的额外自同构。

复乘在椭圆曲线与类域论之间建立了尤为明确的联系。jj-函数在虚二次数处的值是代数整数,这些值生成了虚二次域的重要阿贝尔扩张。这些代数值也为在有限域上构造具有指定点数的椭圆曲线提供了算法依据。

在特征为 pp 的情形下,超奇异曲线具有不同的自同态理论:它们在代数闭包上的自同态代数是四元数代数,而不是虚二次域。另一种刻画自同态的方式是使用泰特模

Tℓ(E)=lim←⁡nE[ℓn],T_\ell(E)=\varprojlim_n E[\ell^n],

其中素数 ℓ\ell 不同于域的特征。它是 ℓ\ell-进整数环上的秩二模。自同态和域自同构都作用于这一模,从而将几何运算转化为线性代数,并把同源理论与伽罗瓦理论联系起来。

L 函数、模性与费马大定理

对于定义在 Q\mathbb Q 上的椭圆曲线,可以通过计算其模各素数的点数,得到一系列算术数据。对于具有良约化的素数 pp,令

ap=p+1−#E(Fp).a_p=p+1-\#E(\mathbb F_p).

它的 L 函数将这些点数编码为一个欧拉乘积:

L(E,s)=∏pLp(E,s).L(E,s)=\prod_p L_p(E,s).

在具有良约化的素数处,局部因子为

Lp(E,s)=(1−app−s+p1−2s)−1.L_p(E,s)=\left(1-a_pp^{-s}+p^{1-2s}\right)^{-1}.

在乘法约化处,局部因子的形式为 (1−app−s)−1(1-a_pp^{-s})^{-1},其中,分裂乘法约化对应 ap=1a_p=1,非分裂乘法约化对应 ap=−1a_p=-1;在加法约化处,局部因子为 11。由哈塞界可知,当 Re⁡(s)>3/2\operatorname{Re}(s)>3/2 时,这个乘积绝对收敛。

模形式是上半平面上具有高度对称性的解析函数。模性定理指出,定义在 Q\mathbb Q 上的每条椭圆曲线,都对应一个权为二、级等于该曲线导子的本原形式。如果这个本原形式的展开为

f(z)=∑n≥1anqn,q=e2πiz,f(z)=\sum_{n\ge1}a_nq^n, \qquad q=e^{2\pi iz},

那么,在具有良约化的素数处,它的系数与由点数计算得到的 apa_p 一致。导子是一个整数,其素因子恰为坏约化素数,各素因子的指数反映了相应的局部算术性质。

这一对应关系赋予了 L 函数一些无法直接从欧拉乘积看出的解析性质。完备化函数

Λ(E,s)=Ns/2(2π)−sΓ(s)L(E,s)\Lambda(E,s)=N^{s/2}(2\pi)^{-s}\Gamma(s)L(E,s)

可延拓为整函数,并满足

Λ(E,s)=wEΛ(E,2−s),\Lambda(E,s)=w_E\Lambda(E,2-s),

其中,NN 是导子,wE∈{1,−1}w_E\in\{1,-1\} 是根数。点 s=1s=1 是函数方程的中心。函数方程的符号决定了函数在该点的零点阶数的奇偶性,不过,要将这一阶数与有理点联系起来,还需要其他算术结果。

这一定理源于谷山丰、志村五郎和安德烈·韦伊等人的思想。安德鲁·怀尔斯证明了半稳定情形,相关工作在理查德·泰勒的合作下完成,并于 1995 年发表。克里斯托夫·布勒伊、布赖恩·康拉德、弗雷德·戴蒙德和泰勒证明了完整的定理,成果于 2001 年发表。这些证明使用了伽罗瓦表示的形变,以及形变环与赫克代数之间的比较,而不是给出将每条三次曲线转化为模形式的显式公式。

半稳定情形就足以证明费马大定理。沿着格哈德·弗赖提出的联系以及让-皮埃尔·塞尔的表述,肯·里贝特证明了关键的降层推论:如果存在指数为大于二的素数的费马方程解,就会产生一条与模性不相容的半稳定椭圆曲线。怀尔斯的定理排除了这种可能。这个论证展示了椭圆曲线理论的广泛影响:一个关于整数幂的问题,通过研究几何、逐素数的算术性质与解析对称性之间的相容性得到了解决。

贝赫和斯维讷通-戴尔猜想与局部—整体问题

贝赫和斯维讷通-戴尔猜想认为,椭圆曲线的有理点由其 LL-函数在 s=1s=1 处的行为支配。关于秩的断言为

ord⁡s=1L(E,s)=rank⁡E(Q).\operatorname{ord}_{s=1}L(E,s)=\operatorname{rank}E(\mathbb Q).

左侧是解析秩,即解析延拓后的函数在该点的零点阶数。右侧是由莫德尔–韦伊定理给出的代数秩。布赖恩·贝赫和彼得·斯维讷通-戴尔于20世纪60年代提出这一猜想,他们利用早期计算机计算,研究有理点与模各素数的点数之积之间的关系。

猜想的精细形式还预言了首项系数:

\lim_{s\to1}\frac{L(E,s)}{(s-1)^r} = \frac{\Omega_E\,\operatorname{Reg}_E\, \#\Sha(E/\mathbb Q)\,\prod_p c_p} {\#E(\mathbb Q)_{\mathrm{tors}}^2}.

这里,rr 是秩,ΩE\Omega_E 是按标准方式归一化的实周期,Reg⁡E\operatorname{Reg}_E 是调整子,cpc_p 是局部玉河数。该公式还预言了 泰特–沙法列维奇群 \Sha(E/\mathbb Q) 的有限性。各个因子分别反映曲线的不同方面:实积分、有理点格的几何、有限挠子群,以及在坏素数处的行为。

泰特–沙法列维奇群衡量局部—整体原理的失效。EE 的一个挠子是一条亏格为一的曲线,在扩张到代数闭包后,EE 在其上有单纯传递作用,但这条曲线本身可能没有有理点。\Sha 中的类由这样的挠子代表:它们在实数域和每个 pp-进域上都有点,却可能在 Q\mathbb Q 上没有点。因此,即使一个方程模每个素数的任意高次幂都有解,也未必存在有理数解。

塞尔默群是一个有限且可计算的近似对象,将局部检验与整体有理点联系起来。对于整数 n≥2n\ge2,有正合列

0\longrightarrow E(\mathbb Q)/nE(\mathbb Q) \longrightarrow\operatorname{Sel}_n(E/\mathbb Q) \longrightarrow\Sha(E/\mathbb Q)[n] \longrightarrow0.

因此,利用下降法计算可以给出秩的上界。这个上界与已知有理点所生成子群的秩之间若有差距,可能是因为尚未找到某些生成元,也可能反映了 \Sha 中非平凡元素的存在。

一些重要定理解决了若干关键情形,但尚未证明完整猜想。1986年的格罗斯–扎吉尔公式将 LL-函数的导数与希格纳点的高度联系起来。结合科利瓦金的工作,可以推出:在 Q\mathbb Q 上解析秩为零或一的椭圆曲线,其代数秩符合猜想的预言,且泰特–沙法列维奇群是有限群。一般情形下,关于秩的断言、\Sha 的有限性以及完整的首项系数公式仍未得到解决;这一猜想是千禧年大奖难题之一。

算术计算与因数分解

椭圆曲线计算涵盖若干不同的问题:寻找有理点、证明秩的确切值、计算有限域上的点数、计算同源映射以及求 LL-函数的值。这些问题的难度差别很大。计算两个给定点的和并不困难,但要证明某个候选点集生成了所有有理点,则可能需要深刻的算术理论。用计算机搜索坐标大小有界的点,只有在证明所找到的点相互独立之后,才能给出秩的下界;未能找到更多的点,并不能给出秩的上界。

下降法将寻找有理点的问题转化为研究有限个受局部条件约束的覆盖曲线,从而给出秩的上界。其中,二下降法尤为常用;如果存在合适的同源映射,与之相关的下降法也可能十分高效。高度配对可用于检验候选生成元的独立性。另一个称为饱和化的过程则检查:这些生成元所生成的子群,是否遗漏了某个点,而该点的某个倍点已在子群中。可靠的计算应当区分已获证明的秩及完整生成元集、仅有的上下界,以及依赖尚未证明假设的条件性结果。

有限域上的点计数有其独立的算法理论。勒内·斯霍夫于 1985 年提出的算法,通过确定弗罗贝尼乌斯迹模若干小素数的值,再用中国剩余定理将其重构出来;在采用适当的标准表示时,该算法能在关于 log⁡q\log q 的多项式时间内计算 #E(Fq)\#E(\mathbb F_q)。斯霍夫–埃尔基斯–阿特金方法利用弗罗贝尼乌斯在挠点上的作用以及模多项式,提高了实际计算效率。借助这些方法,即使有限域大到无法逐一枚举所有可能的坐标,也能够计算曲线上的点数。

椭圆曲线还提供了一种整数分解方法,由亨德里克·伦斯特拉于 1987 年提出。该方法尝试在模合数 NN 的意义下进行椭圆曲线运算。如果某个分母在模 NN 下不可逆,就可能通过计算最大公因数找到一个因子。其主要阶段是将一个点乘以某个整数,该整数能被许多小素数的幂整除。如果这个点模某个未知素因子 pp 约化后的阶足够光滑,那么这次倍点运算就会使它在模 pp 下变为单位元,从而有机会找出 pp。

与基于模 pp 乘法群的方法相比,这种方法的优势在于:更换曲线就会改变相关群的阶。对于一个固定的未知因子 pp,不同椭圆曲线的阶各不相同,但根据哈塞界的约束,它们都在 p+1p+1 附近。因此,不断选择新的曲线,就能不断获得遇到光滑群阶的新机会。椭圆曲线法尤其适合从很大的合数中找出相对较小的素因子。

椭圆曲线也是一些素性证明算法的基础。在椭圆曲线素性证明中,精心选择的曲线和点可以提供证书,其群阶性质能够推出待检验整数是素数。证书的验证依赖明确的算术条件,可能比生成证书所需的搜索简单得多。

密码学应用与安全边界

椭圆曲线密码学利用曲线上的点所构成的有限群来构建公钥系统。维克托·米勒和尼尔·科布利茨于 1985 年各自独立提出了这一方法。其基本运算是标量乘法:给定点 PP 和整数 kk,计算

Q=[k]P.Q=[k]P.

通过反复倍点和点加,所需的群运算次数与 kk 的比特长度成正比。反向问题——从 PP 和 QQ 求出 kk——是离散对数问题的一个实例;在恰当选取的群中,这一问题被认为难以求解。

在椭圆曲线 Diffie–Hellman 密钥协商中,双方分别公开点 [a]P[a]P 和 [b]P[b]P。双方都可以利用自己的私有标量和对方的公开点计算出 [ab]P[ab]P。旁观者能获得公开点,却不知道这些标量。ECDSA 和 EdDSA 等签名方案利用相关的群运算,使任何人都能验证签名。实际协议还包括编码、哈希函数、密钥派生过程和验证规则;仅凭抽象的曲线群,并不能确定一个完整的安全系统。

对于阶为素数 nn 的子群,Pollard ρ 方法等通用经典攻击大约需要 n\sqrt n 次群运算。这解释了为什么阶接近 22562^{256} 的群通常被认为具有约 128 比特的经典安全强度。这一估计的前提是,不存在利用曲线特殊性质的更快攻击。群阶异常或配对性质不合适的曲线,即使参数看似很大,也可能不安全。

多种方程形式在实现中各有用途。蒙哥马利曲线可以仅用 xx 坐标表示来高效运算,而扭曲爱德华曲线则可提供高效且具有良好完备性的加法公式。丹尼尔·伯恩斯坦于 2006 年提出的 Curve25519 使用阶为 2255−192^{255}-19 的素域;X25519 则规定了一种基于该曲线、得到广泛部署的密钥协商函数。Ed25519 是一种使用相关扭曲爱德华曲线的签名系统。比特币所用的 Secp256k1 在其指定的素域上具有短魏尔斯特拉斯方程 y2=x3+7y^2=x^3+7。

实现安全与数学上的求解难度是两回事。依赖秘密信息的运行时间、功耗或内存访问模式都可能泄露标量信息。无效的输入点和对子群结构的不当处理可能破坏协议的安全性,而在 ECDSA 中重复使用随机数则可能泄露签名密钥。常数时间运算和精确的输入处理规则所应对的威胁,并不是仅靠较大的群阶就能防范的。

椭圆曲线密码学无法抵抗能力足够强的量子计算机。肖尔算法能够在多项式时间内求解离散对数,包括椭圆曲线群中的离散对数。基于同源的密码学探索涉及椭圆曲线的其他计算问题,但并不是把标量乘法换成同源映射就能保证安全:2022 年 SIKE 方案被攻破的事件表明,具体采用的数学问题以及协议暴露的额外信息才是决定性因素。