修 士 学 位 論 文

修 士 学 位 論 文

論文題名

楕円曲線のねじれ部分群を計算するアルゴリズムについて

指導教員 内田 幸寛 准教授 2020 年 1 月 10 日 提出

首都大学東京 大学院 理学研究科 数理科学専攻

学修番号 18843403

氏名 石川 岳

目次

1 概要 3

2 Doudのアルゴリズム 3

2.1 主要な3つの定理 . . . 3

2.2 楕円曲線に対する解析的アプローチ . . . 4

2.3 Doudのアルゴリズムの概略 . . . 5

3 定理の拡張 6 4 主結果 8 4.1 アルゴリズムの構成 . . . 8

4.2 計算量の考察. . . 11

4.3 等分多項式 . . . 12

4.4 数値実験 . . . 14

5 考察 16

6 謝辞 17

1 ^概要

本研究では楕円曲線のねじれ部分群を計算するアルゴリズムについて考察する. Kを代数体, OKをKの整数環とする. K上の楕円曲線Eを方程式

y²+a1xy+a3y=x³+a2x²+a4x+a6 (ai∈K)

の解の集合と定義する(ただし,Eは非特異). この方程式は適当な変数変換を行うことで, Weierstrass型楕円 曲線y²=x³+Ax+B (A, B∈ OK,4A³+ 27B²̸= 0)へと変形できる.

ここで代数体上の楕円曲線に関する以下のような定理が存在する.

定理1.1 (Mordell-Weil). 代数体K上の楕円曲線Eに対し,EのK-有理点の群E(K)は有限生成アーベル 群である.

ただし,Oを無限遠点として,

E(K) ={P = (x, y)∈K×K|y²+a1xy+a3y=x³+a2x²+a4x+a6} ∪ {O}

とする. この定理から,E(K)は有限なねじれ部分群E(K)_torを持つことが分かる. 与えられた楕円曲線Eに 対して, このE(K)_torを求めるアルゴリズムは等分多項式の因数分解を用いる方法などが知られている. また

K=Q^の場合, DoudのアルゴリズムやLutz-Nagellの定理を用いた方法などでも楕円曲線のねじれ部分群を

求めることができる. この中で, Doudのアルゴリズムについては,そのアルゴリズムを拡張することで,一般 の代数体K上の楕円曲線のねじれ部分群も求めることが可能であるかは知られていない.

本研究はKを虚2次体に制限した場合, Doudのアルゴリズムを拡張することで, E(K)torを計算するこ とが可能であることを示している. また, 虚2次体上の楕円曲線のねじれ部分群を求めるアルゴリズムを具体 的に構成することで,その計算時間について, 実際に等分多項式の因数分解を用いたアルゴリズムとの比較を 行った.

本論文の構成は以下の通りである. 第2章では, 有理数体上の楕円曲線のねじれ部分群を計算するDoudの アルゴリズムについて述べる. 第3章では, Doudのアルゴリズムを構成する際に用いた定理を虚2次体へ拡 張した場合の定理を与える. 第4章では,本研究の主結果として, 虚2次体上の楕円曲線のねじれ部分群を求 めるアルゴリズムを与え,その計算量についての考察と, 等分多項式の因数分解を用いたアルゴリズムと比較 した数値実験の結果を載せる. 第5章では,その結果についての考察を述べる.

2 Doud ^{のアルゴリズム}

本研究ではDoudのアルゴリズムを虚2次体へ拡張するが, まずDoudのアルゴリズムについて説明する. 詳しくはDoud [4]を参照せよ.

2.1 主要な 3 つの定理

Doudのアルゴリズムで用いる3つの定理を述べる.

定理2.1 (Mazur). 任意のQ上の楕円曲線のねじれ部分群は,Z/nZ(1≤n≤10, n= 12),またはZ/2Z× Z/2nZ(1≤n≤4)のいずれかに同型である.

証明. Mazur [9], [10]を参照せよ.

定理 2.2 (Lutz-Nagell). 任意のZ^{上の楕円曲線}E : y²+a1xy+a3y=x³+a2x²+a4x+a6 (ai∈Z)に 対して,以下が成り立つ.

• ^点P = (x, y)がE(Q)のねじれ点ならば4x∈Z^かつ8y∈Z^である.

• ^点P = (x, y)がねじれ点で, E がWeierstrass型楕円曲線y² = x³+Ax+B (A, B ∈ Z)ならば x, y ∈Z. さらにy= 0またはy²|4A³+ 27B²である.

証明. Silverman [13, Corollary 7.2, p. 221]を参照せよ.

素数pに対してFp =Z/pZ^とする. またE(Fp)をFp上の楕円曲線のFp-有理点の集合とする.

定理 2.3. Eをy² =x³+Ax+B (A, B∈Z)の形で与えられる楕円曲線とする. pをEの判別式を割り切 らない奇素数とすると,E(Q)torからE(Fp)への単射準同型が存在する.

証明. Silverman [13, Propositon 3.1, p. 176]を参照せよ.

2.2 楕円曲線に対する解析的アプローチ

この節では,楕円曲線に対するWeierstrassの℘関数の定義とその性質について述べる.

