基于模特征的椭圆曲线的算法

何丽

椭圆曲线在数学当中有很广泛的应用，在其计算方面也有很多的算法出现。J.E.Cremona的《Algorithms for Modular Elliptic Curves》就是这方面的一本著作。这本书主要分为两大部分：一部分介绍一种基于模特征来计算阶为N的椭圆曲线的算法，另一部分则介绍一些能够计算椭圆曲线的某些算术量的算法。与Tingley的方法相比，书中介绍的算法有一个重要的优点。对于Γ0（N）在扩充上半平面上的作用的基本域，我们并不需要了解其确切的几何形态。也就是说，对于合数N，只需要考虑其素因子就行了。另一部分计算的量包括最小方程、秩、挠元素、Mordell-Weil群的生成元等等。

一、椭圆曲线的基本定义和一些术语

在Q上定义的椭圆曲线E满足Weierstrass方程：

y2+a1xy+a3y=x3+a2x2+a4x+a6

其中的参数ai都是有理数。特别地，如果这些ai都是整数，则称E为定义在Z上的椭圆曲线。椭圆曲线也可以简单记为[a1，a2，a3，a4，a6]。除了这些定义的基本量之外，还可以定义一些辅助量，最重要的是不变量c4，c6，判别式Δ，以及定义为c43/Δ的j-不变量。j-不变量在同构下是保持不变的，而最常见的同构通过坐标变换来实现。在所有定义在Z上的模型中，使得Δ的绝对值最小的被称为E的整体最小模型。每一条定义在Q上的椭圆曲线，都存在唯一这样的模型。这一事实说明，要分辨不同的曲线是比较容易的。

一个典型的问题是，当给出不变量c4和c6时，是否存在Q上的曲线以它们为不变量？进一步地，是否为最小模型？Kraus给出了这个问题在同余意义下的充要条件，被称为Kraus条件。也有相应的算法，根据给出的符合Kraus条件的整数对，来计算最小模型。另一个重要的定义是模椭圆曲线：Q上的椭圆曲线E被称为模椭圆曲线，如果存在非平凡映射Φ，将某条模曲线XG映到E。

二、基于模特征的椭圆曲线算法

1.准备工作：定义、性质等。

首先要说明考虑对象，也就是扩充的上半平面：H*=H∪Q∪{∞}，其中H={x+iy|y>0}。群PSL2（R）在上半平面有一个分式线性变换，取Γ=PSL2（Z），则其生成元为S和T，即映射z→-1/z和z→z+1对应的变换矩阵。其基本域，则是z的实部绝对值不超过1/2，z的模又不小于1的区域。XG=G＼H*记为商空间，需要注意的点有尖点和椭圆点。G的权为2的尖点形式构成的空间记为S2（G），这些尖點形式f指的是上半平面的全纯函数，满足一定的条件。其中f|M=f，任取M∈G。在无穷远处的情况则需要另外定义，涉及到f的Fourier展开。

该方法计算的基础是Riemann面XG的同调，我们需要通过对曲面上的闭路进行积分，得到尖点形式f的周期。这样可以给出一个H1（XG，Z）的几何定义：将XG的所有闭路视为生成元，得到一个Abel群。其中两条闭路等价，当且仅当一条可以通过连续变换成为另外一条。以下给出模特征的定义：设α，β∈H*是在群G作用下等价的点，则从α到β的光滑路径能够投影到商空间的闭路，那么将决定一个整同调类，将这一同调类称为模特征，记作{α，β}。由此可以将f（z）从α到β积分，并将该积分乘以2πi的值定义为尖点形式的周期If（α，β）。如果α和β是任意的，则通过映射f→If（α，β）能够定义H1（XG，R）上的模特征。可以定义一个R-双线性函数，给出S2（G）×H1（XG，R）→C的一个对偶映射。

令J为行向量为（-1，0）和（0，1）的2×2矩阵，Γ的子群G称为实类型，如果J能够将G正规化。也就是说M∈G和M的伴随矩阵M*∈G等价。通过取负共轭数的方法可以定义映射z*，这一映射可以推广到{α，β}上。类似地可以定义f*，其Fourier系数是f的相应系数的共轭。从而可以得到一个重要的结论：H1（XG，R）可以分解为映射*的特征值分别为1和-1的特征子空间的直和。这样的话，就可以通过处理H+来处理H上的问题，维数降低了一半。

有了以上的工作，不难发现任意H1（XG，Z）的元素γ均具备形式{α，Mα}。考虑最重要的同余子群Γ0（N）：所有左下角元素为N的倍数的2×2矩阵。根据Manin-Drinfeld定理，如果G是Γ的同余子群，则对任何尖点对α，β，都有{α，β}∈H1（XG，Q）。使用Hecke算子，也可以说明当G是同余子群时，S2（G）具有有理数结构。也就是说，存在一组基，它们的Fourier系数全是有理数。这一有理结构的重要性在于，可以确定发现的曲线确实是在Q上定义的。考虑上半平面的三角剖分，可以定义边界映射δ，记其核为Z（G）。如果定义B（G）为（M）+（MS）和（M）+（MTS）+（M（TS）2）张成的子空间，那么可以定义H（G）=Z（G）＼B（G）。通过Manin的重要结论，H（G）和H1（XG，Q）是同构的。要用这个结论计算同调的话，需要寻找子群G的右陪集表示，也需要设法考察尖点的G-等价性。

