何麗

橢圓曲線在數(shù)學(xué)當(dāng)中有很廣泛的應(yīng)用，在其計(jì)算方面也有很多的算法出現(xiàn)。J.E.Cremona的《Algorithms for Modular Elliptic Curves》就是這方面的一本著作。這本書主要分為兩大部分：一部分介紹一種基于模特征來計(jì)算階為N的橢圓曲線的算法，另一部分則介紹一些能夠計(jì)算橢圓曲線的某些算術(shù)量的算法。與Tingley的方法相比，書中介紹的算法有一個(gè)重要的優(yōu)點(diǎn)。對(duì)于Γ0（N）在擴(kuò)充上半平面上的作用的基本域，我們并不需要了解其確切的幾何形態(tài)。也就是說，對(duì)于合數(shù)N，只需要考慮其素因子就行了。另一部分計(jì)算的量包括最小方程、秩、撓元素、Mordell-Weil群的生成元等等。

一、橢圓曲線的基本定義和一些術(shù)語

在Q上定義的橢圓曲線E滿足Weierstrass方程：

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

其中的參數(shù)ai都是有理數(shù)。特別地，如果這些ai都是整數(shù)，則稱E為定義在Z上的橢圓曲線。橢圓曲線也可以簡(jiǎn)單記為[a1，a2，a3，a4，a6]。除了這些定義的基本量之外，還可以定義一些輔助量，最重要的是不變量c4，c6，判別式Δ，以及定義為c43/Δ的j-不變量。j-不變量在同構(gòu)下是保持不變的，而最常見的同構(gòu)通過坐標(biāo)變換來實(shí)現(xiàn)。在所有定義在Z上的模型中，使得Δ的絕對(duì)值最小的被稱為E的整體最小模型。每一條定義在Q上的橢圓曲線，都存在唯一這樣的模型。這一事實(shí)說明，要分辨不同的曲線是比較容易的。

一個(gè)典型的問題是，當(dāng)給出不變量c4和c6時(shí)，是否存在Q上的曲線以它們?yōu)椴蛔兞?？進(jìn)一步地，是否為最小模型？Kraus給出了這個(gè)問題在同余意義下的充要條件，被稱為Kraus條件。也有相應(yīng)的算法，根據(jù)給出的符合Kraus條件的整數(shù)對(duì)，來計(jì)算最小模型。另一個(gè)重要的定義是模橢圓曲線：Q上的橢圓曲線E被稱為模橢圓曲線，如果存在非平凡映射Φ，將某條模曲線XG映到E。

二、基于模特征的橢圓曲線算法

1.準(zhǔn)備工作：定義、性質(zhì)等。

首先要說明考慮對(duì)象，也就是擴(kuò)充的上半平面：H*=H∪Q∪{∞}，其中H={x+iy|y>0}。群PSL2（R）在上半平面有一個(gè)分式線性變換，取Γ=PSL2（Z），則其生成元為S和T，即映射z→-1/z和z→z+1對(duì)應(yīng)的變換矩陣。其基本域，則是z的實(shí)部絕對(duì)值不超過1/2，z的模又不小于1的區(qū)域。XG=G＼H*記為商空間，需要注意的點(diǎn)有尖點(diǎn)和橢圓點(diǎn)。G的權(quán)為2的尖點(diǎn)形式構(gòu)成的空間記為S2（G），這些尖點(diǎn)形式f指的是上半平面的全純函數(shù)，滿足一定的條件。其中f|M=f，任取M∈G。在無窮遠(yuǎn)處的情況則需要另外定義，涉及到f的Fourier展開。

該方法計(jì)算的基礎(chǔ)是Riemann面XG的同調(diào)，我們需要通過對(duì)曲面上的閉路進(jìn)行積分，得到尖點(diǎn)形式f的周期。這樣可以給出一個(gè)H1（XG，Z）的幾何定義：將XG的所有閉路視為生成元，得到一個(gè)Abel群。其中兩條閉路等價(jià)，當(dāng)且僅當(dāng)一條可以通過連續(xù)變換成為另外一條。以下給出模特征的定義：設(shè)α，β∈H*是在群G作用下等價(jià)的點(diǎn)，則從α到β的光滑路徑能夠投影到商空間的閉路，那么將決定一個(gè)整同調(diào)類，將這一同調(diào)類稱為模特征，記作{α，β}。由此可以將f（z）從α到β積分，并將該積分乘以2πi的值定義為尖點(diǎn)形式的周期If（α，β）。如果α和β是任意的，則通過映射f→If（α，β）能夠定義H1（XG，R）上的模特征?？梢远x一個(gè)R-雙線性函數(shù)，給出S2（G）×H1（XG，R）→C的一個(gè)對(duì)偶映射。