L=Zω1+Zω2とする(ただし,ω1, ω2∈C^はR^{上線形独立とする}). Lを格子と呼ぶ. また,Lに対して, F ={a₁ω₁+a₂ω₂|0≤a_i<1, i= 1,2}

をLの基本平行四辺形という. 定理2.4.

℘(z) = 1

z² + ∑

ω∈L,ω̸=0

( 1

(z−ω)²− 1 ω²

)

とおく. ℘(z)をWeierstrassの℘関数という. ℘関数は以下を満たす. 1. ℘(z)はC\Lにおけるコンパクト集合上で,絶対かつ一様収束する. 2. ℘(z)はCにおける有理型関数かつLの各点に２位の極を持つ. 3. 任意のz∈C^に対し, ℘(−z) =℘(z).

4. 任意のω∈Lに対し,℘(z+ω) =℘(z).

証明. Washington [14, Theorem 9.3]を参照せよ. 定義2.1. k≥3に対して,

Gk =Gk(L) = ∑

ω∈L,ω̸=0

ω^−k と定義する. G_kをアイゼンシュタイン級数と呼ぶ.

これは,絶対収束する. またkが奇数のとき, G_k = 0.

定理2.5. ℘(z)を格子Lに対するWeierstrassの℘関数とする.

℘^′(z)²= 4℘(z)³−60G4℘(z)−140G6.

証明. Washington [14, Theorem 9.8]を参照せよ. いま,

g₂= 60G₂ g3= 140G4

と表記することにすると,点(℘(z), ℘^′(z))は,

E:y²= 4x³−g2x−g3

という曲線上の点である. なお, この曲線の判別式は16(g₂³−27g²₃)であるが,g₂³−27g₃²̸= 0であることが知 られているため,曲線Eは楕円曲線となる. 従って, z ∈C^{から楕円曲線上の点}(℘(z), ℘^′(z))への写像を考 えることができる. ただし, ℘(z), ℘^′(z)はz modLに依存するため, 実際にはC/LからE(C)への写像を考 える.

定理2.6. Lを格子,Eを楕円曲線y²= 4x³−g2x−g3とする. 写像 Ψ :C/L→E(C)

z7→(℘(z), ℘^′(z)) 07→O

は群同型である.

証明. Washington [14, Theorem 9.10]を参照せよ.

この定理により, E(K)のねじれ点を求める問題を, C/Lにおけるねじれ点を見つけ, その点の像がE(K) に含まれるかという問題に置き換えることができる.

ここで,与えられたあるC^{上の楕円曲線に対して},格子Lを定義するω1, ω2は,楕円曲線の方程式の右辺の 根を求める,かつAGMアルゴリズムを適用することで得ることができる. また,このAGMアルゴリズムは2 次収束するが,後に述べる本研究におけるアルゴリズムは定理2.7のような1次収束する級数を含む. 従って, ω1, ω2の計算はアルゴリズム全体の計算量に影響しない(詳しくはCremona, Thongjunthug [3]を参照せよ).

さらに,℘関数を具体的に計算するための定理についても,ここで述べる. 定理2.7. z∈C, u=e^2πiz/ω1, τ =ω₂/ω₁(Im(τ)>0とする), q=e^2πiτ とおく.

℘(z) = (2πi

ω₁ )2(

1

12+ u

(1−u)² +

∑∞ n=1

qⁿ

( u

(1−qⁿu)²+ u

(qⁿ−u)² − 2 (1−qⁿ)²

))

証明. Washington [14, Theorem 9.35]を参照せよ.

2.3 Doud のアルゴリズムの概略

前節の定理を用いて,有理数体上の楕円曲線のねじれ部分群を求めるDoudのアルゴリズムの概略を述べる. E : y² =x³+Ax+B (A, B ∈ Z)を楕円曲線とする. AGM アルゴリズムを用いることにより, 与えら れた楕円曲線Eに対する格子L =Zω₁+Zω₂を得る. また定理2.3より, いくつかのEの判別式を割り 切らない素数pに対して#E(Fp)を計算することで, #E(Q)torの上界bを得る. このbを割り切る, かつ

Mazurの定理に当てはまるようなnについて大きい方から順番に試していく. 具体的には,まずC/Lのn-ね じれ点zに対し, (℘(z), ℘^′(z))を計算する. ここで, Q上の楕円曲線を考えているので,C/Lのn-ねじれ点は ω1/n, ω1/n+ω2/2, ω1/n+ω1/2 +ω2/2のいずれかである. Lutz-Nagellの定理より℘(z), ℘^′(z)に近い整数 を座標とする点をPとし, P ∈E(Q)かつnP =Oとなるかを確認する. この条件を点Pが満たせば, 点P がE(Q)torの生成元となり,E(Q)torと同型な群を決定できる.

3 ^{定理の拡張}

この章ではDoudのアルゴリズムを虚2次体上へ拡張するために, Mazurの定理, Lutz-Nagellの定理,定 理2.3,それぞれを2次体の場合に拡張したものを紹介する.

Kを2次体とする.

定理3.1. 任意のK上の楕円曲線のねじれ部分群は,以下のいずれかに同型である. Z/mZ (1≤m≤16, m= 18)

Z/2Z×Z/2mZ (1≤m≤6)

