修 士 学 位 論 文
論文題名
テータ関数に基づく
Kummer
曲面上の擬加法
に関する等分多項式
指導教授内田 幸寛
准教授
平成
30
年
1
月
10
日
提出
首都大学東京 大学院
理工学研究科 数理情報科学専攻
学修番号
16878310
氏名 小澤 英泰
目次
1 概要 3
2 GaudryによるKummer曲面上の擬加法及び, Kummer曲面と種数2の超楕円曲線のヤコビア
ンとの関係 4 2.1 テータ関数と指標付きテータ関数と諸公式 . . . 4 2.2 GaudryによるKummer曲面上の擬加法. . . 7 2.3 Kummer曲面と種数2の超楕円曲線のヤコビアンとの関係 . . . 10 2.4 有限体 . . . 12 3 等分多項式µm 13 3.1 等分多項式µmの存在 . . . 13 3.2 等分多項式µmの構成と計算量評価 . . . 17 4 具体例 21 5 謝辞 22
1
概要
楕円曲線暗号はICカードや仮想通貨を支えるブロックチェーンに使用されている.楕円曲線暗号の一般化
である超楕円曲線暗号は1989年にKoblitzにより提案された.安全な種数2の超楕円曲線暗号を構成するた
めには,ヤコビアンの位数がヤコビアンの位数の最大の素因子と同程度である必要がある.そのため,ヤコビ
アンの位数計算は重要である.位数計算法の1つとして, Schoofのアルゴリズムを拡張したもの[3]がある.
Gaudry [8]は,テータ関数に基づくKummer曲面上の擬加法を与え, Kummer曲面と種数2の超楕円曲線の
ヤコビアンとの関係を与えた.これより, Kummer曲面上の等分多項式を用いることで,ヤコビアンの位数を 求めることができる.本論文では,テータ関数に基づくKummer曲面上の擬加法に関する等分多項式µmの存 在を示し,実際に構成した. 最初に,本論文の内容を説明するために,定義を与える. a, b∈ Q2, z∈ C2とする.H2={A ∈ M(2, C) | A =tA, ImA > 0}に対して, Ω∈ H2とする.指標付き テータ関数を以下で定義する. ϑ[a; b](z, Ω) = ∑ n∈Z2
exp(πit(n + a)Ω(n + a) + 2πit(n + a)· (z + b)).
また,基本テータ関数を以下で定義する. ϑ1(z) = ϑ[(0, 0); (0, 0)](z, Ω), ϑ2(z) = ϑ [ (0, 0); (1 2, 1 2 )] (z, Ω), ϑ3(z) = ϑ [ (0, 0); (1 2, 0 )] (z, Ω), ϑ4(z) = ϑ [ (0, 0); ( 0,1 2 )] (z, Ω). ϑ1(z), ..., ϑ4(z)は偶関数である.さらに, z = 0での指標付きテータ関数の値をテータ定数と呼び, 4個のテー タ定数を定義する. a = ϑ1(0), b = ϑ2(0), c = ϑ3(0), d = ϑ4(0). Ωに付随するKummer曲面Kを κ : z7→ (ϑ1(2z) : ϑ2(2z) : ϑ3(2z) : ϑ4(2z)) により定まる, Abel多様体J =C2/(Z2+ ΩZ2)からP3(C)への写像κの像と定義する. ϑiは偶関数よりκは準同型写像ではない.しかし, K上の点に対して, 2倍と擬加法を定められる.つまり, 未知のz, z′ ∈ Jに対して, κ(z), κ(z′), κ(z− z′)が既知であれば, κ(2z), κ(z + z′)を計算できる.K上の擬加 法に関する単位元はO = (a, b, c, d)である. P ∈ Jに対して,K上の点をκ(P ) = (ξ1(P ) : ξ2(P ) : ξ3(P ) : ξ4(P )) = (ξ1: ξ2: ξ3: ξ4)と書く. O′をJの 単位元とする.このとき, κ(O′) = Oとなる.Kの射影方程式は以下で与えられる. L : ξ41+ ξ24+ ξ34+ ξ44+ 2Eξ1ξ2ξ3ξ4− F (ξ21ξ 2 4+ ξ 2 2ξ 2 3)− G(ξ 2 1ξ 2 3+ ξ 2 2ξ 2 4)− H(ξ 2 1ξ 2 2+ ξ 2 3ξ 2 4) = 0. 但し, E, F, G, Hはa, b, c, dの有理式である. 次に,主結果について述べる. Gaudry [8]によれば適切な条件の下で,標数0から正標数に還元でき,有限体Fq 上でも2倍と擬加法が成 り立つ.
kを標数が0の体または,有限体とする. a, b, c, d∈ k×とし, kの代数閉包を¯kで表す.次の性質を満たす多 項式δ = (δ1, δ2, δ3, δ4), Biを作れる.任意のP, Q ∈ J(¯k)に対して,定数c′ ∈ ¯k× が存在し, i = 1, 2, 3, 4に 対して, κ([2]P ) = δ(κ(P )), ξi(P + Q)ξi(P − Q) = c′· Bi(κ(P ), κ(Q)). この多項式を用いて, m倍写像を表す多項式を得た. 主定理 1. 任意のm∈ Z≥0, i = 1, 2, 3, 4に対して,以下を満たす斉次多項式µm,i∈ k[ξ1, ...., ξ4]/⟨L⟩が存在 する. µ0,1= a, µ0,2 = b, µ0,3 = c, µ0,4= d, µ1,i= ξi, µ2m,i= δi(µm) (m≥ 1), µ2m+1,iξi= Bi(µm+1, µm) (m≥ 1). 但し, µm= (µm,1, µm,2, µm,3, µm,4)である. また,任意のP∈ J(¯k)に対して, κ([m]P ) = (µm,1(κ(P )) : µm,2(κ(P )) : µm,3(κ(P )) : µm,4(κ(P ))). 主定理1は[12]と同様であるが,違いはKummer曲面の定義の方法である.[12]は[6]で与えられている定 義方程式を用いる.本論文では[8]に基づき, Kummer曲面をテータ関数を用いて定義した場合でも同様であ ることを示した.また,実際に等分多項式を計算するアルゴリズムを構成し,四則演算の回数での計算量を以下 で与えた. 主定理 2. 任意のm ∈ Z>1に対して,等分多項式µmを求めるアルゴリズムの四則演算回数での計算量は
O(m6(log m)2log log m)である.
本論文の構成は以下の通りである.第2章では準備として,テータ関数とKummer曲面の定義と諸公式を述
べる.また, Kummer曲面と種数2の超楕円曲線のヤコビアンとの関係を述べる.第3章では主結果として,等
分多項式の存在を示す.また,等分多項式の計算アルゴリズムと計算量評価を与える.第4章では具体例として,
Kummer曲面上の点のスカラー倍を等分多項式を用いて計算する.
2
Gaudry
による
Kummer
曲面上の擬加法及び
, Kummer
曲面と種数
2
の超
楕円曲線のヤコビアンとの関係
この章では[8]に従って, GaudryによるKummer曲面上の擬加法及び, Kummer曲面と種数2の超楕円曲
線のヤコビアンとの関係を説明する.
2.1
テータ関数と指標付きテータ関数と諸公式
この節では, Kummer曲面を定義するために,テータ関数と指標付きテータ関数の定義,さらに導出される
定義2.1. M (2,C)を2次の複素行列全体とする.このとき,次数2のSiegel上半空間を H2={A ∈ M(2, C) | A =tA, ImA > 0} と定義する. 定義2.2. z∈ C2, Ω∈ H2とする.このとき, Riemannテータ関数を ϑ(z, Ω) = ∑ n∈Z2 exp(πitnΩn + 2πitn· z) と定義する. ϑ(z, Ω)は絶対収束する. 定義2.3. a, b∈ Q2とする.このとき,指標付きテータ関数を ϑ[a; b](z, Ω) = ∑ n∈Z2
exp(πit(n + a)Ω(n + a) + 2πit(n + a)· (z + b)) = exp(πitaΩa + 2πita· (z + b)) · ϑ(z + Ωa + b, Ω)
と定義する.さらに, z = (0, 0)での指標付きテータ関数の値をテータ定数と呼ぶ. 以下では, a, b∈{0,12}2として,指標[a; b]をみる. ϑ[a; b](−z, Ω) = (−1)4ta·bϑ[a; b](z, Ω) が成り立ち, 16個の指標付きテータ関数に番号をつける. 定義2.4. 10個の偶関数の指標付きテータ関数を ϑ1(z) = ϑ[(0, 0); (0, 0)](z, Ω), ϑ2(z) = ϑ [ (0, 0); (1 2, 1 2 )] (z, Ω), ϑ3(z) = ϑ [ (0, 0); (1 2, 0 )] (z, Ω), ϑ4(z) = ϑ [ (0, 0); ( 0,1 2 )] (z, Ω), ϑ5(z) = ϑ [(1 2, 0 ) ; (0, 0) ] (z, Ω), ϑ6(z) = ϑ [(1 2, 0 ) ; ( 0,1 2 )] (z, Ω), ϑ7(z) = ϑ [( 0,1 2 ) ; (0, 0) ] (z, Ω)), ϑ8(z) = ϑ [(1 2, 1 2 ) ; (0, 0) ] (z, Ω), ϑ9(z) = ϑ [( 0,1 2 ) ; (1 2, 0 )] (z, Ω), ϑ10(z) = ϑ [(1 2, 1 2 ) ; (1 2, 1 2 )] (z, Ω)
と定義し, ϑ1(z), ϑ2(z), ϑ3(z), ϑ4(z)を基本テータ関数と呼ぶ.また, 6個の奇関数の指標付きテータ関数を ϑ11(z) = ϑ [( 0,1 2 ) ; ( 0,1 2 )] (z, Ω), ϑ12(z) = ϑ [( 0,1 2 ) ; (1 2, 1 2 )] (z, Ω), ϑ13(z) = ϑ [(1 2, 0 ) ; (1 2, 0 )] (z, Ω), ϑ14(z) = ϑ [(1 2, 1 2 ) ; (1 2, 0 )] (z, Ω), ϑ15(z) = ϑ [(1 2, 0 ) ; (1 2, 1 2 )] (z, Ω), ϑ16(z) = ϑ [(1 2, 1 2 ) ; ( 0,1 2 )] (z, Ω) と定義する.このとき, ϑ11(0) =· · · = ϑ16(0) = 0である.さらに, 2Ωでの4つの指標付きテータ関数を Θ1(z) = ϑ[(0, 0); (0, 0)](z, 2Ω), Θ2(z) = ϑ [(1 2, 1 2 ) ; (0, 0) ] (z, 2Ω), Θ3(z) = ϑ [( 0,1 2 ) ; (0, 0) ] (z, 2Ω), Θ4(z) = ϑ [(1 2, 0 ) ; (0, 0) ] (z, 2Ω) と定義する. 任意のz∈ C2について,以下の2倍公式が成り立つ. ϑ1(z)ϑ1(0) = Θ1(z)2+ Θ2(z)2+ Θ3(z)2+ Θ4(z)2, ϑ2(z)ϑ2(0) = Θ1(z)2+ Θ2(z)2− Θ3(z)2− Θ4(z)2, ϑ3(z)ϑ3(0) = Θ1(z)2− Θ2(z)2+ Θ3(z)2− Θ4(z)2, ϑ4(z)ϑ4(0) = Θ1(z)2− Θ2(z)2− Θ3(z)2+ Θ4(z)2. (2.1) 4Θ1(2z)Θ1(0) = ϑ1(z)2+ ϑ2(z)2+ ϑ3(z)2+ ϑ4(z)2, 4Θ2(2z)Θ2(0) = ϑ1(z)2+ ϑ2(z)2− ϑ3(z)2− ϑ4(z)2, 4Θ3(2z)Θ3(0) = ϑ1(z)2− ϑ2(z)2+ ϑ3(z)2− ϑ4(z)2, 4Θ4(2z)Θ4(0) = ϑ1(z)2− ϑ2(z)2− ϑ3(z)2+ ϑ4(z)2. (2.2) また、任意のz, z′ ∈ C2について,以下の加法公式が成り立つ. ϑ1(z + z′)ϑ1(z− z′) = Θ1(2z)Θ1(2z′) + Θ2(2z)Θ2(2z′) + Θ3(2z)Θ3(2z′) + Θ4(2z)Θ4(2z′), ϑ2(z + z′)ϑ2(z− z′) = Θ1(2z)Θ1(2z′) + Θ2(2z)Θ2(2z′)− Θ3(2z)Θ3(2z′)− Θ4(2z)Θ4(2z′), ϑ3(z + z′)ϑ3(z− z′) = Θ1(2z)Θ1(2z′)− Θ2(2z)Θ2(2z′) + Θ3(2z)Θ3(2z′)− Θ4(2z)Θ4(2z′), ϑ4(z + z′)ϑ4(z− z′) = Θ1(2z)Θ1(2z′)− Θ2(2z)Θ2(2z′)− Θ3(2z)Θ3(2z′) + Θ4(2z)Θ4(2z′). (2.3) 4Θ1(z + z′)Θ1(z− z′) = ϑ1(z)ϑ1(z′) + ϑ2(z)ϑ2(z′) + ϑ3(z)ϑ3(z′) + ϑ4(z)ϑ4(z′), 4Θ2(z + z′)Θ2(z− z′) = ϑ1(z)ϑ1(z′) + ϑ2(z)ϑ2(z′)− ϑ3(z)ϑ3(z′)− ϑ4(z)ϑ4(z′), 4Θ3(z + z′)Θ3(z− z′) = ϑ1(z)ϑ1(z′)− ϑ2(z)ϑ2(z′) + ϑ3(z)ϑ3(z′)− ϑ4(z)ϑ4(z′), 4Θ4(z + z′)Θ4(z− z′) = ϑ1(z)ϑ1(z′)− ϑ2(z)ϑ2(z′)− ϑ3(z)ϑ3(z′) + ϑ4(z)ϑ4(z′). (2.4)
さらに,以下のテータ定数の関係式が成り立つ. ϑ5(0)2ϑ6(0)2= ϑ1(0)2ϑ4(0)2− ϑ2(0)2ϑ3(0)2, ϑ7(0)2ϑ9(0)2= ϑ1(0)2ϑ3(0)2− ϑ2(0)2ϑ4(0)2, ϑ8(0)2ϑ10(0)2= ϑ1(0)2ϑ2(0)2− ϑ3(0)2ϑ4(0)2. (2.5) ϑ5(0)4+ ϑ6(0)4= ϑ1(0)4− ϑ2(0)4− ϑ3(0)4+ ϑ4(0)4, ϑ7(0)4+ ϑ9(0)4=−ϑ1(0)4+ ϑ2(0)4− ϑ3(0)4+ ϑ4(0)4, ϑ8(0)4+ ϑ10(0)4= ϑ1(0)4+ ϑ2(0)4− ϑ3(0)4− ϑ4(0)4. (2.6)
2.2
Gaudry
による
Kummer
曲面上の擬加法
この節ではKummer曲面の定義, Kummer曲面上の擬加法について説明する. 定義2.5. Ω∈ H2とする. Ωに付随するKummer曲面を κ : z7→ (ϑ1(2z) : ϑ2(2z) : ϑ3(2z) : ϑ4(2z)) により定まるC2からP3(C)への写像κの像と定義する. ϑiは同時に0にならない. また, ϑiは次の周期性をもつ.ϑ[(0, 0); b](z + Ωm + n, Ω) = exp(−2πitm· b − πitmΩm− 2πitm· z)ϑ[(0, 0); b](z, Ω).
これより,格子Z2+ ΩZ2分の差がある2つのベクトルは写像κにより同じ点に写される. 従って,写像κ はAbel多様体J =C2/(Z2+ ΩZ2)からの写像とみなせる. Ωに付随するKummer曲面は２次元射影多様 体であり,K(Ω)または,単にKと表す. κによってK上の群構造を定めることはできない. ϑiは偶関数より,任意のz∈ J に対して, κ(z) = κ(−z) である.これより, κは準同型写像ではない.しかし,K上の点に対して, 2倍と擬加法を定められる.つまり,未 知のz, z′ ∈ Jに対して, κ(z), κ(z′), κ(z− z′)が既知であれば,２倍公式(2.1), (2.2)を用いて, κ(2z),加法公 式(2.3), (2.4)を用いて, κ(z + z′)を計算できる. 次に、具体的に2倍アルゴリズムと擬加法アルゴリズムを作るために,Kの射影方程式をみていく. a = ϑ1(0), b = ϑ2(0), c = ϑ3(0), d = ϑ4(0), A = Θ1(0), B = Θ2(0), C = Θ3(0), D = Θ4(0) により,パラメータ化されたKummer曲面K = Ka,b,c,dを考える.以下の関係式は(2.2)にz = 0を代入する ことで得られる. 4A2= a2+ b2+ c2+ d2, 4B2= a2+ b2− c2− d2, 4C2= a2− b2+ c2− d2, 4D2= a2− b2− c2+ d2. (2.7) K上の点の射影座標を(x : y : z : t)と書く.すなわち,あるz∈ C2, λ∈ C×(=C\{0})に対して, x = λϑ1(z), y = λϑ2(z), z = λϑ3(z), t = λϑ4(z)
とする.Kの射影方程式は以下で与えられる. L := x4+ y4+ z4+ t4+ 2Exyzt− F (x2t2+ y2z2)− G(x2z2+ y2t2)− H(x2y2+ z2t2) = 0. 但し, E = 256abcdA 2B2C2D2 (a2d2− b2c2)(a2c2− b2d2)(a2b2− c2d2), (2.8) F = a 4− b4− c4+ d4 a2d2− b2c2 , (2.9) G =a 4− b4+ c4− d4 a2c2− b2d2 , (2.10) H = a 4+ b4− c4− d4 a2b2− c2d2 (2.11) である. E, F, G, H の分母が0になるときがある. (2.5)より, E, F, G, Hの分母はそれぞれ, ϑ5(0), ..., ϑ10(0) の積で表せる.これより,条件を設ける. 条件1. a, b, c, dは0ではなく,他の6つの指標付きテータ定数ϑ5(0), ..., ϑ10(0)も0でない. K上の点を2倍するときに,条件1のみだと問題が起こる.そのため,条件2を設ける. 条件2. 条件1を満たし,さらに, A, B, C, Dも0でない. 以下,K = Ka,b,c,dを条件2を満たすKummer曲面とする. Lと2倍公式(2.1), (2.2)より,点の2倍アルゴリズムを構成できる. Algorithm 1点の2倍アルゴリズム: DoubleKummer(P ) Input: P = (x : y : z : t)∈ K Output: 2P = (X : Y : Z : T )∈ K 1: x′= A12(x 2+ y2+ z2+ t2)2. 2: y′ = 1 B2(x 2+ y2− z2− t2)2. 3: z′= C12(x 2− y2+ z2− t2)2. 4: t′= D12(x 2− y2− z2+ t2)2. 5: X = 1a(x′+ y′+ z′+ t′). 6: Y = 1b(x′+ y′− z′− t′). 7: Z = 1c(x′− y′+ z′− t′). 8: T = 1d(x′− y′− z′+ t′). 9: return (X : Y : Z : T )
また,Lと加法公式(2.3), (2.4)より,点の擬加法アルゴリズムを構成できる. Algorithm 2点の擬加法アルゴリズム: PseudoAddKummer(P, Q, R) Input: P = (x : y : z : t), Q = (x : y : z : t), R = (¯x : ¯y : ¯z : ¯t)∈ K（但し, RはP + QとP− Qのどちら か一方の点であり, ¯x¯y ¯z¯t̸= 0） Output: P + QとP− Qの内Rとは異なる点(X : Y : Z : T )∈ K 1: x′= A12(x2+ y2+ z2+ t2)(x2+ y2+ z2+ t 2). 2: y′ =B12(x 2+ y2− z2− t2)(x2+ y2− z2− t2). 3: z′= C12(x 2− y2+ z2− t2)(x2− y2+ z2− t2). 4: t′= D12(x 2− y2− z2+ t2)(x2− y2− z2+ t2). 5: X = (x′+ y′+ z′+ t′)/¯x. 6: Y = (x′+ y′− z′− t′)/¯y. 7: Z = (x′− y′+ z′− t′)/¯z. 8: T = (x′− y′− z′+ t′)/¯t. 9: return (X : Y : Z : T ) さらに,点の2倍アルゴリズムと擬加法アルゴリズムを組み合わせることで,点のスカラー倍アルゴリズム を構成できる. Algorithm 3点のスカラー倍アルゴリズム Input: n∈ Z>1,P ∈ K（但し,座標に0を持たない.） Output: nP ∈ K 1: if n = 2 then 2: return DoubleKummer(P ). 3: end if 4: n = n02k+ n12k−1+· · · · +nk−12 + nk（n0= 1, ni∈ {0, 1}, k ∈ N）とnを２進展開する. 5: Pn= P . 6: Pp=DoubleKummer(P ). 7: for i = 1, ....k do 8: Q = PseudoAddKummer(Pp, Pm, P ). 9: if ni= 1 then 10: Pp=DoubleKummer(Pp). 11: Pn= Q. 12: else 13: Pn=DoubleKummer(Pm). 14: Pp= Q. 15: end if 16: end for 17: return Pn
K = Ka,b,c,dの方程式Lに対して,次の16個の点がKの結節点である.
(a : b : c : d), (a : b : − c: − d), (a: − b: c: − d), (a: − b: − c: d), (b : a : d : c), (b : a : − d: − c), (b: − a: d: − c), (b: − a: − d: c), (c : d : a : b), (c : d : − a: − b), (c: − d: a: − b), (c: − d: − a: b), (d : c : b : a), (d : c : − b: − a), (d: − c: b: − a), (d: − c: − b: a).
K上の点での擬加法に関する単位元は(a : b : c : d)であり, (a : b : c : d) = Oとおく.
2.3
Kummer
曲面と種数
2
の超楕円曲線のヤコビアンとの関係
この節ではKummer曲面と種数2の超楕円曲線のヤコビアンとの関係について説明する. まず,曲線の方程式とテータ定数の関係をみる. Cを以下で与えられるC上の種数2の曲線とし,右辺は重 根を持たないとする. y2= f (x) = x(x− 1)(x − α)(x − β)(x − γ). 2つのテータ定数に対して, e = ϑ8(0), f = ϑ10(0) とおく.このとき, α = a 2c2 b2d2, β = c2e2 d2f2, γ = a2e2 b2f2 が成り立つ. (2.5), (2.6)より, e4+ f4= a4+ b4− c4− d4, e2f2= a2b2− c2d2 であるから, e2+ f2=±4AB, e2− f2=±4CD である.従って,(e2, f2) =(2(AB + CD), 2(AB− CD)), (2(AB − CD), 2(AB + CD)),
(−2(AB − CD), −2(AB + CD)), (−2(AB + CD), −2(AB − CD))
が成り立つ.よって, e2 f2 = AB + CD AB− CD, AB− CD AB + CD である.以上より,曲線の方程式を基本テータ定数で表すことができる. 次に,Kummer曲面K上の点を曲線Cのヤコビアンに写す関数をみる.
補題2.6. a, b, c, dは条件2を満たすとする.このとき, ϑ7(0)4̸= ϑ9(0)4, ϑ5(0)4̸= ϑ6(0)4, ϑ8(0)4̸= ϑ10(0)4 である. 証明. ϑ8(0)4= ϑ10(0)4と仮定する. ϑ8(0)2 ϑ10(0)2 =AB + CD AB− CD とすると, 1 = A 2B2+ 2ABCD + C2D2 A2B2− 2ABCD + C2D2. これより, ABCD = 0となる.しかし,これは条件2に矛盾する. ϑ8(0)2 ϑ10(0)2 =AB− CD AB + CD のときも同様である.また, ϑ7(0)4̸= ϑ9(0)4, ϑ5(0)4̸= ϑ6(0)4についても同様に成り立つ. ϑ5(z)2, ..., ϑ16(z)2は以下のように基本テータ関数とテータ定数で表すことができる. ϑ5(z)2= ϑ3(z)2ϑ8(0)2ϑ9(0)2+ ϑ2(z)2ϑ7(0)2ϑ10(0)2− ϑ4(z)2ϑ9(0)2ϑ10(0)2− ϑ1(z)2ϑ7(0)2ϑ8(0)2 ϑ9(0)4− ϑ7(0)4 ϑ6(z)2= ϑ4(z)2ϑ7(0)2ϑ8(0)2+ ϑ1(z)2ϑ9(0)2ϑ10(0)2− ϑ3(z)2ϑ7(0)2ϑ10(0)2− ϑ2(z)2ϑ8(0)2ϑ9(0)2 ϑ7(0)4− ϑ9(0)4 ϑ7(z)2= ϑ4(z)2ϑ6(0)2ϑ8(0)2+ ϑ2(z)2ϑ5(0)2ϑ10(0)2− ϑ3(z)2ϑ6(0)2ϑ10(0)2− ϑ1(z)2ϑ5(0)2ϑ8(0)2 ϑ6(0)4− ϑ5(0)4 ϑ8(z)2= ϑ4(z)2ϑ6(0)2ϑ7(0)2+ ϑ3(z)2ϑ5(0)2ϑ9(0)2− ϑ2(z)2ϑ6(0)2ϑ9(0)2− ϑ1(z)2ϑ5(0)2ϑ7(0)2 ϑ9(0)4− ϑ7(0)4 ϑ9(z)2= ϑ3(z)2ϑ5(0)2ϑ8(0)2+ ϑ1(z)2ϑ6(0)2ϑ10(0)2− ϑ4(z)2ϑ5(0)2ϑ10(0)2− ϑ2(z)2ϑ6(0)2ϑ8(0)2 ϑ8(0)4− ϑ10(0)4 ϑ10(z)2= ϑ2(z)2ϑ5(0)2ϑ7(0)2+ ϑ1(z)2ϑ6(0)2ϑ9(0)2− ϑ4(z)2ϑ5(0)2ϑ9(0)2− ϑ3(z)2ϑ6(0)2ϑ7(0)2 ϑ7(0)4− ϑ9(0)4 ϑ11(z)2= ϑ3(z)2ϑ5(0)2ϑ10(0)2+ ϑ1(z)2ϑ6(0)2ϑ8(0)2− ϑ4(z)2ϑ5(0)2ϑ8(0)2− ϑ2(z)2ϑ6(0)2ϑ10(0)2 ϑ6(0)4− ϑ5(0)4 ϑ12(z)2= ϑ4(z)2ϑ6(0)2ϑ10(0)2+ ϑ2(z)2ϑ5(0)2ϑ8(0)2− ϑ3(z)2ϑ6(0)2ϑ8(0)2− ϑ1(z)2ϑ5(0)2ϑ10(0)2 ϑ8(0)4− ϑ10(0)4 ϑ13(z)2= ϑ3(z)2ϑ7(0)2ϑ8(0)2+ ϑ2(z)2ϑ9(0)2ϑ10(0)2− ϑ4(z)2ϑ7(0)2ϑ10(0)2− ϑ1(z)2ϑ8(0)2ϑ9(0)2 ϑ7(0)4− ϑ9(0)4 ϑ14(z)2= ϑ4(z)2ϑ6(0)2ϑ9(0)2+ ϑ3(z)2ϑ5(0)2ϑ7(0)2− ϑ2(z)2ϑ6(0)2ϑ7(0)2− ϑ1(z)2ϑ5(0)2ϑ9(0)2 ϑ7(0)4− ϑ9(0)4 ϑ15(z)2= ϑ3(z)2ϑ9(0)2ϑ10(0)2+ ϑ2(z)2ϑ7(0)2ϑ8(0)2− ϑ4(z)2ϑ8(0)2ϑ9(0)2− ϑ1(z)2ϑ7(0)2ϑ10(0)2 ϑ7(0)4− ϑ9(0)4 ϑ16(z)2= ϑ4(z)2ϑ5(0)2ϑ7(0)2+ ϑ3(z)2ϑ6(0)2ϑ9(0)2− ϑ2(z)2ϑ5(0)2ϑ9(0)2− ϑ1(z)2ϑ6(0)2ϑ7(0)2 ϑ7(0)4− ϑ9(0)4 . よって,結節点でないP = (x : y : z : t)∈ Ka,b,c,dを与えれば, ϑ5(z)2, ..., ϑ16(z)2を計算できる. 以下で, Mumford表現の定義をする.詳細は[13]を参照せよ.
定義2.7. 任意のP∈ J に対して, DP = P1+ P2− 2∞ という形の因子が対応する.但し, P1, P2 ∈ C であり, ∞ は無限遠点である. P1, P2 が無限遠点でなく, P1= (x1, y1), P2(x2, y2), x1̸= x2とする.多項式u, v∈ C[x]を u = (x− x1)(x− x2), v =y1(x− x2) x1− x2 +y2(x− x1) x2− x1 で定義する.組(u, v)を P またはDP の Mumford表現と呼ぶ. P1, P2 が上の条件を満たさない場合も Mumford表現(u, v)が定まる. ϑ16(z)̸= 0のとき, u0= αϑ8(0)2ϑ14(z)2 ϑ10(0)2ϑ16(z)2 , u1= (α− 1)ϑ5(0)2ϑ13(z)2 ϑ10(0)2ϑ16(z)2 − u0− 1 と定義する.このとき, u(x) = u1x + u0がDP のMumford表現のu多項式である. v(x) = v1x + v0とする と, v0２は以下である. v02= −ϑ1(0) 4ϑ 3(0)4ϑ8(0)2ϑ14(z)2 (ϑ2(0)2ϑ4(0)2ϑ10(0)2ϑ16(z)2)3 ( ϑ2(0)2ϑ3(0)2ϑ9(0)4ϑ7(z)2ϑ12(z)2+ ϑ1(0)2ϑ4(0)2ϑ7(0)4ϑ9(z)2ϑ11(z)2 + 2ϑ1(0)2ϑ2(0)2ϑ3(0)2ϑ4(0)2(ϑ1(z)2ϑ3(z)2+ ϑ2(z)2ϑ4(z)2) − 2ϑ1(0)ϑ2(0)ϑ3(0)ϑ4(0)ϑ1(z)ϑ2(z)ϑ3(z)ϑ4(z)(ϑ1(0)2ϑ3(0)2+ ϑ2(0)2ϑ4(0)2) ) . v1はu(x)| (v(x)2− f(x))より,求められる. ϑ16(z) = 0のときはDP のMumford表現のu多項式の次数が2より小さいときの因子に対応しており, u0= αϑ8(0)2ϑ14(z)2 (α− 1)ϑ5(0)2ϑ13(z)2− αϑ8(0)2ϑ14(z)2 となる.因子のMumford表現はこのとき, (x + u0,± √ f (−u0))である. よって,Ka,b,c,dからCのヤコビアンへの写像を得た.ヤコビアンの因子をKに写すアルゴリズムを得るこ とは,方程式を解くことに還元できる.
2.4
有限体
この節では,今までの操作を有限体上でも扱えるようにする. Fqを標数が奇数である有限体とし, a, b, c, dを条件２を満たすFq の元とする.Ka,b,c,dに対応する曲線の方 程式を得たい.しかし, e2, f2を得るには,平方根をとる必要がある.そのため,条件を設ける. 条件3. a, b, c, dは条件2を満す体kの元である.さらに, (2.7)で定義される C2D2 A2B2 はkで平方である.以下,K = Ka,b,c,dを条件3を満たすKummer曲面とする. [8]によれば,曲線Cが通常(ordinary)であれ
3
等分多項式
µ
m この章では等分多項式µmの存在を示し,実際に構成する.3.1
等分多項式
µ
mの存在
この節では等分多項式µmの存在を示す. kを標数が0の体または,標数が2でない有限体とする. P ∈ J(¯k)に対して, κ(P ) = (ξ1(P ) : ξ2(P ) : ξ3(P ) : ξ4(P )) = (x : y : z : t)とする. 簡単のためξi(P )をξiと書く. O′をJの単位元とする.このとき, κ(O′) = Oである. J 上のm倍写像を[m]で表す.K上の点の2倍写像をδ = (δ1, δ2, δ3, δ4)と表す.すなわち, κ([2]P ) = δ(κ(P )) である.2倍公式(2.1), (2.2)より, δiは係数をkにもつ次数4のξ1, ξ2, ξ3, ξ4の斉次多項式である. また,加法 公式(2.3), (2.4)より,任意のP, Q∈ J(¯k), i = 1, 2, 3, 4に対して, ξi(P + Q)ξi(P − Q) = c′· Bi(κ(P ), κ(Q)) (3.1) となる定数c′∈ ¯k×が存在するような係数をkにもつ斉次変数の２つの組(ξ1(P ), ..., ξ4(P )), (ξ1(Q), ..., ξ4(Q)) の双二次形式である多項式Biが存在する.補題3.1. LiをLにξi= 0を代入して得られる多項式とする.このとき, Liはk[ξ1, ...., ξi−1, ξi+1, ...., ξ4]で
既約である. 証明. i = 1のとき, L1= ξ42+ ξ 4 3+ ξ 4 4− F ξ 2 2ξ 2 3− Gξ 2 2ξ 2 4− Hξ 2 3ξ 2 4 である.P2内の曲線Dを D : f(ξ2: ξ3: ξ4) = 0 とする. [2, 命題6.3]よりDが非特異ならば,Dは既約である. 従って,Dが特異点を持たないことを云う.ま ず, L1を各変数で偏微分をする. ∂f ∂ξ2 = 4ξ23− 2F ξ2ξ32− 2Gξ2ξ42, (3.2) ∂f ∂ξ3 = 4ξ33− 2F ξ22ξ3− 2Hξ3ξ42, (3.3) ∂f ∂ξ4 = 4ξ43− 2Gξ22ξ4− 2Hξ32ξ4. (3.4) ξ2 = 0とする. (3.3)より, 4ξ33− 2Hξ3ξ42= 0とする. (3.4)より, 4ξ43− 2Hξ32ξ4= 0とする. ξ3= 0ならば, ξ4= 0であり, ξ4= 0ならば, ξ3= 0である.従って, ξ3ξ4̸= 0とする.これより, (4− H2)ξ32= 0, ξ42= H 2ξ 2 3 を得る.よって, H =±2のときのみ,Cは特異点を持つ.同様にして, ξ3= 0とすると, G =±2のときのみ, Cは特異点を持ち, ξ4= 0とすると, F =±2のときのみ,Cは特異点を持つ. 次に, F, G, H ̸= ±2を云う. H = 2と仮定すると, (2.11)より, a4+ b4− c4− d4= 2(a2b2− c2d2).整理 してa2− b2 =±(c2− d2)を得る.しかし,これは(2.7)と条件２に矛盾する.次に, H =−2と仮定すると, (2.11)より, a4+ b4− c4− d4 =−2(a2b2− c2d2).整理してa2+ b2 =±(c2+ d2)を得る.しかし,これは
(2.7)と条件2に矛盾する.よって, H ̸= ±2である.同様にして, F, G̸= ±2である.従って, Cの特異点は座 標に0を持たない. よって, (3.2), (3.3), (3.4)を 2ξ22− F ξ23− Gξ24= 0, −F ξ2 2+ 2ξ 2 3− Hξ 2 4= 0, −Gξ2 2− Hξ 2 3+ 2ξ 2 4= 0 とする.これを行列に直すと, −F2 −F −G2 −H −G −H 2 ξ 2 2 ξ32 ξ2 4 = 0. 行列式を計算する. det −F2 −F −G2 −H −G −H 2 =−2(F2+ G2+ H2+ F GH− 4) =−2a 2b2c2d2(a2+ b2+ c2+ d2)2(a2+ b2− c2− d2)2(a2− b2+ c2− d2)2(a2− b2− c2+ d2)2 (a2d2− b2c2)2(a2c2− b2d2)2(a2b2− c2d2)2 = −2a 2b2c2d2A2B2C2D2 (a2d2− b2c2)2(a2c2− b2d2)2(a2b2− c2d2)2 ̸= 0. 従って, ξ2 2 ξ2 3 ξ2 4 は自明な解しか持たない.よって, Dは特異点を持たない. i = 2, 3, 4のときも同様に従 う. 定義3.2. イデアルIは,あるm∈ Z≥1に対して, fm∈ Iならば, f ∈ Iを満たすとき,根基イデアルと定義 する.また, I ⊂ k[x0, ..., xn]をイデアルとする.集合 {f ∈ I |あるm∈ Z≥1に対して, fm∈ I} をIの根基といい,√Iと書く. 補題 3.3. I =⟨L, ξi⟩をLとξiにより生成されるk[ξ1, ...., ξ4]のイデアルとする.このとき, Iは素イデアル である.特に, I は根基イデアルである.すなわち,√I = Iである.
証明. R = k[ξ1, ...., ξ4], Ri= k[ξ1, ..., ξi−1, 0, ξi+1, ..., ξ4]とする.環準同型写像ψi: R→ Riを
ψi(g(ξ1, ...., ξ4))7→ g(ξ1, ..., ξi−1, 0, ξi+1, ..., ξ4)
で定義する.このとき, Li= ψi(L)である. IiをLiで生成されるRiのイデアルとする.このとき, I = ψi−1(Ii)
である.補題3.1より, IiはRiの素イデアルである.よって, IはRの素イデアルである.ゆえに, IはRの根
次に[7]に従って,射影多様体に関する準備をする. 定義3.4. イデアルI⊂ k[x0, ..., xn]が各f ∈ Iに対して, f の斉次成分がIに属しているとき, Iは斉次であ ると定義する. 定義3.5. kを体とし, f1, ..., fs∈ k[x0, ..., xn]を斉次多項式とする. V(f1, ..., fs) ={(a0: ... : an)∈ Pn(k)|任意の1≤ i ≤ sに対して, fi(a0, ..., an) = 0} とする. V(f1, ..., fs)を(f1, ..., fs)によって定義された射影多様体と呼ぶ. 定義3.6. 任意の斉次イデアルI⊂ k[x0, ..., xn]に対して, V(I) ={p ∈ Pn(k)|任意のf ∈ Iに対して, f (p) = 0} と定義する.このとき, V(I)は射影多様体である. また,射影多様体V ⊂ Pn(k)に対して, I(V ) ={f ∈ k[x0, ..., xn]|任意の(a0: ... : an)∈ V に対して, f (a0, ..., an) = 0} と定義する. 定理3.7. (射影多様体に対する強零点定理) kを代数閉体とし, I をk[x0, ..., xn]の斉次イデアルとする. V = V(I)がPn(k)の空でない射影多様体なら ば, I(V(I)) =√Iである. 証明. [7, Theorem 9]を参照せよ. 定義3.8. 部分集合S ⊂ Pnに対して, Zariski閉包SをSを含む最小の射影多様体と定義する. 定義 3.9. 射影多様体V ⊂ Pnが既約であることを射影多様体V1, V2に対し, V = V1∪ V2ならば, V = V1 またはV = V2が成り立つことと定義する. 定義 3.10. V を射影多様体とし, S⊂ V とする. ¯S = V が成り立つとき, SがV でZariski稠密であると定 義する. 命題3.11. 射影多様体 V, W ⊂ Pnに対して, V = (V ∩ W ) ∪ (V \W ) が成り立つ. 証明. V は射影多様体であ り, V\W ⊂ V より, V\W ⊂ V である. また, V ∩ W ⊂ V であるから, V ⊃ (V ∩ W ) ∪ (V \W )である.逆についてはV\W ⊂ V \W より, V ⊂ (V ∩ W ) ∪ (V \W )が従う. 命題3.12. 射影多様体V が既約であることは,任意のW ⊊ V である射影多様体W に対して, V\WがV で Zariski稠密であることと同値である. 証明. V を既約とし,任意の W ⊊ V をとる. 命題3.11より, V = W ∪ (V \W )である. V は既約であ り,W ⊊ V より, V = V\Wである.逆について, V1, V2 ⊂ V に対して, V = V1∪ V2であるとする. V1 ⊊ V ならば, V\V1 = V である.また, V\V1⊂ V2より, V\V1⊂ V2である.これより, V ⊂ V2である.すなわち, V = V2である.
定理3.13. 任意のm∈ Z≥0, i = 1, 2, 3, 4に対して,以下を満たす斉次多項式µm,i ∈ k[ξ1, ...., ξ4]/⟨L⟩が存在 する. µ0,1= a, µ0,2 = b, µ0,3 = c, µ0,4= d, µ1,i= ξi, µ2m,i= δi(µm) (m≥ 1), (3.5) µ2m+1,iξi= Bi(µm+1, µm) (m≥ 1). (3.6) 但し, µm= (µm,1, µm,2, µm,3, µm,4)である. 任意のP ∈ J(¯k)に対して, κ([m]P ) = (µm,1(κ(P )) : µm,2(κ(P )) : µm,3(κ(P )) : µm,4(κ(P ))). (3.7) 証明. 帰納法を用いる. m = 0, 1のときは定義より従う. m < nに対して,条件を満たすµm,iが存在すると仮 定する. nが偶数のとき, µn,i= δi(µn 2)で定義すると, (3.5)を満たす.次に, (3.7)より, κ([n 2]P ) = (µn2,1(κ(P )) : µ n 2,2(κ(P )) : µ n 2,3(κ(P )) : µ n 2,4(κ(P ))). 両辺にδを施すと, δκ([n 2]P ) = δ(µn2,1(κ(P )) : µ n 2,2(κ(P )) : µ n 2,3(κ(P )) : µ n 2,4(κ(P ))). よって, κ([n]P ) = (µn,1(κ(P )) : µn,2(κ(P )) : µn,3(κ(P )) : µn,4(κ(P ))). これより, nが偶数のときは成り立つ.次に, nが奇数のとき, n = 2l + 1とおく.このとき,任意のP ∈ J(¯k) に対し, ξi([2l + 1]P )ξi(P ) = c′Bi(κ([l + 1]P ), κ([l]P )) となるc′∈ ¯k×が存在する. i = 1, 2, 3, 4に対し, gi∈ k[ξ1, ..., ξ4]を gi= Bi(µl+1, µl) と定義する.つまり, ξi([2l + 1]P )ξi(P ) = c′gi(κ(P ))である.このとき, ξi(Q) = 0なる任意のQ∈ J(¯k)に対 して, gi(κ(Q)) = 0である.従って,定理3.7より, gi∈ √ ⟨L, ξi⟩¯kである.但し,⟨L, ξi⟩k¯はLとξiにより生成 されるk[ξ¯ 1, ..., ξ4]のイデアルである. gi∈ k[ξ1, ..., ξ4]より, gi∈ √ ⟨L, ξi⟩k¯∩ k[ξ1, ..., ξ4] = √ ⟨L, ξi⟩k.但し, ⟨L, ξi⟩kはLとξiにより生成されるk[ξ1, ..., ξ4]のイデアルである.補題3.3より, √ ⟨L, ξi⟩k =⟨L, ξi⟩kが成 り立つ.従って,あるg1,i, g2,i∈ k[ξ1, ..., ξ4]に対して,
gi= g1,iξi+ g2,iL. (3.8)
となる. g1,i= µn+1,iとすれば, (3.6)が成り立つ.
であり, i = 1, 2, 3, 4に対して, ξi(P )̸= 0ならば, ξi([2l + 1]P ) = c′µ2l+1,i(κ(P )). ゆえに, κ([2l + 1]P ) = (ξ1([2l + 1]P ) : ξ2([2l + 1]P ) : ξ3([2l + 1]P ) : ξ4([2l + 1]P )) = (c′µ2l+1,1(κ(P )) : c′µ2l+1,2(κ(P )) : c′µ2l+1,3(κ(P )) : c′µ2l+1,4(κ(P ))) = (µ2l+1,1(κ(P )) : µ2l+1,2(κ(P )) : µ2l+1,3(κ(P )) : µ2l+1,4(κ(P ))) (3.9) が成り立つ. U ={P ∈ J(¯k) | i = 1, 2, 3, 4に対して, ξi(P )̸= 0}, T ={P ∈ J(¯k) | κ([2l + 1]P ) = (µ2l+1,1(κ(P )), ...µ2l+1,4(κ(P )))} と定義する.このとき, (3.9)より, U ⊂ T である.定義よりT は射影多様体である.よって, U ⊂ T である. また, J (¯k)\Uは射影多様体である. W = J (¯k)\U ⊊ J(¯k)とする. JはAbel多様体であるから,既約である. 従って,命題3.12より, J (¯k)\W = J(¯k)\(J(¯k)\U) = U はJ (¯k)でZariski稠密である.よって, U = J (¯k)で ある. ゆえに, T = J (¯k)である.これより, nが奇数のときも成り立つ. 補足 3.14. µ2m+1,i は[4]より, Gr¨obner基底を使って計算できる.また,以下の初等的な操作でも計算でき る. (3.8)でg2,iはξiを含まないとして良い. hiを(3.8)のξiに0を代入して得られる多項式とする.このと
き, hi= g2,iLiである.従って, g2,i=Lhii を計算でき, g1,i=
gi−g2,iL ξi も計算できる. 補題3.15. 任意のm≥ 0, i = 1, 2, 3, 4に対して, deg(µm,i) = m2である. 証明. 帰納法を用いる. m = 0, 1のときは定義より従う. m < nに対して, deg(µm,i) = m2であると仮定 する. n が偶数のとき, µn,i = δi(µn 2)が成り立つ. δi は次数４の斉次多項式であり, deg µ n 2,i = n2 4 より,
deg(µn,i) = n2が成り立つ.次に, nが奇数のとき, n = 2l + 1とおく. µ2l+1ξi= Bi(µl+1, µl)より,
deg(µ2l+1ξi) = deg(Bi(µl+1, µl)) deg(µ2l+1) + deg(ξi) = 2(l + 1)2+ 2l2 deg(µ2l+1) + 1 = 4l2+ 4l + 2 deg(µ2l+1) = (2l + 1)2.
3.2
等分多項式
µ
mの構成と計算量評価
この節では等分多項式µmを構成し,計算量を評価する. 2倍公式(2.1), (2.2)より, δを構成できる.Algorithm 4２倍アルゴリズム: δ(µm) Input: µm= (µm,1, µm,2, µm,3, µm,4) Output: µ2m 1: S = A12 + 1 B2 + 1 C2 + 1 D2. 2: T = A12 + 1 B2 − 1 C2 − 1 D2. 3: U = A12 − 1 B2 + 1 C2 − 1 D2. 4: V = A12 − 1 B2 − 1 C2 + 1 D2. 5: M1= µ4m,1+ µ4m,2+ µ4m,3+ µ4m,4. 6: M2= µ2m,1µ2m,2+ µ2m,3µ2m,4. 7: M3= µ2m,1µ2m,3+ µ2m,2µ2m,4. 8: M4= µ2m,1µ2m,4+ µ2m,2µ2m,3. 9: µ2m,1= 1a(SM1+ 2T M2+ 2U M3+ 2V M4). 10: µ2m,2= 1b(T M1+ 2SM2+ 2V M3+ 2U M4). 11: µ2m,3= 1c(U M1+ 2V M2+ 2SM3+ 2T M4). 12: µ2m,4= 1d(V M1+ 2U M2+ 2T M3+ 2SM4). 13: return (µ2m,1, µ2m,2, µ2m,3, µ2m,4) アルゴリズム4はアルゴリズム1を展開したものである.
また,加法公式(2.3), (2.4),補足3.14より,擬加法アルゴリズムを構成できる. Algorithm 5擬加法アルゴリズム: η(µm+1, µm) Input: µm+1, µm Output: µ2m+1 1: S = A12 + 1 B2 + 1 C2 + 1 D2. 2: T = A12 + 1 B2 − 1 C2 − 1 D2. 3: U = A12 − 1 B2 + 1 C2 − 1 D2. 4: V = A12 − 1 B2 − 1 C2 + 1 D2. 5: N1= µ2m+1,1µ2m,1+ µ2m+1,2µm,22 + µ2m+1,3µ2m,3+ µ2m+1,4µ2m,4. 6: N2= µ2m+1,1µ2m,2+ µ2m+1,2µm,12 + µ2m+1,3µ2m,4+ µ2m+1,4µ2m,3. 7: N3= µ2m+1,1µ2m,3+ µ2m+1,2µm,42 + µ2m+1,3µ2m,1+ µ2m+1,4µ2m,2. 8: N4= µ2m+1,1µ2m,4+ µ2m+1,2µm,32 + µ2m+1,3µ2m,2+ µ2m+1,4µ2m,1. 9: g1= SN1+ T N2+ U N3+ V N4. 10: g2= T N1+ SN2+ V N3+ U N4. 11: g3= U N1+ V N2+ SN3+ T N4. 12: g4= V N1+ U N2+ T N3+ SN4. 13: for i = 1, ..., 4 do 14: hi= gi(ξ1, ..., ξi−1, 0, ξi+1, ..., ξ4). 15: Li = L(ξ1, ..., ξi−1, 0, ξi+1, ..., ξ4). 16: µ2m+1,i = (gi− (hi/Li)L)/ξi. 17: end for 18: return (µ2m+1,1, µ2m+1,2, µ2m+1,3, µ2m+1,4) アルゴリズム5のステップ13まではアルゴリズム2を展開したものである.
さらに, 2倍アルゴリズムと擬加法アルゴリズムを組み合わせることで,スカラー倍アルゴリズムを作れる. Algorithm 6スカラー倍アルゴリズム Input: m∈ Z>1 Output: µm 1: if m = 2 then 2: return δ(µ1). 3: end if 4: m = m02k+ m12k−1+· · · + mk−12 + mk（m0= 1, ni∈ {0, 1}, k ∈ N）とmを２進展開する. 5: µm= µ1. 6: µp= δ(µ1). 7: for i = 1, ....k do 8: ν = η(µp, µm). 9: if mi= 1 then 10: µp= δ(µp). 11: µm= ν. 12: else 13: µm= δ(µm). 14: µp= ν. 15: end if 16: end for 17: return µm
アルゴリズムの計算量をkの四則演算の回数で評価する. Aを単位元をもつ任意の可換環とする. M (n)
を２つのA係数 1 変数n 次多項式の乗算に必要な Aの演算回数とする. このとき, [5]より, M (n) =
O(n log n log log n)ととれる.任意の多項式f ∈ A[z1, ..., zn]に対して, df,j = degzjf + 1と定義し, df =
df,1· · · df,nと定義する. [9]より,任意の多項式f, g∈ Aに対して,積h = f gは以下のKronecker代入を用 いて計算できる. Kdh :A[z1, ..., zn]−→ A[x], f 7−→ f(x, xdh1, xdh,1dh,2, ..., xdh,1···dh,n−1). とし, h = Kd−1 h(Kdh(f )Kdh(g))を計算すればよい. 命題3.16. 積h = f gはM (dh)回のAにおける演算で計算できる. 証明. [9, Proposition 2]を参照せよ. アルゴリズム4について, µm,iは4変数m2次斉次多項式である. µm,iに対して, ξ4 = 1と非斉次化し, 3 変数m2次多項式にしたものをµ′m,iとする.このとき, 1≤ i, j ≤ 4に対して, dµ′2m,iµ′2m,j = (4m2+ 1)3であ
る.従って,命題3.16より, µ′2m,iµ′2m,jの計算量はO(m6log m log log m)である.他の計算は定数の乗除である
から問題ない.よって,アルゴリズム4の計算量はO(m6log m log log m)である.
アルゴリズム5について, 1 ≤ i, j ≤ 4に対して, dµ′2
m+1,iµ′2m,j = ((2m + 1)
2+ 2)3である.従って,命題
3.16より, µ′2m+1,iµ′2m,i の計算量はO(m6log m log log m)である. g
i, hi, L, Li に対して,非斉次化したもの をそれぞれ, g′i, h′i, L′, L′i とする.h′i は2変数 {(2m + 1)2+ 1} 次多項式であり,項数は 3H{(2m+1)2+1} = 2(4m4+ 8m3+ 11m2+ 7m + 3)項である. L′ iは2変数4次多項式であり,項数は6項である.よって, h′i/L′iの 計算量はO(m4)である.また, L′は3変数4次多項式であり, 11項であるから, (h′ i/L′i)L′の計算量はO(m4) である. g′iは3変数{(2m + 1)2+ 1}次多項式より, g′ i− (h′i/L′i)L′の計算量もO(m4)である. ξiでの割り算 は指数を一つずらすだけである.他の計算は定数の乗除であるから問題ない.よって, (gi′− (h′i/L′i)L′)/ξiの計
算量はO(m4)である.よって,アルゴリズム5の計算量はO(m6log m log log m)である.
アルゴリズム6の繰り返し回数は⌊log2m⌋回である.従って,以下の定理を得る.
定理3.17. 任意のm∈ Z>1に対して,等分多項式µmを求めるアルゴリズム6のkの四則演算回数での計算
量はO(m6(log m)2log log m)である.
4
具体例
F17上の種数2の曲線Cを y2= x(x− 1)(x − 2)(x − 3)(x − 10) ととる.このとき, fe22 = 7とすると, O = (a : b : c : d) = (4 : 1 : 8 : 6)と選べる.これより, Kの射影方程式は 以下である. L := x4+ y4+ z4+ t4+ 2xyzt + 6(x2t2+ y2z2)− 6(x2z2+ y2t2) + 5(x2y2+ z2t2) = 0.このとき, µ2= (µ2,1, µ2,2, µ2,3, µ2,4), µ3= (µ3,1, µ3,2, µ3,3, µ3,4)は以下である. µ2,1= 2(x4+ y4+ z4+ y4) + 13(x2y2+ z2t2) + 7(x2z2+ y2t2) + 14(x2t2+ y2z2), µ2,2= 9(x4+ y4+ z4+ y4) + 16(x2y2+ z2t2) + 5(x2z2+ y2t2) + 11(x2t2+ y2z2), µ2,3= 6(x4+ y4+ z4+ y4) + 7(x2y2+ z2t2) + 2(x2z2+ y2t2) + 15(x2t2+ y2z2), µ2,4= 16(x4+ y4+ z4+ y4) + 16(x2y2+ z2t2) + 3(x2z2+ y2t2) + 14(x2t2+ y2z2). µ3,1 = x9+ (−4y2− 2z2+ 2t2)x7+ (4y4+ 6y2z2− z4− 6y2t2− 2z2t2− t4)x5 + (4y6− 5y4z2+ 3y2z4+ z6+ 5y4t2+ y2z2t2+ 8z4t2+ 3y2t4− 8z2t4− t6)x3 + (6y8− 6y6z2− 4y4z4− 5y2z6− 8z8+ 6y6t2+ y4z2t2+ 2y2z4t2+ 4z6t2 − 4y4t4− 2y2z2t4− 7z4t4+ 5y2t6+ 4z2t6− 8t8)x + 5y7zt + (7z3t− 7zt3)y5+ (3z5t− 6z3t3+ 3zt5)y3+ (−6z7t− 7z5t3+ 7z3t5+ 6zt7)y, µ3,2 = y9+ (−4x2+ 2z2− 2t2)y7+ (4x4− 6x2z2− z4+ 6x2t2− 2z2t2− t4)y5 + (4x6+ 5x4z2+ 3x2z4− z6− 5x4t2+ x2z2t2− 8z4t2+ 3x2t4+ 8z2t4+ t6)y3 + (6x8+ 6x6z2− 4x4z4+ 5x2z6− 8z8− 6x6t2+ x4z2t2− 2x2z4t2+ 4z6t2 − 4x4t4+ 2x2z2t4− 7z4t4− 5x2t6+ 4z2t6− 8t8)y + 6xz7t + (3x3t + 7xt3)z5+ (−7x5t− 6x3t3− 7xt5)z3+ (5x7t + 7x5t3+ 3x3t5− 6xt7)z, µ3,3 = z9+ (−2x2+ 2y2− 4t2)z7+ (−x4− 2x2y2− y4+ 6x2t2− 6y2t2+ 4t4)z5 + (x6+ 8x4y2− 8x2y4− y6+ 3x4t2+ x2y2t2+ 3y4t2− 5x2t4+ 5y2t4+ 4t6)z3 + (−8x8+ 4x6y2− 7x4y4+ 4x2y6− 8y8− 5x6t2+ 2x4y2t2− 2x2y4t2+ 5y6t2 − 4x4t4+ x2y2t4− 4y4t4− 6x2t6+ 6y2t6+ 6t8)z
+ 5xyt7+ (7x3y− 7xy3)t5+ (3x5y− 6x3y3+ 3xy5)t3+ (−6x7y− 7x5y3+ 7x3y5+ 6xy7)t,
µ3,4 = t9+ (2x2− 2y2− 4z2)t7+ (−x4− 2x2y2− y4− 6x2z2+ 6y2z2+ 4z4)t5
+ (−x6− 8x4y2+ 8x2y4+ y6+ 3x4z2+ x2y2z2+ 3y4z2+ 5x2z4− 5y2z4+ 4z6)t3 + (−8x8+ 4x6y2− 7x4y4+ 4x2y6− 8y8+ 5x6z2− 2x4y2z2+ 2x2y4z2− 5y6z2 − 4x4z4+ x2y2z4− 4y4z4+ 6x2z6− 6y2z6+ 6z8)t
+ 6x7yz + (7y3z + 3yz3)x5+ (−7y5z− 6y3z3− 7yz5)x3+ (−6y7z + 3y5z3+ 7y3z5+ 5yz7)x.
µ4= δ(µ2)も計算でき, P = (5 : 3 : 4 : 11)∈ Kとすると, 2P = (1 : 13 : 2 : 10), 3P = (12 : 14 : 13 : 6), 4P = Oである.
5
謝辞
本研究は,著者が首都大学東京大学院理工学研究科数理情報科学専攻博士前期課程在学中に,同大学院理工学 研究科数理情報科学専攻の内田幸寛准教授の指導のもとに行ったものである.適切な助言を賜り,熱心に指導し てくださった内田幸寛准教授に深く感謝いたします.そしてご多忙の中,本論文の副査を快諾していただきまし た内山成憲教授と徳永浩雄教授に深く感謝いたします.また,２年間多くの苦楽を共にした髙田尚樹氏や,今ま で支えていただいた家族にも深く感謝いたします.参考文献
[1] 大西良博，Abel函数論 ，中央大学数学教室講究録 6，http://ir.c.chuo-u.ac.jp/repository/
search/binary/p/4118/s/2343/，2013.
[2] 難波誠，代数曲線の幾何学，現代数学社，京都，1991.
[3] 松尾和人，超楕円曲線暗号と位数計算，情報セキュリティ総合科学 第2巻，pp. 43-61，2010.
[4] T. Becker and V. Weispfenning，Gr¨obner Bases，Grad. Texts in Math. 141，Springer，New York，
1993.
[5] D. G. Cantor and E. Kaltofen，On fast multiplication of polynomials over arbitrary algebras，Acta Inform. 28 (1991)，no. 7，pp. 693-701.
[6] J. W. S. Cassels and E. V. Flynn，Prolegomena to a Middlebrow Arithmetic of Curves of Genus 2，
Cambridge Univ.Press，Cambridge，1996.
[7] D. Cox, J. Litlte and D. O’Shea，Ideals, Varieties, and Algorithms: An Introduction to Computa-tional Algebraic Geometry and Commutative Algebra，4th ed.，Springer，Cham，2015
[8] P. Gaudry，Fast genus 2 arithmetic based on Theta functions，J. Math. Cryptol. 1(2007)，no. 3，
pp. 243–265.
[9] J. van der Hoeven and G. Lecerf，On the bit-complexity of sparse polynomial and series multipli-cation，J. Symbolic Comput. 50(2013)，pp. 227–254 .
[10] D. Mumford，Tata Lectures on Theta I，Progress in Mathematics 28. Birkh¨auser，Boston，1983. [11] D. Mumford，Tata Lectures on Theta II，Progress in Mathematics 43. Birkh¨auser，Boston，1984. [12] Y. Uchida，Canonical local heights and multipulication formulas for the Jacobians of curves of genus
2，Acta Arith. 149(2011)，pp. 111–130.
[13] L. C. Washington，Elliptic Curves : Number Theory and Cryptography，2nd ed.，Chapman & Hall/CRC，Boca Raton，2008.