令J為行向量為（-1，0）和（0，1）的2×2矩陣，Γ的子群G稱為實(shí)類型，如果J能夠?qū)正規(guī)化。也就是說M∈G和M的伴隨矩陣M*∈G等價(jià)。通過取負(fù)共軛數(shù)的方法可以定義映射z*，這一映射可以推廣到{α，β}上。類似地可以定義f*，其Fourier系數(shù)是f的相應(yīng)系數(shù)的共軛。從而可以得到一個(gè)重要的結(jié)論：H1（XG，R）可以分解為映射*的特征值分別為1和-1的特征子空間的直和。這樣的話，就可以通過處理H+來處理H上的問題，維數(shù)降低了一半。

有了以上的工作，不難發(fā)現(xiàn)任意H1（XG，Z）的元素γ均具備形式{α，Mα}。考慮最重要的同余子群Γ0（N）：所有左下角元素為N的倍數(shù)的2×2矩陣。根據(jù)Manin-Drinfeld定理，如果G是Γ的同余子群，則對(duì)任何尖點(diǎn)對(duì)α，β，都有{α，β}∈H1（XG，Q）。使用Hecke算子，也可以說明當(dāng)G是同余子群時(shí)，S2（G）具有有理數(shù)結(jié)構(gòu)。也就是說，存在一組基，它們的Fourier系數(shù)全是有理數(shù)。這一有理結(jié)構(gòu)的重要性在于，可以確定發(fā)現(xiàn)的曲線確實(shí)是在Q上定義的?？紤]上半平面的三角剖分，可以定義邊界映射δ，記其核為Z（G）。如果定義B（G）為（M）+（MS）和（M）+（MTS）+（M（TS）2）張成的子空間，那么可以定義H（G）=Z（G）＼B（G）。通過Manin的重要結(jié)論，H（G）和H1（XG，Q）是同構(gòu)的。要用這個(gè)結(jié)論計(jì)算同調(diào)的話，需要尋找子群G的右陪集表示，也需要設(shè)法考察尖點(diǎn)的G-等價(jià)性。

如果將問題具體到Γ0（N），可以考慮M-特征。定義等價(jià)關(guān)系：（c1，d1）與（c2，d2）等價(jià)，當(dāng)且僅當(dāng)c1d2和c2d1模N同余。這種被記為（c：d）的等價(jià)類稱為M-特征。而所有M-特征組成的集合到Γ0（N）的右陪集代表系有一個(gè)雙射。因此如果計(jì)算ker（δ），需要判斷兩個(gè)尖點(diǎn)是否Γ0（N）-等價(jià)。通過對(duì)這種等價(jià)性的分析，可以發(fā)現(xiàn)H（N）是由M-特征給出的。通過考慮c和d與N的最大公約數(shù)，能夠給出所有不等價(jià)的M-特征。之后可以在這些M-特征的自由生成元上計(jì)算映射δ，并考察其尖點(diǎn)等價(jià)性。記虧格為g，那么可以將H（N）的元素視為Z2g中的向量。在模特征和M-特征之間，可以通過簡(jiǎn)單的映射進(jìn)行轉(zhuǎn)換。

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

對(duì)于不能整除N的素?cái)?shù)p，可以定義作用在模特征上的Hecke算子Tp，這一算子也可以定義在S2（N）上。具體作用為{α，β}→{pα，pβ}+{（α+r）/p，（β+r）/p}其中r對(duì)所有r（modp）求和。而（f|Tp）（z）定義為pf（pz）+f（（z+r）/p）/p，其中r從0到p-1求和。另一個(gè)需要考慮的算子則是對(duì)合算子Wq，其中q是能夠整除N的素?cái)?shù)。令α是N的素因數(shù)分解式中q的次數(shù)，再令qαxw-（N/qα）yz=1。那么Wq可以用行向量為（qαx，y）和（Nz，qαw）的矩陣表示，其行列式為qα，并且將Γ0（N）正規(guī)化。由于在Hecke代數(shù)的意義下，之前提到的特征值分別為±1的特征子空間彼此同構(gòu)，因此只需要在一個(gè)空間上計(jì)算Hecke算子的特征值即可。endprint

另一個(gè)重要的概念是Heilbronn矩陣，這是M2（Z）中的一個(gè)有限矩陣集Rp，其行列式為p。因此Tp在M-特征上有一個(gè)作用，通過取所有M∈Rp來實(shí)現(xiàn)。其具體定義是：行向量為（x，-y）和（y1，x1），行列式為p，并且滿足以下條件之一：（1）x>|y|>0，x1>|y1|>0，yy1>0；（2）y=0，y1