Z/3Z×Z/3mZ (m= 1,2) ただしK=Q(√

−3)のときのみ Z/4Z×Z/4Z ^ただしK=Q(√

−1)のときのみ 証明. Kenku, Momose [7], Kamienny [5]を参照せよ.

ここでOK をKの整数環とする. OK はデデキント環だから零でない素イデアルは極大イデアルである. OKをある零でない素イデアルpで局所化した環をR=S⁻¹OK (S=OK\p)とすると,Rは離散付値環で あるから単項イデアル整域である. Rのある素元πにおいて,α∈Kに対して, α=π^ru(u∈R^∗)とかける とき,r= ordπ(α)とおく. また,Eを

E:y²=x³+Ax+B (A, B∈ OK) の形で与えられる楕円曲線とする.

以下, Lutz-Nagellの定理を2次体の場合へ拡張した定理について, Lang [8]に従って述べる.

補題 3.1. n∈Z_≥1を素数のベキでないとし, P = (x, y)∈E(K)を位数がちょうどnである点とする. す ると

x∈ OK. 証明. Lang [8, Theorem 2.1, p. 55]を参照せよ.

補題3.2. 素数pに対して,P = (x, y)∈E(K)を位数p^m(m∈Z_≥1)のねじれ点とする. Rの素元πがpを 割り切ると仮定し, eをπの分岐指数とおく. すると,

ordπ(x)≥ −2r, ordπ(y)≥ −3r.

(

ただし, r= [e

4 ]) [·]はガウス記号を表す.

証明. Lang [8, Theorem 1.3, p. 51]を参照せよ.

補題3.3. P = (x, y)∈E(K)に対して, 2P = (x2, y2)とおく. Eの判別式を∆0= 4A³+ 27B²とすると, y²(4x2(3x²+ 4A)−3x³+ 5Ax+ 27B) = ∆0.

特に,P,2Pが整数点ならばy²|∆0.

証明. Lang [8, Theorem 1.4, p. 52]を参照せよ.

これらの補題を用いて, Lutz-Nagellの定理の2次体の場合についての定理を述べる. なお,この定理は補題 から直ちに従うが, 記載されている文献を見つけられないため,以下で証明を与える.

定理3.2. P = (x, y)∈E(K)torとすると,

x, y∈ OK. さらに,y = 0またはy²|∆0.

証明. 補題3.1より,P の位数が素数のベキでないとき,x, y∈ OK. Pの位数をp^m (pは素数)とする. いま Kは2次体だから, pを割り切る任意のRの素元πに対して,e≤2<4である. 従って, 補題3.2よりpを 割り切る全てのRの素元πについて,r= 0を得る. よって,x, y∈ OK.

また,Pがねじれ点のとき, 2P もねじれ点だから,P,2P は整数点である. 補題3.3より, y²|∆₀. Rの素元πによる還元写像を

R→k=R/πR t7→˜t

と定義する. このとき,OK/pとR/πRは自然な同型になる. また楕円曲線Eに対して,曲線E˜を E˜:y²=x³+ ˜Ax+ ˜B

とおく.

定理3.3. Rの素元πに対して,曲線E˜が非特異であるとすると,写像 Ψ :E(K)_tor →E(k)˜

P = (x, y)7→P˜= (˜x,y)˜ O7→O˜

が存在し, Ψは単射かつ群準同型である.

証明. 定理3.2より,上記のように定義できる写像Ψが存在することが分かる. Ψが群準同型であることはよ く知られている. また単射性については定義より明らかである.

注意1. 定理3.2,定理3.3では,Kは2次体であり,楕円曲線をWeierstrass型として考えている. しかし,一 般の代数体K上の楕円曲線

E:y²+a1xy+a3y=x³+a2x²+a4x+a6 (ai∈ OK)

に対しては, 以下のような定理が存在する. この定理は,本質的にはCasselsが証明を与えた([1]を参照せよ).

ここで,Rは代数体Kの整数環OKをある零でない素イデアルpで局所化した環,k=R/πRとする.

定理3.4. P = (x, y)∈E(K)を位数m∈Z_≥2のねじれ点とする. 1. mが素数のベキでないとき,

x, y∈ OK.

2. 素数pに対して,m=p^sとする. またRの素元πがpを割り切ると仮定し, eをπの分岐指数とおく. すると,

ordπ(x)≥ −2r, ordπ(y)≥ −3r.

(

ただし, r= [ e

ϕ(p^s) ])

ϕはオイラー関数である. 特に,e < p−1ならばord_π(x)≥0,ord_π(y)≥0.

証明. Silverman [13, Theorem 7.1, p. 240]を参照せよ. 定理3.4から以下の定理が導かれる.

定理3.5. 素数pに対してRの素元πがordπ(p) =e < p−1を満たすと仮定する. 楕円曲線Eを素元πで 還元した曲線E˜が非特異であるとき,写像

Ψ :E(K)tor →E(k)˜ P = (x, y)7→P˜= (˜x,y)˜

O7→O˜ が存在し, Ψは単射かつ群準同型である.

定理3.4は,代数体上の楕円曲線のねじれ点が一般に整数点でないことを示している. このことは, Doudの アルゴリズムを一般の代数体上へ拡張することを困難にしている要因の１つである.