如果将问题具体到Γ0（N），可以考虑M-特征。定义等价关系：（c1，d1）与（c2，d2）等价，当且仅当c1d2和c2d1模N同余。这种被记为（c：d）的等价类称为M-特征。而所有M-特征组成的集合到Γ0（N）的右陪集代表系有一个双射。因此如果计算ker（δ），需要判断两个尖点是否Γ0（N）-等价。通过对这种等价性的分析，可以发现H（N）是由M-特征给出的。通过考虑c和d与N的最大公约数，能够给出所有不等价的M-特征。之后可以在这些M-特征的自由生成元上计算映射δ，并考察其尖点等价性。记亏格为g，那么可以将H（N）的元素视为Z2g中的向量。在模特征和M-特征之间，可以通过简单的映射进行转换。

2.Hecke算子和其他算子、Heilbronn矩阵。

对于不能整除N的素数p，可以定义作用在模特征上的Hecke算子Tp，这一算子也可以定义在S2（N）上。具体作用为{α，β}→{pα，pβ}+{（α+r）/p，（β+r）/p}其中r对所有r（modp）求和。而（f|Tp）（z）定义为pf（pz）+f（（z+r）/p）/p，其中r从0到p-1求和。另一个需要考虑的算子则是对合算子Wq，其中q是能够整除N的素数。令α是N的素因数分解式中q的次数，再令qαxw-（N/qα）yz=1。那么Wq可以用行向量为（qαx，y）和（Nz，qαw）的矩阵表示，其行列式为qα，并且将Γ0（N）正规化。由于在Hecke代数的意义下，之前提到的特征值分别为±1的特征子空间彼此同构，因此只需要在一个空间上计算Hecke算子的特征值即可。endprint

另一个重要的概念是Heilbronn矩阵，这是M2（Z）中的一个有限矩阵集Rp，其行列式为p。因此Tp在M-特征上有一个作用，通过取所有M∈Rp来实现。其具体定义是：行向量为（x，-y）和（y1，x1），行列式为p，并且满足以下条件之一：（1）x>|y|>0，x1>|y1|>0，yy1>0；（2）y=0，y1

由于Hecke算子具有的性质，可以先考虑在H+（N）上的工作。首先可以将Γ0（N）稍作变形，添加条件ad-bc=±1，同时也可以定义在这个新的群上的等价关系。这样的话H+（N）中的特征向量可以与S2（N）中的特征形式相对应。那么通过计算Hecke算子的特征值，可以间接得到f的Fourier系数。事实上，S2（N）是一个维数为g的空间，g为亏格。

接下来的问题，是定义“新形式”和“旧形式”。对N的真因子M和g∈S2（M），考虑N/M的因子D以及g（Dz），它们张成的子空间被称为“旧形式”，其正交补则被称为“新形式”。考虑Af=C＼Λ，其Hecke算子的特征值和f的Fourier系数均为有理数，被称为有理“新形式”。于是可以定义周期格Λf，并且由Ef=C＼Λf，得到相应的椭圆曲线。通过对Hecke特征值的计算，可以得到f的Fourier系数。

3.基于模特征的算法说明。

（1）详细步骤

要计算出阶为N的模椭圆曲线，需要经过下面五个步骤：

①通过M-特征和它们之间的关系表出空间H+（N）；

②计算足够多的Hecke算子和对合算子在H+（N）上的作用，找到一维特征子空间，并且其特征值是有理数；

③找到周期格Λf的整数基，对于每个新形式f，用尽可能高的精度计算其周期；

④根据整数基，计算椭圆曲线方程的系数；

⑤计算L（Ef，1）/Ω（f）和L（Ef，1）的值

（2）对于第一阶段的说明

用M-特征的方法，可以将H+（N）用Qg来表示。在辨别“旧形式”的过程中，可以通过积累的形式建立一个数据库，其中储存“新形式”和它们对应的第一个Hecke算子的特征值。在分解H+（N）之前，已经获得了这些数据：对于N的真因子M，S2（M）中新形式的个数；对每个新形式g，对应的Wq和Tp的特征值，其中q取遍所有整除M的素数，p则是一些不能整除N的素数。同时可以推广Wq的定义：当q不能整除N时，相应的α取为0。通过相应的性质，可以由数据库得到完整的集合，即对任意T和W具有相同特征值的子“旧形式”。如果子空间完全由旧形式组成，则将它丢弃；否则就找到了一个符合条件的有理新形式。在具体操作当中，比较可能遇到的问题是在高斯消元法过程中出现的溢出。对于比较大的素数P，可以采取在Z/PZ上处理的方式。在之后的计算中，将只会考虑到子空间，相应的向量也会被投影到子空间上的向量所代替。