由于Hecke算子具有的性質(zhì)，可以先考慮在H+（N）上的工作。首先可以將Γ0（N）稍作變形，添加條件ad-bc=±1，同時(shí)也可以定義在這個(gè)新的群上的等價(jià)關(guān)系。這樣的話H+（N）中的特征向量可以與S2（N）中的特征形式相對(duì)應(yīng)。那么通過計(jì)算Hecke算子的特征值，可以間接得到f的Fourier系數(shù)。事實(shí)上，S2（N）是一個(gè)維數(shù)為g的空間，g為虧格。

接下來的問題，是定義“新形式”和“舊形式”。對(duì)N的真因子M和g∈S2（M），考慮N/M的因子D以及g（Dz），它們張成的子空間被稱為“舊形式”，其正交補(bǔ)則被稱為“新形式”?？紤]Af=C＼Λ，其Hecke算子的特征值和f的Fourier系數(shù)均為有理數(shù)，被稱為有理“新形式”。于是可以定義周期格Λf，并且由Ef=C＼Λf，得到相應(yīng)的橢圓曲線。通過對(duì)Hecke特征值的計(jì)算，可以得到f的Fourier系數(shù)。

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

（1）詳細(xì)步驟

要計(jì)算出階為N的模橢圓曲線，需要經(jīng)過下面五個(gè)步驟：

①通過M-特征和它們之間的關(guān)系表出空間H+（N）；

②計(jì)算足夠多的Hecke算子和對(duì)合算子在H+（N）上的作用，找到一維特征子空間，并且其特征值是有理數(shù)；

③找到周期格Λf的整數(shù)基，對(duì)于每個(gè)新形式f，用盡可能高的精度計(jì)算其周期；

④根據(jù)整數(shù)基，計(jì)算橢圓曲線方程的系數(shù)；

⑤計(jì)算L（Ef，1）/Ω（f）和L（Ef，1）的值

（2）對(duì)于第一階段的說明

用M-特征的方法，可以將H+（N）用Qg來表示。在辨別“舊形式”的過程中，可以通過積累的形式建立一個(gè)數(shù)據(jù)庫(kù)，其中儲(chǔ)存“新形式”和它們對(duì)應(yīng)的第一個(gè)Hecke算子的特征值。在分解H+（N）之前，已經(jīng)獲得了這些數(shù)據(jù)：對(duì)于N的真因子M，S2（M）中新形式的個(gè)數(shù)；對(duì)每個(gè)新形式g，對(duì)應(yīng)的Wq和Tp的特征值，其中q取遍所有整除M的素?cái)?shù)，p則是一些不能整除N的素?cái)?shù)。同時(shí)可以推廣Wq的定義：當(dāng)q不能整除N時(shí)，相應(yīng)的α取為0。通過相應(yīng)的性質(zhì)，可以由數(shù)據(jù)庫(kù)得到完整的集合，即對(duì)任意T和W具有相同特征值的子“舊形式”。如果子空間完全由舊形式組成，則將它丟棄；否則就找到了一個(gè)符合條件的有理新形式。在具體操作當(dāng)中，比較可能遇到的問題是在高斯消元法過程中出現(xiàn)的溢出。對(duì)于比較大的素?cái)?shù)P，可以采取在Z/PZ上處理的方式。在之后的計(jì)算中，將只會(huì)考慮到子空間，相應(yīng)的向量也會(huì)被投影到子空間上的向量所代替。

通過Mellin變換，可以得到L函數(shù)L（f，s），它可以寫成Dirichlet序列的無窮級(jí)數(shù)的和。這一函數(shù)是新形式f和模橢圓曲線Ef之間的重要橋梁，一個(gè)重要的結(jié)果是L（f，s）=L（Ef，s）。L函數(shù)的重要性還在于，根據(jù)Birch-Swinnerton-Dyer猜想，L（E，s）的零點(diǎn)的階和E（Q）的秩相同。以Ω0（f）記f的最小實(shí)周期，如果周期格為矩形，則定義Ω（f）為它的2倍，否則和它相等。進(jìn)而可以推得L（f，1）/Ω（f）的表達(dá)式，此式與BSD猜想是相關(guān)的。

接下來就要考慮Fourier系數(shù)的計(jì)算，這與Hecke特征值的計(jì)算關(guān)系很大。表達(dá)式中一些參數(shù)的計(jì)算有賴于對(duì)模特征的分析：需要將模特征表達(dá)為M-特征的線性組合，然后將它們投影到f對(duì)應(yīng)的子空間上。但如果能夠事先得到一個(gè)p0和n（α，p0，f），通過在H+（N）上的計(jì)算，可以獲得一個(gè)與p不相關(guān)的比值表達(dá)式。這樣的話只需計(jì)算相應(yīng)的n（α，p，f），就可以得出ap。在實(shí)際操作中，如果所有有理新形式均滿足L（f，1）非零。此時(shí)的策略是先確定一個(gè)界，并對(duì)所有在范圍內(nèi)的ap進(jìn)行計(jì)算。這樣在第一階段計(jì)算結(jié)束之后，得到了S2（N）中新形式f的數(shù)量。而對(duì)每個(gè)f則有如下信息：L（f，1）/Ω（f）的表達(dá)式；所有q的W算子的特征值；大量的p對(duì)應(yīng)的Hecke特征值。