4 主結果

4.1 アルゴリズムの構成

この節では, 前章の定理を用いて,虚2次体K =Q(√

−D),D ∈Z_≥1上の楕円曲線のねじれ部分群を求め るアルゴリズムを構成する. なおOKとRについては前章で定義した通りである.

予め2≤n≤16かつn= 18に対して,Z/nZ×Z/nZ^{の部分群で}Z/nZ^{と同型な群}H の生成元のリスト を計算しておく.

与えられたK上の楕円曲線に対して,適当な変数変換を用いて

E:y²=x³+Ax+B (A, B∈ OK)

とする. 後の節で述べるように, 計算精度としてはlog(3⁴max(|A³|,|B²|)) + 2ビットで十分である. まずK からC^{への埋め込みを定め}, AGMアルゴリズムを用いて楕円曲線Eに対する周期ω1, ω2を計算する. 次に, 曲線E˜ が非特異となるような還元写像を与えるRのいくつかの素元πに対して(本研究では20個の素元を 取る),k=R/πRとして# ˜E(k)を計算し,それらの最大公約数を上限値bとする. 定理3.3より,E(K)torの 位数はbの約数である.

• b= 1のとき：E(K)torと同型な群として,自明な群を出力する.

• 4∤bのとき：以下のように場合分けをする.

◆ 9∤bのとき：定理3.1よりE(K)torはZ/nZ(1≤n≤15)のいずれかに同型である. 従ってbを 割り切るようなnに対して, 以下の操作を大きい方から順番に実行していく.

[E(K)のn-ねじれ点の計算]

1. 予め計算してあるZ/nZ×Z/nZ^{の部分群と同型な群}H の生成元(s, t) (s, t∈Z/nZ) に対して,℘(sω1/n+tω2/n), ℘^′(sω1/n+tω2/n)を計算する.

2. ℘(sω1/n+tω2/n), ℘^′(sω1/n+tω2/n)/2に対して,それぞれの値に最も近いOKの値 をx, yとして,点P = (x, y)とおく. なお近い値の求め方は以下の通りである.

∗ −D≡2, 3(mod 4)のとき : ℘(sω₁/n+tω₂/n)を実部α,虚部βに分ける. Kの 整数環はZ[√

−D]であるから,定理3.2より, x∈Z[√

−D]. 従ってα, β/√ Dを 四捨五入した値をそれぞれα^′, β^′とおき,x=α^′+β^′√

−Dとする. yについても 同様.

∗ −D≡1(mod 4)のとき: ℘(sω1/n+tω2/n)を実部α,虚部βに分ける. Kの整 数環はZ[(1 +√

−D)/2]であるから,定理3.2より,x∈Z[(1 +√

−D)/2]. 従って 2α,(2/√

D)βを四捨五入した値をそれぞれα^′, β^′とおき,x=α^′/2 + (β^′/2)√

−D とする. yについても同様.

3. P ∈E(K)かつnP =Oとなるかを確認する. これを満たすならば,点P はE(K)tor

の生成元になり,Z/nZ^{を出力する}.

4. 上記の操作を部分群Hの各生成元に対して行う. 全ての生成元が条件を満たさないな らば,次のnに対して同様の操作を行う.

5. 全てのnが条件を満たさないならば,自明な群を出力する.

これによりE(K)torと同型な群として, Z/nZ^{または自明な群を得る}.

◆ 9 | bのとき：定理 3.1より, D = 3のときのみE(K)tor はZ/3Z×Z/3mZ (m = 1,2)と同型 である可能性がある. そこで℘(ω₁/3), ℘^′(ω₁/3)/2, ℘(ω₂/3), ℘^′(ω₂/3)/2を計算し, それぞれの値 に近いOK の値をx₁, y₁, x₂, y₂とおき, P₁ = (x₁, y₁), P₂ = (x₂, y₂)とする. いまE(K)_tor が Z/3Z×Z/3mZ^{と同型ならば}P₁, P₂∈E(K)となるはずである.

∗ P₁, P₂∈E(K)かつD = 3であるとき：E(K)_torはZ/3Z×Z/3mZ(m= 1,2)のいずれか に同型である. ここで楕円曲線Eの方程式の右辺x³+Ax+Bの根の個数をlとする.

· l = 0 のとき：E(K)tor は 2-ねじれ点を持たないので, E(K)tor と同型な群として, Z/3Z×Z/3Z^を得る.

· l = 1のとき：E(K)tor は2-ねじれ点をただ一つ持つので, E(K)tor と同型な群として, Z/3Z×Z/6Z^を得る.

∗ ^{それ以外のとき：}E(K)torはZ/nZ(1≤n≤15, n= 18)のいずれかに同型であるから, 9∤b のときと同様の操作を行う.

• 4|bのとき：以下のように場合分けをする.

◆ 9∤bのとき：さらに以下のように場合分けをする.

∗ 16∤bのとき：定理3.1より,E(K)_torはZ/nZ(1≤n≤15),Z/2Z×Z/2mZ(1≤m≤6)

のいずれかに同型である.