通过Mellin变换，可以得到L函数L（f，s），它可以写成Dirichlet序列的无穷级数的和。这一函数是新形式f和模椭圆曲线Ef之间的重要桥梁，一个重要的结果是L（f，s）=L（Ef，s）。L函数的重要性还在于，根据Birch-Swinnerton-Dyer猜想，L（E，s）的零点的阶和E（Q）的秩相同。以Ω0（f）记f的最小实周期，如果周期格为矩形，则定义Ω（f）为它的2倍，否则和它相等。进而可以推得L（f，1）/Ω（f）的表达式，此式与BSD猜想是相关的。

接下来就要考虑Fourier系数的计算，这与Hecke特征值的计算关系很大。表达式中一些参数的计算有赖于对模特征的分析：需要将模特征表达为M-特征的线性组合，然后将它们投影到f对应的子空间上。但如果能够事先得到一个p0和n（α，p0，f），通过在H+（N）上的计算，可以获得一个与p不相关的比值表达式。这样的话只需计算相应的n（α，p，f），就可以得出ap。在实际操作中，如果所有有理新形式均满足L（f，1）非零。此时的策略是先确定一个界，并对所有在范围内的ap进行计算。这样在第一阶段计算结束之后，得到了S2（N）中新形式f的数量。而对每个f则有如下信息：L（f，1）/Ω（f）的表达式；所有q的W算子的特征值；大量的p对应的Hecke特征值。

（3）对于第二阶段的说明

这一阶段的主要任务是对每一个新形式计算周期格，这一工作必须在H（N）上进行。对于所有的p和q，需要计算两个向量，分别是*算子特征值分别为±1的向量，分别记为v+和v-。因此可以考虑Λf在Z上张成的形态，可以找出它们的整数基。通过v+、v-和Z上的Euclid算法，可以计算出所需要的基。实现计算过程有两种方式：一种是直接计算法，一种则是基于二次特征的间接算法。

直接法是通过取简单的回路γ，其中γ满足v+γ和v-γ都非零。通过对积分的分析，以及适当选取α和Mα的值，能够得到相关的周期表达式。但这个无穷和面临的一个问题是，如果想要得到足够精确的周期，是要计算很多项的。在用这个方法计算的时候，需要如下数据：形式（1或2，根据之前对Ω（f）的定义而来）、M（满足γ={0，M（0）}）、v+γ和v-γ。间接法的思路则是通过计算L（f，1）和L（f，1）/Ω（f）的值来得出周期，首先要得到L（f，1）的積分形式表达式。之后取l为不能整除N的奇素数，再取l的二次特征。定义了相关的函数之后，可以通过具体的计算，得出之前直接法计算时需要的量。为了节省时间，很多时候并不计算太多的特征值，而是在c4和c6基本接近整数时，就取最接近的整数作为其值。间接法所需要积累的数据，和直接法所需的数据基本类似。r阶导数L（r）（f，1）的计算也是非常关键的，这部分的计算利用到一个函数序列。一般来说，r的值不会超过2。在秩更高的情况下，并没有很好的办法来决定高阶导数是否为0。

最后一个部分就是得到具体的椭圆曲线方程了。在获得周期ω1和ω2之后，将τ设定为二者的比值。需要注意τ的近似过程中可能出现的问题，否则在某些情况下算法无法终止。令q=e2πiτ，通过含有q的无穷级数的方式，可以计算出c4和c6的相应值。通过这两个量，可以最终得到椭圆曲线方程中的系数。根据Tate的算法，可以确定该曲线的阶。

之后作者给出了几个例子：第一个例子N=11是最初的非平凡的情况；N=33则遇到了一些复杂的M-特征；N=37则需要采取不同的方法来计算特征值；最后取N为平方数49的情况。在这些例子当中，比较大的问题就是计算规模，而大部分消耗时间的部分都来自高斯消元法，另一个耗时间的部分则是需要计算大量的特征值。

三、其他算法的简单介绍

Tate算法除了验证阶之外，还能验证最小性。另一个问题是关于Mordell-Weil群的计算，主要有三个方面：一是根据Mordell的定理确定的群结构来寻找挠元素，在这个步骤当中，必要的性质使得有限步的检验就可以完成该工作；二是计算其生成元，关键是寻找无限阶的元素；三则是秩，这也是Mordell-Weil群的相关计算中最困难的部分。秩的计算涉及局部可解性和整体可解性，书中介绍了两种下降算法，分别利用2-同源关系和更通用的下降算法。在这个算法中需要采取新的不变量I和J，并决定对应的四次形式。在经过平凡性、等价性等检测之后，将I和J表示的方程代换回原形式即可。