（3）對(duì)于第二階段的說明

這一階段的主要任務(wù)是對(duì)每一個(gè)新形式計(jì)算周期格，這一工作必須在H（N）上進(jìn)行。對(duì)于所有的p和q，需要計(jì)算兩個(gè)向量，分別是*算子特征值分別為±1的向量，分別記為v+和v-。因此可以考慮Λf在Z上張成的形態(tài)，可以找出它們的整數(shù)基。通過v+、v-和Z上的Euclid算法，可以計(jì)算出所需要的基。實(shí)現(xiàn)計(jì)算過程有兩種方式：一種是直接計(jì)算法，一種則是基于二次特征的間接算法。

直接法是通過取簡(jiǎn)單的回路γ，其中γ滿足v+γ和v-γ都非零。通過對(duì)積分的分析，以及適當(dāng)選取α和Mα的值，能夠得到相關(guān)的周期表達(dá)式。但這個(gè)無窮和面臨的一個(gè)問題是，如果想要得到足夠精確的周期，是要計(jì)算很多項(xiàng)的。在用這個(gè)方法計(jì)算的時(shí)候，需要如下數(shù)據(jù)：形式（1或2，根據(jù)之前對(duì)Ω（f）的定義而來）、M（滿足γ={0，M（0）}）、v+γ和v-γ。間接法的思路則是通過計(jì)算L（f，1）和L（f，1）/Ω（f）的值來得出周期，首先要得到L（f，1）的積分形式表達(dá)式。之后取l為不能整除N的奇素?cái)?shù)，再取l的二次特征。定義了相關(guān)的函數(shù)之后，可以通過具體的計(jì)算，得出之前直接法計(jì)算時(shí)需要的量。為了節(jié)省時(shí)間，很多時(shí)候并不計(jì)算太多的特征值，而是在c4和c6基本接近整數(shù)時(shí)，就取最接近的整數(shù)作為其值。間接法所需要積累的數(shù)據(jù)，和直接法所需的數(shù)據(jù)基本類似。r階導(dǎo)數(shù)L（r）（f，1）的計(jì)算也是非常關(guān)鍵的，這部分的計(jì)算利用到一個(gè)函數(shù)序列。一般來說，r的值不會(huì)超過2。在秩更高的情況下，并沒有很好的辦法來決定高階導(dǎo)數(shù)是否為0。

最后一個(gè)部分就是得到具體的橢圓曲線方程了。在獲得周期ω1和ω2之后，將τ設(shè)定為二者的比值。需要注意τ的近似過程中可能出現(xiàn)的問題，否則在某些情況下算法無法終止。令q=e2πiτ，通過含有q的無窮級(jí)數(shù)的方式，可以計(jì)算出c4和c6的相應(yīng)值。通過這兩個(gè)量，可以最終得到橢圓曲線方程中的系數(shù)。根據(jù)Tate的算法，可以確定該曲線的階。

之后作者給出了幾個(gè)例子：第一個(gè)例子N=11是最初的非平凡的情況；N=33則遇到了一些復(fù)雜的M-特征；N=37則需要采取不同的方法來計(jì)算特征值；最后取N為平方數(shù)49的情況。在這些例子當(dāng)中，比較大的問題就是計(jì)算規(guī)模，而大部分消耗時(shí)間的部分都來自高斯消元法，另一個(gè)耗時(shí)間的部分則是需要計(jì)算大量的特征值。

三、其他算法的簡(jiǎn)單介紹

Tate算法除了驗(yàn)證階之外，還能驗(yàn)證最小性。另一個(gè)問題是關(guān)于Mordell-Weil群的計(jì)算，主要有三個(gè)方面：一是根據(jù)Mordell的定理確定的群結(jié)構(gòu)來尋找撓元素，在這個(gè)步驟當(dāng)中，必要的性質(zhì)使得有限步的檢驗(yàn)就可以完成該工作；二是計(jì)算其生成元，關(guān)鍵是尋找無限階的元素；三則是秩，這也是Mordell-Weil群的相關(guān)計(jì)算中最困難的部分。秩的計(jì)算涉及局部可解性和整體可解性，書中介紹了兩種下降算法，分別利用2-同源關(guān)系和更通用的下降算法。在這個(gè)算法中需要采取新的不變量I和J，并決定對(duì)應(yīng)的四次形式。在經(jīng)過平凡性、等價(jià)性等檢測(cè)之后，將I和J表示的方程代換回原形式即可。