· l = 0のとき：E(K)torは2-ねじれ点を持たないので, 奇数nに対して, 大きい方から順 番に[E(K)のn-ねじれ点の計算]を実行し,E(K)torと同型な群として,Z/nZ^または自 明な群を得る.

· l= 1のとき：E(K)torは2-ねじれ点をただ一つ持つので,偶数nに対して,大きい方から 順番に[E(K)のn-ねじれ点の計算]を実行し,E(K)torと同型な群として,Z/nZ^を得る.

· l = 3のとき：E(K)tor は 2-ねじれ点を3 つ持つので, E(K)tor はZ/2Z×Z/2mZ (1≤m≤6)のいずれかに同型である. 従って, m= 6,· · ·,1に対してn= 2mとして順 番に[E(K)のn-ねじれ点の計算]を実行し,E(K)_torと同型な群として,Z/2Z×Z/2mZ を得る.

∗ 16|bのとき：℘(ω₁/4), ℘^′(ω₁/4)/2, ℘(ω₂/4), ℘^′(ω₂/4)/2を計算し,それぞれの値に近いOK

の値をx₃, y₃, x₄, y₄とおき, P₃= (x₃, y₃), P₄= (x₄, y₄)とする.

· P3, P4 ∈E(K)かつD = 1であるとき：E(K)tor と同型な群として, Z/4Z×Z/4Z^を 得る.

· ^{それ以外のとき：}E(K)torはZ/nZ(1≤n≤16),Z/2Z×Z/2mZ(1≤m≤6)のいず れかに同型であるから, 16∤bのときと同様の操作を行う.

◆ 9|bのとき：4∤bかつ9|bのときと同様にZ/3Z×Z/3mZと同型になるかを確認する. 同型で ない場合は4|bかつ9∤bのときと同様の操作を行う.

上記のアルゴリズムの具体例を与える. K=Q(√

−1)として楕円曲線のねじれ部分群を計算する. 楕円曲線Eを E:y²=x³−(519075 + 196344√

−1)x+ (129864114 + 85934520√

−1) とする. E の判別式は 4A³ + 27B² = −63347229534763008−1925671990892544√

−1 である. また K=Q(√

−1)だからOKは単項イデアル整域である. 従って, この判別式が0にならないような還元写像を 与える20個の素元π∈ OK=Z[√

−1]に対して, # ˜E(OK/πOK)を計算し,最大公約数をとることで上限値 として7を得る. さらに, log(3⁴max(|A³|,|B²|)) + 2ビットの計算精度でAGMアルゴリズムを用いること で,楕円曲線Eに対する周期

ω1= 0.13763846005987042124 + 0.0023879170433909900940√

−1 ω2=−0.0081603625555070421831−0.087211319097713110560√

−1

を得る. いま上限値は7であるから, #E(K)_torは7の約数であることに注意して, ω₁, ω₂を用いて℘関数を 順番に計算すると, Z/7Z×Z/7Zの部分群と同型な群の生成元(1, 5)に対して,

℘ (1

7ω1+5 7ω2

)

= (−159.000000· · ·)−√

−1×(756.000000· · ·) を得る. 同様に,

℘^′ (1

7ω1+5 7ω2

)

= (50544.000000· · ·) +√

−1×(34992.000000· · ·)

を得る. これらの℘, ℘^′/2に近いOK上の点

(x, y) = (−159−756√

−1,25272 + 17496√

−1)

は E(K) 上の点であることと, 位数が 7 であることが確かめられる. 従って, E(K)tor の生成元は点 (−159−756√

−1,25272 + 17496√

−1)であり,E(K)torと同型な群として,Z/7Z^を得る.

4.2 計算量の考察

この節では, 前節で構成したアルゴリズムの計算量の評価を行う. 前述のアルゴリズムにおいて最も計算時 間を要する部分は, ℘関数の計算であるが, まずは,計算する楕円曲線のねじれ点P = (x1, y1)の各座標の絶 対値と楕円曲線上の点同士の計算時間を評価する. 楕円曲線はy²=x³+Ax+B(A, B∈ OK)であると仮定 する. 定理3.2より, |y1| ≤∆0かつx1は,x³+Ax+ (B−y₁²)の根だから,

|x₁| ≤max(|A|,|B−y²₁|)

≤max(|A|,|B|+|4A³+ 27B²|)

≤3⁴max(|A³|,|B²|)

となる. 従って3⁴max(|A³|,|B²|) = Cとおくと,x1, y1の絶対値はO(C)で評価できる. ここで, 絶対値が O(C)の値の算術演算にはO(log²C)ビットの時間がかかる. また楕円曲線上の点同士の計算には, 有限回の 楕円曲線上の群演算と各楕円曲線上の群演算に対して有限回の算術演算を要する. 従って,本研究におけるア ルゴリズムのうち, 楕円曲線上の点同士の計算時間は,O(log²C)である.

次に℘関数の計算時間について評価する. 定理2.7より, ℘関数について

℘(z) = (2πi

ω1

)2( 1

12+ u

(1−u)² +

∑∞ n=1

qⁿ

( u

(1−qⁿu)²+ u

(qⁿ−u)² − 2 (1−qⁿ)²

))

(1)

とかける. 実際, 格子Lに対する周期ω1, ω2を適当に変換することで, Im(τ)>√

