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

何麗

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

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

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

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

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

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

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

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

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

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

令J為行向量為（-1，0）和（0，1）的2×2矩陣，Γ的子群G稱為實類型，如果J能夠?qū)正規(guī)化。也就是說M∈G和M的伴隨矩陣M*∈G等價。通過取負(fù)共軛數(shù)的方法可以定義映射z*，這一映射可以推廣到{α，β}上。類似地可以定義f*，其Fourier系數(shù)是f的相應(yīng)系數(shù)的共軛。從而可以得到一個重要的結(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是Γ的同余子群，則對任何尖點對α，β，都有{α，β}∈H1（XG，Q）。使用Hecke算子，也可以說明當(dāng)G是同余子群時，S2（G）具有有理數(shù)結(jié)構(gòu)。也就是說，存在一組基，它們的Fourier系數(shù)全是有理數(shù)。這一有理結(jié)構(gòu)的重要性在于，可以確定發(fā)現(xiàn)的曲線確實是在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)的。要用這個結(jié)論計算同調(diào)的話，需要尋找子群G的右陪集表示，也需要設(shè)法考察尖點的G-等價性。

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

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

對于不能整除N的素數(shù)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的素數(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)，因此只需要在一個空間上計算Hecke算子的特征值即可。endprint

另一個重要的概念是Heilbronn矩陣，這是M2（Z）中的一個有限矩陣集Rp，其行列式為p。因此Tp在M-特征上有一個作用，通過取所有M∈Rp來實現(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，同時也可以定義在這個新的群上的等價關(guān)系。這樣的話H+（N）中的特征向量可以與S2（N）中的特征形式相對應(yīng)。那么通過計算Hecke算子的特征值，可以間接得到f的Fourier系數(shù)。事實上，S2（N）是一個維數(shù)為g的空間，g為虧格。

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

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

（1）詳細步驟

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

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

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

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

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

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

（2）對于第一階段的說明

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

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

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

（3）對于第二階段的說明

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

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

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

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

三、其他算法的簡單介紹

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