3/2となるようにできる (Serre [12, Proposition 3, p. 82]を参照せよ). 従って|q| ≤ k(k=e^−2π√3/2≒4.33×10⁻³)となる. さら に,zをω1, ω2に対する基本平行四辺形の中から選ぶことで,|q|<|u| ≤1とできる.

ここで点 (℘(z), ℘^′(z)) が楕円曲線 y² = 4x³−g2x−g3 のねじれ点とすると, 点(4℘(z),4℘^′(z))は A^′ =−4g2, B^′ =−16g3として, Weierstrass型楕円曲線y² =x³+A^′x+B^′ 上の点となる. 従って等式 (1)の級数の項は, 余りが1/8未満になるところまで計算すれば十分である. つまりM 項まで加えるとし て, M + 1項以降の和が1/8未満であればよい. 級数の中の各分数は, 1/|q|² の定数倍で上から抑えられる ので, 定数K₁を用いて, 余りであるM + 1項以降の和はK₁|q|^{M−2で上から抑えられる}. いま, この余り は(2πi/ω₁)²倍されるが, 以下の等式を用いることで上から評価できる(Chandrasekharan [2, Corollary 2, p. 69]を参照せよ).

ω³₁= 2π³

∆^1/4₀

θ²₁(0, τ)θ²₂(0, τ)θ₃²(0, τ),

ただし,q=e^2πiτとして

θ1(v, τ) = 2

∑∞ n=0

q^18(2n+1)2cos(2n+ 1)πv,

θ2(v, τ) = 1 + 2

∑∞ n=1

(−1)ⁿq¹²ⁿ²cos(2nπv),

θ₃(v, τ) = 1 + 2

∑∞ n=1

q¹²ⁿ²cos(2nπv)

とする. よってθ1(0, τ) = 2(q^1/8+q^9/8+q^25/8+· · ·), θ2(0, τ) = 1−2q^1/2+ 2q^4/2−2q^9/2+· · · , θ3(0, τ) = 1 + 2q^1/2 + 2q^4/2+ 2q^9/2+· · · ^である. また ∆0 = 4A³ + 27B² である. いま|q| ≤ k であるから,

|θ2(0, τ)|>1/2,|θ3(0, τ)|>1/2,|θ1(0, τ)|>|q|^{1/8という不等式を得る}. 従って,

|ω₁|> π

2|∆0|^1/12|q|^1/12. 以上より, (

2π ω1

)2

K₁|q|^M−2<4π²|∆₀|^1/6K₁q^M−2−1/6

(π/2)² ≤16K₁|∆₀|^1/6k^M−13/6 が1/8未満であればよいので,

16K1|∆0|^1/6k^M−13/6< 1 8 k^M−13/6< 1

2⁷K₁|∆₀|^1/6 (

M −13 6

)

logk <−log(2⁷K1|∆0|¹⁶) M > 13

6 − 1 logk

(

7 log 2 + logK1+1

6log|∆0| )

となる. よって,

M =O(log|∆₀|) =O(logC)

を得る. E(K)のねじれ点Pのx座標x1の絶対値はC以下であるから, Doud [4]によると,各項はおおよそ 2 + logC桁の精度で計算すればよい. 従って, 各項の算術演算の計算時間はO(log²C)である. また上記の議 論から, M =O(logC)項まで計算すればよいので,℘関数の計算量は, O(log³C)である. ℘^′に関しても同様 の結果を得ることができるかつ,計算すべき点の個数はO(1)で評価できるから,本研究のアルゴリズムの計算 時間はO(log³C)で評価できる.

4.3 等分多項式

この節では,次節で計算量の比較を行うアルゴリズムに用いられる等分多項式について,概略を述べる. 詳し くはLang [8]を参照せよ.

アーベル群Aに対して,A[n]をAのn-ねじれ点の集合とする. n∈Z>1に対して, 以下の楕円関数f_nが 存在する.

fn(z)²=n² ∏

0̸=u∈(C/L)[n]

(℘(z)−℘(u)).

いまfnの符号は次のように決定する.

1. n: 奇数⇒fn =Pn(℘),ただしPnは次数(n²−1)/2かつ最高次係数がnであるような多項式である. fn=n℘^(n2−1)/2+· · · .

2. n: 偶数⇒fn= ¹₂℘^′Pn(℘),ただしPnは次数(n²−4)/2かつ最高次係数がnであるような多項式で ある.

fn= n

2℘^′℘^(n2−4)/2+· · ·. 従って,fnのz= 0における展開は,

fn(z) =(−1)ⁿ⁺¹n zⁿ²⁻¹ +· · · となる. またfnの根は明らかに0̸=u∈(C/L)[n]である.

命題4.1. ℘n(z) =℘(nz)とおく.

℘_n=℘−f_n+1f_n−1 f_n² . 証明. Lang [8, Theorem 1.1, p. 34]を参照せよ.

さらにfnは以下の漸化式を満たす. 命題4.2.

f2n+1=fn+2f_n³−f_n+1³ fn−1

℘^′f2n =f2nf2=fn(fn+2f_n²₋₁−fn−2f_n+1² ) 証明. Lang [8, Theorem 1.3, p. 37]を参照せよ.

ここで改めて

x=℘, y= 1

2℘^′, A=−1

4g2, B=−1 4g3

と置き換えると,曲線

y²=x³+Ax+B は楕円曲線になる. さらに命題4.1を用いると

f₁= 1, f₂= 2y

f3= 3x⁴+ 6Ax²+ 12Bx−A²

f4= 4y(x⁶+ 5Ax⁴+ 20Bx³−5A²x²−4ABx−8B²−A³) とかける. いまf_nについても

fn=ψn(x, y)

と置き換える. これらの記号を用いて前述の主張をまとめると次のようにかける. 定理4.1.

ϕn=xψ_n²−ψn+1ψn−1

4yωn=ψn+2ψ²_n−1−ψn−2ψ²_n+1 とおく.

1.

n(x, y) = (ϕ_n

ψ_n²,ω_n ψ_n³

) .

2. ϕn, ψn (n: 奇数),ψn/2y (n: 偶数)はZ[x, A, B]の多項式である. 特に, ϕn(x) =xⁿ²+· · ·

ψ²_n(x) =n²xⁿ²⁻¹+· · ·. とかける. ψ_nを等分多項式とよぶ.

定理4.1より,nに対する等分多項式ψnを因数分解することで,楕円曲線のねじれ点を得ることができ,楕 円曲線のねじれ部分群と同型な群を求めることができる.

4.4 数値実験

この節では,前節で述べた等分多項式の因数分解を用いたアルゴリズム(等分多項式アルゴリズムとする)と 4.1節のDoudのアルゴリズムを拡張したアルゴリズム(Doudの拡張アルゴリズムとする)の計算量の比較を 行う.

以下,数値実験の結果について述べる. 利用した計算機はIntel Core i5-7200U 2.70GHzのプロセッサ,メ モリ8.0GBを実装したWindows 10 Pro, 64ビットオペレーティングシステム,ソフトウェアはSage Math 8.8である.

今回はZ/7Z,Z/9Z,Z/4Z×Z/4Zと同型であるねじれ部分群を持つQ(√

−1)上の楕円曲線に対して実験 を行っている. なおそれぞれの楕円曲線の構成には, Schmitt, Zimmer [11, Theorem 6.18]を参考にした. 具 体的には,K=Q(√

−1)として, 以下のように楕円曲線Eを構成すると,各有限アーベル群はE(K)_torと同 型になる.

• Z/7Z: b, cをパラメータα∈Kを用いて

b=α²(α−1), c=α−1 とおき,楕円曲線Eを

E:y²+ (1−c)xy−by=x³−bx² とする.

• Z/9Z: b, cをパラメータα∈Kを用いて

b=α²(α−1)(α²−α−1), c=α²(α−1) とおき,楕円曲線Eを

E:y²+ (1−c)xy−by=x³−bx² とする.

• Z/4Z×Z/4Z: パラメータα∈Kを用いて楕円曲線Eを

E:y²=x(x²+ 2(α⁴+ 1)x+ (α⁴−1)²) とする.

今回の実験では,まず絶対値が10^k以下の整数p, q, r, sをランダムに生成する. 次にパラメータα∈Kを α=p

q +r s

√−1

とおく. そのαに対して,上記のように構成した楕円曲線のねじれ部分群を計算することを50回行い, それら の平均時間を計算した. 結果については,k= 5,10,20,30に対して数値実験したものを,Z/7Z^{と同型になる} 場合を表1に,Z/9Z^{と同型になる場合を表}2に,Z/4Z×Z/4Z^{と同型になる場合を表}3に記載した.

表1 Z/7Z

k 等分多項式アルゴリズム[ms] Doudの拡張アルゴリズム [ms]

5 163 57

10 320 103

20 731 742

30 1531 2060

表2 Z/9Z

k 等分多項式アルゴリズム[ms] Doudの拡張アルゴリズム [ms]

5 157 95

10 229 390

20 467 1937

30 1087 7048

表3 Z/4Z×Z/4Z

k 等分多項式アルゴリズム[ms] Doudの拡張アルゴリズム [ms]

5 140 42

10 235 85

20 286 162

30 442 411

さらにZ/11Zと同型なねじれ部分群を持つ楕円曲線に対しても数値実験を行った. この楕円曲線の構成 にはSchmitt, Zimmer [11, Theorem 6.18]に加えて, Kamienny, Najman [6]を参考にした. 具体的には, K=Q(√

−7)として,以下のように楕円曲線Eを構成する.

• Z/11Z: b, cをパラメータα, βを用いて, b= 1

2⁷α(2α+β−4)(β−4)(β+ 4), c= 1

2⁴α(2α+β−4)(β−4) とおき,楕円曲線Eを

E:y²+ (1−c)xy−by=x³−bx²

とする. ただし(α, β)は楕円曲線

C:V²=U³−4U²+ 16 上のK-有理点である.

今回はC(K)の生成元(−4,−4√

−7) をQとし, kQ = (α, β)として計算を行った. 結果については k= 7,10,13,16に対して数値実験したものを表4に記載した.

表4 Z/11Z

k 等分多項式アルゴリズム[ms] Doudの拡張アルゴリズム [ms]

7 1170 186

10 3800 391

13 7720 688

16 16500 3490

5 考察

本研究では, Doudのアルゴリズムを構成するときに用いる諸定理の拡張を用いることで, 虚2次体上の楕 円曲線のねじれ部分群を計算するアルゴリズムを構成し,実装した.

実験結果より,Z/7Z^とZ/4Z×Z/4Zの場合はそれほど有意な差が見られない. だがDoudの拡張アルゴ リズムの計算時間は, 前章で計算した通り, 与えられた楕円曲線の係数に依存するので, kをより大きくとる と等分多項式アルゴリズムの方が速くなることが予想される. また, Z/9Zの場合は等分多項式アルゴリズム の方がより顕著に速くなっているが,これもDoudの拡張アルゴリズムの計算時間が楕円曲線の係数の大きさ に依存していることが理由の１つである(Z/9Z^の場合, パラメータの値をおおよそ5乗している). 加えて, Z/9Z^の場合,等分多項式アルゴリズムについては,n= 3に対する等分多項式の根に対応する点P^′を計算し, 3P =P^′となる点P を求めるという操作を行っているため, 実質4次の多項式の因数分解をしている. 従っ て,計算時間が,因数分解を行う等分多項式の次数に依存している等分多項式アルゴリズムの方が,より顕著に 速くなっている. 逆にZ/11Z^の場合は, Doudの拡張アルゴリズムの方が速いが, これも等分多項式アルゴリ ズムの計算時間が,因数分解を行う等分多項式の次数に依存しているからだと考えられる(Z/11Z^の場合,因 数分解する等分多項式の次数はおおよそ60次である). 一方係数が小さい場合, いずれの有限アーベル群に対 してもDoudの拡張アルゴリズムの方が速くなっている.

従って,係数が小さい楕円曲線や, 位数が大きい素因数を含む有限アーベル群と同型になるねじれ部分群を もつ楕円曲線に対して計算する場合に, Doudの拡張アルゴリズムの方が速くなると考えられる.

今後の課題としては, 定理3.4などを用いてDoudのアルゴリズムを拡張することで,虚２次体以外の代数 体上の楕円曲線のねじれ部分群を計算するアルゴリズムを構成できるかを検討することが挙げられる. 特に実 ２次体や３次体の場合は定理3.2より, ねじれ点が整数点になるため,アルゴリズムの構成が可能であるかも しれない.

6 ^謝辞

本研究は,著者が首都大学東京大学院理学研究科数理科学専攻博士前期課程在学中に, 同大学院理学研究科 数理科学専攻の内田幸寛准教授の指導のもとに行ったものであります. 適切な助言を賜り,熱心に指導してく ださった内田幸寛准教授に深く感謝いたします. そしてご多忙の中, 本論文の副査を快諾していただきました 内山成憲教授と横山俊一准教授に深く感謝いたします. また, 2年間の苦楽を共にした梶野智哉氏, 樺島祐氏 や, 今まで支えていただいた家族にも深く感謝いたします. そして最後に, 学生時代の6年間, 関わってくだ さったすべての方に御礼申し上げます.

参考文献

[1] Cassels, J. W. S., A note on the division values of ℘(u), Math. Proc. Cambridge Philos. Soc. 45, 167–172, 1949.

[2] Chandrasekharan, K., Elliptic Functions, Springer, Berlin-Heidelberg-New York, 1985.

[3] Cremona, J. and Thongjunthug, T., The complex AGM, periods of elliptic curves overCand complex elliptic logarithms, J. Number Theory 133, no. 8, 2813–2841, 2013.

[4] Doud, D., A procedure to calculate torsion of elliptic curves over Q, Manuscripta Math. 95, no. 4, 463–469, 1998.

[5] Kamienny, S., Torsion points on elliptic curves, Bull. Amer. Math. Soc, (N.S.) 23, no. 2, 371–373, 1990.

[6] Kamienny, S. and Najman, F., Torsion groups of elliptic curves over quadratic fields, Acta Arith.

152, no. 3, 291–305, 2012.

[7] Kenku, M. A. and Momose, F., Torsion points on elliptic curves defined over quadratic fields, Nagoya Math. J. 109, 125–149, 1988.

[8] Lang, S., Elliptic Curves: Diophantine Analysis, Springer-Verlag, Berlin-Heidelberg-New York, 1978.

[9] Mazur, B., Modular curves and the Eisenstein ideal, Inst. Hautes ´Etudes Sci. Publ. Math., no. 47, 33–186, 1978.

[10] Mazur, B., Rational isogenies of prime degree, Invent. Math. 44, no. 2, 129–162, 1978.

[11] Schmitt, S. and Zimmer, H., Elliptic Curves: A Computational Approach, De Gruyter Studies in Mathematics Book 31, Walter de Gruyter & Co., Berlin, 2003.

[12] Serre, J.-P., A Cource in Arithmetic, Springer-Verlag, New York, 1973.

[13] Silverman, J., The Arithmetic of Elliptic Curves (Second Edition), Springer, Berlin-Heidelberg-New York, 2009.

[14] Washington, L., Elliptic Curves: Number Theory and Cryptography (Second Edition), Chapman and Hall/CRC, 2008.