修 士 学 位 論 文

修 士 学 位 論 文

論文題名

楕円離散対数問題に対する

elliptic net

^{を用いた指数計算法}

 指導教授 内田 幸寛 准教授 平成

30

年

1

月

10

日 提出

首都大学東京 大学院

 理工学研究科 数理情報科学専攻  学修番号

16878323

氏名 髙田 尚樹

目 次

1

^はじめに

3

2 ECDLP

に対する指数計算法

3

2.1

^{楕円曲線および}

ECDLP

^の定義

. . . . 4

2.2 Semaev’s summation polynomial . . . . 5

2.3 Stange’s elliptic net . . . . 5

2.4

指数計算法

. . . . 6

2.5 Weil descent . . . . 7

2.6 ECDLP

に対する

summation polynomial

を用いた指数計算法

. . . . 9

2.7

^計算量

. . . . 10

3

主結果

11 3.1 elliptic net

の行列式表示

. . . . 11

3.2 ECDLP

に対する

elliptic net

を用いた指数計算法

. . . . 14

3.3

^計算量

. . . . 15

4

まとめ

17

5

^謝辞

17

1

はじめに

楕円曲線暗号は現在広く使用されている代表的な公開鍵暗号方式の一つである

.

また

,

実用化が 進められている公開鍵暗号方式としてペアリング暗号が挙げられる

.

これらの公開鍵暗号方式は 楕円離散対数問題

(ECDLP)

の難解さによって安全が保たれており

, ECDLP

が解かれてしまうと 暗号も解読されてしまう

. ECDLP

を解読する一つの攻撃として指数計算法がある

.

^{指数計算法に} おいて楕円曲線上の点の分解が必要となる

. Semaev

^は

[1]

において点の分解に使用する道具とし て

summation polynomial

^を提案し

, Gaudry, Diem

は指数計算法においてこれを用いた

.

^さらに 篠原らは

[2]

において

,

指数計算法に

summation polynomial

を用いた場合の計算量を考察した

.

点 の分解に利用できる他の方法として齋藤らは

[3]

において

Stange

の

elliptic net

を用いている

.

本 論文ではまず

ellitic net

を行列式の形で以下のように表した

.

主定理

. Ψ

v

(z)

^において

v = (v

1

, · · · , v

n

) = (1, · · · , 1)

としたとき以下の等式が成り立つ

.

c

n

× Ψ

v

(z) =

1 ℘(z

1

) ℘

^′

(z

1

) · · · ℘

⁽ⁿ⁻²⁾

(z

1

) 1 ℘(z

2

) ℘

^′

(z

2

) · · · ℘

⁽ⁿ⁻²⁾

(z

2

)

.. . .. . .. . . .. .. .

1 ℘(z

_n

) ℘

^′

(z

_n

) · · · ℘

⁽ⁿ⁻²⁾

(z

_n

)

∏

1≤s<t≤n

( − ℘(z

_s

) + ℘(z

_t

))

但し

c

n

= (−1)

^{(n−1)(n2 −2)}

1! 2! · · · (n − 1)!

^であり

, ℘(z

i

)

^は

Weierstrass

^の

℘

^{関数である}

.

^さらに

℘(z

i

) = x

i

, ℘

^′

(z

i

) = 2y

iとすると次が得られる

.

1 ℘(z

1

) ℘

^′

(z

1

) · · · ℘

⁽ⁿ⁻²⁾

(z

1

) 1 ℘(z

2

) ℘

^′

(z

2

) · · · ℘

⁽ⁿ⁻²⁾

(z

2

)

.. . .. . .. . . .. .. . 1 ℘(z

_n

) ℘

^′

(z

_n

) · · · ℘

⁽ⁿ⁻²⁾

(z

_n

)

= d

n

×

1 x

1

y

1

x

12

x

1

y

1

· · · · 1 x

2

y

2

x

22

x

2

y

2

· · · · .. . .. . .. . .. . .. . . .. .. . 1 x

_n

y

_n

x

_n²

x

_n

y

_n

· · · ·

但し右辺各行の末項は

n

が偶数のとき

x

_iⁿ²

, n

が奇数のとき

x

_iⁿ⁻³²

y

_iであり

, d

_n

= 1! 2! · · · (n − 1)!.

さらに主定理と

[3]

の定理より次の系を得た

.

系

.

^有限体

F

qと

P

i

= (x

i

, y

i

)

^{である楕円曲線上の点}

P

1

, · · · , P

n

∈ E(F

q

)(

^但し

P

i

̸= O

^かつ

P

i

̸=

±P

j

)

^に対して

P

1

+ · · · + P

n

= O ⇐⇒

1 x

1

y

1

x

12

x

1

y

1

· · · · 1 x

2

y

2

x

22

x

2

y

2

· · · ·

.. . .. . .. . .. . .. . . .. .. .

1 x

n

y

n

x

n2

x

n

y

n

· · · ·

= 0

この系を指数計算法に適用することで点の分解において解かなくてはならない連立方程式の 構成にかかる計算量を考察した

.

結果

,

連立方程式の構成にかかる計算量は理論上

summation polynomial

を用いた場合より小さくなることがわかった

.

以下

2

章で楕円曲線

, ECDLP, summation polynomial, elliptic net

の定義および先行研究である

summation polynomial

を用いた指数計算法 について述べ

, 3

章で本論文の主定理の証明および計算量の評価を与え

, 4

^{章でまとめを行う}

.

2 ECDLP

に対する指数計算法

ECDLP

に対する攻撃法の一つとして知られる指数計算法

(index calculus)

について説明する

.

2.1

楕円曲線および

ECDLP

の定義 楕円曲線および

ECDLP

の定義を与える

.

定義

2.1.

^標数が

2, 3

^でない体

K

^上の

3

^次曲線

E : y

²

= x

³

+ Ax + B (A, B ∈ K

であり

4A

³

+ 27B

²

̸ = 0

を満たす

)

を

K

^{上の楕円曲線という}

.

集合

E(K)

^{を次のように定める}

.

E(K) := { (x, y) ∈ K

²

| y

²

= x

³

+ Ax + B } ∪ {O}

(

^但し

, O

^{は無限遠点とする）}

次のように演算を定義することで

E(K)

^{は加法群を成す}

.

• P

i

:= (x

_i

, y

_i

) ∈ E(K).

• O

^{を単位元とする}

.

• P

1の逆元を

−P

1

:= (x

_i

, − y

_i

)

とする

.

• P

1

̸ = −P

2のとき

P

3を次のように定める

. – x

₁

̸ = x

₂のとき

P

3

:= P

1

+ P

2

x

₃

= λ

²

− x

₁

− x

₂

, y

₃

= − λx

₃

− y

₁

+ λx

₁

(

但し

λ = y

₂

− y

₁

x

₂

− x

₁

) – x

1

= x

2のとき

P

3

:= 2P

1

x

3

= λ

²

− 2x

1

, y

3

= − λx

3

− y

1

+ λx

1

(

^但し

λ = 3x

12

+ A 2y

1

)

さらに

m ∈ N

^に対して

m

個の

P

^の和を

m P

^と表す

.

但し

( − m) P := − (m P ) , 0 P := O

^とす る

.

体

K

が有限体

,

即ちある素数べき

q

に対して

K = F

qのとき

, E( F

q

)

は有限群となる

.

従って

P ∈ E( F

q

)

を生成元として有限巡回群

⟨P⟩

^{を構成できる}

.

一般の離散対数問題（

Discrete Logarithm Problem

^{）について説明する}

.

^有限群

G

^上（位数

#G =: n

^）の

DLP

^とは

,

^{与えられた}

g, T ∈ G

^{に対して次を満たす}

X ∈ Z /n Z

^{が存在するならば} それを求める問題である

. (X = log

_g

T

^とかく

. )

T = g

^X

有限群

G

が

E( F

q

)

であるとき

,

その離散対数問題を 楕円離散対数問題（

Elliptic Curve Discrete Logarithm Problem

） と呼ぶ

.

即ち

ECDLP

とは

T , P ∈ E( F

q

)

（位数

#E( F

q

) =: N

）に対して 次を満たす

X ∈ Z /N Z

が存在するならばそれを求める問題である

.

T = X P

2.2 Semaev’s summation polynomial

指数計算法で

ECDLP

を解くには点の分解が必要である

. Semaev

は標数が２でも３でもない体

K

^{上の楕円曲線}

E

^{が与えられた場合に}

,

分解に使用する道具として

summation polynomial

^を提

案し

, Gaudry

^と

Diem

は指数計算法においてこれを用いた

.

定理

2.2. q

^は

5

以上の奇数素数べきとし

, E : y

²

= x

³

+ Ax + B

^は

K

^{上の楕円曲線とする}

.

^この

とき

2 ≤ m ∈ N

^に対して

m-summation polynomial S

mを次のように定義できる

.

S

2

(X

1

, X

2

) =X

1

− X

2

S

₃

(X

₁

, X

₂

, X

₃

) =(X

₁

− X

₂

)

²

X

₃²

− 2((X

₁

+ X

₂

)(X

₁

X

₂

+ A) + 2B)X

₃

+ (X

₁

X

₂

− A)

²

− 4B(X

₁

+ X

₂

)

S

m

(X

1

, · · · , X

m

) =Res

X

(S

m−M

(X

1

, · · · , X

m−M−1

, X), S

M+2

(X

m−M

, · · · , X

m

, X)) (if m ≥ 4, 1 ≤ M ≤ m − 3)

但し

, Res

^{は終結式とする}

. m ≥ 3

^のとき

, S

mは絶対既約で対称な多項式であり

,

^{さらに各変数}

X

i

に対して

deg

_Xi

(S

_m

) = 2

^m−2である

.

S

mには点の分解に利用できる次の性質がある

[1].

定理

2.3. x

₁

, · · · , x

_m

∈ K (K : K

の代数閉包

)

が

S

_m

(x

₁

, · · · , x

_m

) = 0

を満たすことと

,

P

1

+ · · · + P

m

= O

なる

P

i

= (x

_i

, y

_i

) ∈ E(K)

が存在することは同値である

.

2.3 Stange’s elliptic net

Semaev

の方法以外に点の分解を行う方法を述べる

.

^齋藤らは

[3]

^において

Stange’s elliptic net

を用いた方法を述べた

.

使用する楕円関数について説明する

.

^まず

, Weierstrass ℘

^関数を

℘(z) = 1

z

²

+ ∑

ω∈L,ω̸=0

( 1

(z − ω)

²

− 1 ω

²

)

と定義する

.

^ここで

L

^は

C

^{上の格子である}

.

℘

関数は以下の性質をもつ

[4].

• ℘( − z) = ℘(z)

• ℘

^′

(z) = − 2 ∑

ω∈L 1

(z−ω)³

= −

_z²3

+ · · ·

• ℘

^′

(−z) = −℘

^′

(z)

• ℘(z

₁

+ z

₂

) =

^{(℘′(z2)−℘′(z1))2}

4(℘(z2)−℘(z1))²

− ℘(z

₁

) − ℘(z

₂

)

• ℘ (

^′

(z)

²

= 4℘(z)

³

− g

2

℘(z) − g

3

但し

g

2

= 60 ∑

ω∈L,ω̸=0 1

ω⁴

, g

3

= 140 ∑

ω∈L,ω̸=0 1 ω⁶

)

次に

Weierstrass σ

関数を

σ(z) = z ∏

ω∈L,ω̸=0

( 1 − z

ω )

exp ( z

ω + z

²

2ω

²

)

と定義する

.

^{さらに整数値ベクトル}

v = (v

1

, · · · , v

n

) ∈ Z

^nと変数

z = (z

1

, · · · , z

n

) ∈ C

^{nに対して}

Ψ

_v

(z) = σ(v

₁

z

₁

+ · · · + v

_n

z

_n

)

∏

1≤i≤n

σ(z

_i

)

^{2vi2−∑nj=1vivj}

∏

1≤i<j≤n

σ(z

_i

+ z

_j

)

^vivj とする

.

^このとき

Ψ

v

(z

i

)

^は各変数

z

iに関して楕円関数である

.

Stange

^は

[5]

^において

Ψ

vが

F

q上の楕円曲線に対しても定義できることを示した

.

定理

2.4.

^有限体

F

qと楕円曲線上の点

P

1

, · · · , P

n

∈ E( F

q

)(

^但し

P

i

̸ = O

^かつ

P

i

̸ = ±P

j

if i ̸ = j)

に対して

v

₁

P

1

+ · · · + v

_n

P

n

= O ⇐⇒ Ψ

_v

( P

1

, · · · , P

n

) = 0

この定理は

[5, Theorem 3]

より従う

.

楕円曲線上の点

P

1

, · · · , P

n

∈ E( F

q

)

に対して写像

W : Z

ⁿ

→ F

q

, v 7→ Ψ

v

( P

1

, · · · , P

n

)

を

P

1

, · · · , P

nによる

elliptic net

という

.

2.4

指数計算法

有限巡回群

G = ⟨ g ⟩

^上の

T = g

^X

(g, T ∈ G, X ∈ Z /(#G) Z )

で与えられた

DLP

に対する指数計 算法の概要を述べる

.

step 1

因子基底

F := { f

₁

, · · · , f

_s

} ⊂ G

を設定する

.

step 2 (i) a, b ∈ N

^を選び

R = g

^a

T

^b

∈ G

を計算する

.

(ii)

次の等式を満たす

e

_l

∈ Z

_≥0の組

(e

₁

, · · · , e

_s

)

が存在するか判定し

,

存在するならばそれ を計算する

.

R =

∏

s l=1

f

_l^el

この等式は

relation

と呼ばれる

.

この

relation

から因子基底の元および

T

の離散対数を 解とする線形方程式

a + bX ≡

∑

s l=1

e

_l

log

_g

f

_l

(mod #G)

が生成される

.

実際の計算では

(a, b)

と

(e

₁

, · · · , e

_s

)

を結合したベクトルを行列の行と して保存する

.

(iii) (i)

と

(ii)

の計算を十分な個数の

relation

が得られるまで繰り返す

.

step 3 step 2

で得られた行列に対して

, #G

を法とする行列操作を行うことで次を満たす

X

1

, X

2

を計算する

.

e = g

^X1

T

^X2

(e : G

の単位元

)

step 4 X

₂⁻¹

(mod #G)

が存在するならば次を返す

.

X ≡ − X

₁

X

₂⁻¹

(mod #G)

指数計算法で

E( F

qⁿ

)

^に対する

ECDLP

^{を解く場合}

, step 1

^{で設定する因子基底を}

F = { F

₁

, · · · , F

_s

}

とする

. step 2

^{において選んだ}

a, b ∈ N

^に対して

R = aP + bT

を計算する

.

次に

R

^{を因子基底}

F

^の和

R =

∑

s l=1

e

_l

F

_l

で表す

.

即ち点の分解が必要となる

.

^{分解が可能であれば}

log

_P

R ≡

∑

s l=1

e

l

log

_P

F

l

(mod # ⟨P⟩ )

を得る

.

ここで定理

2.3

を利用して

R

^を

F

^{のいくつかの元の和で}

R = F

l1

+ · · · + F

lm

のように表すことを考える

. R

^の

x

座標を

x( R )

と表記する

. S

_m+1の

x

_m+1に

x( R )

を代入した 等式

S

_m+1

(X

₁

, · · · , X

_m

, x( R )) = 0 (1)

に解

(X

1

, · · · , X

m

) ∈ ( F

qⁿ

)

^{mが存在したとする}

.

^このとき

,

^各

X

iに対して

X

i

= x(F

li

)

^なる

F

li

∈ F

が存在するならば

relation

^{が得られる}

.

等式に解が存在しない場合や

, F

に対応する点が存在しな い場合は

R

を取り直して計算を行う

.

代数方程式

(1)

を効率良く解くために

, Frobenius

写像を利用した等式と

(1)

から構成される次の 連立代数方程式を解く方法がある

.

 

 

 



 

 

 

0 = S

m+1

(X

1

, · · · , X

m

, x(R)) 0 = X

₁^qn

− X

₁

.. .

0 = X

_m^qn

− X

_m

(2)

次に

,

連立代数方程式

(2)

を解くために

Weil descent

を導入する

.

2.5 Weil descent

Weil descent

を紹介し

,

それを連立代数方程式

(2)

を解くために利用する方法を述べる

.

まず

, Weil descent

に関する以下の補題を紹介する

.

補題

2.5.

素数べき

q

と自然数

n

に対して

, F

qⁿ を

n

次元の

F

q ベクトル空間としてみたときの 基底を

{ θ

₁

, · · · , θ

_n

}

^とする

.

さらに

f (X

₁

, · · · , X

_m

) ∈ F

qⁿ

[X

₁

, · · · , X

_m

]

とする

.

このとき

Z :=

{ z

_i,j

| 1 ≤ i ≤ m, 1 ≤ j ≤ n }

^に対して

,

次の等式を満たす

f

_k

(Z) ∈ F

q

[Z]

が唯一つ存在する

. f (z

_1,1

θ

₁

+ · · · + z

_1,n

θ

_n

, · · · , z

_m,1

θ

₁

+ · · · + z

_m,n

θ

_n

) =

∑

n k=1

θ

_k

f

_k

(Z)

さらに

,

^ある

(X

1

, · · · , X

m

) ∈ ( F

qⁿ

)

^{mに対して}

f(X

1

, · · · , X

m

) = 0

^{であるならば}

,

^ある

z

i,j

∈ F

q

が存在して次の条件を満たす

. X

_i

=

∑

n j=1

z

_i,j

θ

_j

, f

_k

(Z) = 0 (1 ≤ k ≤ n)

補題

2.5

^における

f (X

1

, · · · , X

m

)

^を

(1)

の左辺の多項式としたときに

, Weil descent

^{によって連} 立代数方程式

(2)

^は

F

q係数の

mn

^変数の

n + mn

個 の等式から成る次の形の連立代数方程式に変 換される

.

 

 

 

 

 

 



 

 

 

 

 

 

0 = f

1

(Z) .. .

0 = f

_n

(Z ) 0 = z

_1,1^q

− z

_1,1

.. .

0 = z

_m,n^q

− z

_m,n

(3)

Weil descent

^{によって代数方程式}

(3)

^{は元の代数方程式}

(2)

より変数と等式の個数は増加するが

,

扱う多項式の次数を

q

よりも小さくできるという利点がある

.

さらに因子基底の設定の工夫によ り連立代数方程式の変数の個数を減らすことが出来る

.

^まず

F

qⁿ のある

F

qベクトル部分空間を

V

とし

, dim V = n

^′

(1 ≤ n

^′

≤ n)

^とする

.

^{このとき因子基底}

F

^{を次のように定める}

.

F = {F ∈ E(F

qⁿ

)|x(F) ∈ V } = {F

1

, · · · , F

s

}

この因子基底の設定により

X

_i は

Weil descent

によって

n

^′ 個の変数

z

_i,j

(1 ≤ j ≤ n

^′

)

で表され るため

,

^方程式

(1)

^は

F

q係数の

mn

^′変数の

n

^′個 の代数方程式に変換される

.

^{それらの代数方程} 式に

Frobenius

^{写像に対応する等式}

z

i,jq

− z

i,j

= 0

を加えた次の連立代数方程式を解く

. (

^但し

Z

^′

:= { z

i,j

| 1 ≤ i ≤ m, 1 ≤ j ≤ n

^′

} ⊊ Z

^で

z

i,j

∈ Z

^′とする

)

 

 

 

 

 

 



 

 

 

 

 

 

0 = f

₁

(Z

^′

) .. .

0 = f

_n

(Z

^′

) 0 = z

_1,1^q

− z

_1,1

.. .

0 = z

_m,n′q

− z

_m,n′

(4)

n

^′を小さくすることで

(4)

の変数が少なくなることにより解くために必要な計算コストは削減

されるが

, (4)

が解を持つ確率も下がってしまう

.

2.6 ECDLP

に対する

summation polynomial

を用いた指数計算法

指数計算法に

Semaev

の

summation polynomial

と

Weil descent

を導入し

, ECDLP

に対して適 用する方法がある

. E( F

qⁿ

)

に対する

ECDLP

が

T = X P ∈ ⟨P⟩ ⊂ E( F

qⁿ

)

として与えられている とする

.

以下に概要を述べる

[2].

step 1

^因子基底

F = {F ∈ E(F

qⁿ

)|x(F ) ∈ V } = {F

1

, · · · , F

s

}

^{を設定する}

.

step 2 (i) a, b ∈ N

^を選び

R = a P + b T

^{を計算する}

.

(ii) Semaev

の

summation polynomial S

_m+1の

X

_m+1に

x( R )

を代入し

,

それに対して

Weil descent

を適用し連立代数方程式

(4)

^{を計算する}

.

 

 

 

 

 

 



 

 

 

 

 

 

0 = f

₁

(Z

^′

) .. .

0 = f

n

(Z

^′

) 0 = z

1,1q

− z

1,1

.. .

0 = z

_m,n′q

− z

_m,n′

この連立代数方程式に解

(z

_1,1

, · · · , z

_m,n′

) ∈ ( F

q

)

^mn′が存在するならば

,

その解に対応す る

(X

1

, · · · , X

m

) ∈ (F

q

)

^{mを求める}

.

^即ち

V

^の基底

θ

1

, · · · , θ

n^′

∈ F

qⁿに対して

X

i

=

n^′

∑

j=1

z

i,j

θ

j

∈ V

を計算する

.

そのような一つの組

(X

₁

, · · · , X

_m

)

に対して

(X

1

, · · · , X

m

) = (x(F

l1

), · · · , x(F

lm

))

を満たす因子基底の元の組

(F

_l1

, · · · , F

_lm

)

は高々

2

^m個存在する

. (

各元で

x

座標に対し て正と負の二つの

y

座標が考えられるため

)

その中から

R =

∑

m i=1

F

li

を満たすものを求め

,

^{次の等式を満たす}

e

l

∈ Z

≥0の組

(e

1

, · · · , e

s

)

^{を決定する}

. R =

∑

s l=1

e

_l

F

_l

(5)

この

relation(5)

は次の線形方程式に対応する

. a + bX ≡

∑

s l=1

e

_l

log

_P

F

_l

(mod # ⟨P⟩ )

実際の計算では

(a, b)

^と

(e

1

, · · · , e

s

)

を結合したベクトルを行列の行として保存する

.

(iii) (i)

と

(ii)

の計算を十分な個数の

relation

が得られるまで繰り返す

.

step 3 step 2

で得られた行列に対して

, # ⟨P⟩

を法とする行列操作を行うことで次を満たす

X

₁

, X

₂ を計算する

.

O = X

₁

P + X

₂

T step 4 X

₂⁻¹

(mod #⟨P⟩)

が存在するならば次を返す

.

X ≡ − X

₁

X

₂⁻¹

(mod # ⟨P⟩ ) 2.7

計算量

前述の

ECDLP

^に対する

Semaev

^の

summation polynomial

^と

Weil descent

^{を導入した指数計} 算法の計算量の評価をする

[2].

計算量は

F

qⁿでの演算回数とする

.

ただしここでは

q ≪ n

の場合 を考える

. (q ≫ n

の場合については

[6]

参照

)

まず

, S

_m+1の

m

と

n

^′

(= dim V )

は

mn

^′

= n

となるように設定される

[7].

また

, S

_m+1の生成に 必要な体演算は

O(2

^m2

) (6)

であることが知られている

[7].

step 2

^において

R

^が

R = ∑

_m

l=1

F

_lと表される確率を考える

.

準備として因子基底の個数

s

^は

s ≈ #V = q

^n′

(7)

として良い

.

これはランダムに選んだ

x

_i

∈ F

qⁿを与えられた楕円曲線の

x

座標として持つ有理点 が存在する確率が約

1/2

であり

,

同じ

x

座標を持つ有理点の個数の期待値が約

2

となるからであ る

.

求める確率は因子基底に属する

m

個の点の和でかくことができる有理点

R ∈ E( F

qⁿ

)

の割合 で見積もるため

,

^{そのような}

m

個の点の和において現れる重複を無視できるものとしている

.

^和 の対称性を考慮すると

,

^{因子基底から}

m

個の点を選ぶ組み合わせはおよそ

s

^m

/m!

^である

.

^さらに

#E( F

qⁿ

) ≈ q

^nと

(7)

より求める確率は次のようになる

. s

^m

m! × q

ⁿ

≈ 1

m! (8)

これと

step 3

^{で扱う行列のランクが}

O(#V ) = O(s)

^より

, step 2

において行われる点の分解の回 数は

O(m!s) = O(m!q

^n′

)

となる

.

よってあとは点の分解の計算コストを

C

とすれば

step 2

の計算量は

O(q

^n′

m!C) (9)

である

.

step 3

^{の計算量は}

,

^{実行可能行列乗算指数}

2 < ω ≤ 3

^に対して

O(s

^ω

) = O(q

^n′ω

) (10)

となる

.

従って

(6), (9), (10)

^{より全体の計算量は}

O(2

^m2

+ q

^n′

m!C + q

^n′ω

) (11)

となる

.

点の分解の計算量

C

とは連立代数方程式

(4)

を解くために必要な計算量である

. (

詳細は

[2]

参照

)

3

主結果

3.1 elliptic net

の行列式表示

主定理

. Ψ

_v

(z)

において

v = (v

₁

, · · · , v

_n

) = (1, · · · , 1)

としたとき以下の等式が成り立つ

.

c

_n

× Ψ

_v

(z) =

1 ℘(z

1

) ℘

^′

(z

1

) · · · ℘

⁽ⁿ⁻²⁾

(z

1

) 1 ℘(z

₂

) ℘

^′

(z

₂

) · · · ℘

⁽ⁿ⁻²⁾

(z

₂

)

.. . .. . .. . . .. .. .

1 ℘(z

n

) ℘

^′

(z

n

) · · · ℘

⁽ⁿ⁻²⁾

(z

n

)

∏

1≤s<t≤n

( − ℘(z

_s

) + ℘(z

_t

)) (12)

但し

c

n

= ( − 1)

^{(n−1)(n−2)2}

1! 2! · · · (n − 1)!

^であり

, ℘(z

i

)

^は

Weierstrass

^の

℘

^{関数である}

.

^さらに

℘(z

_i

) = x

_i

, ℘

^′

(z

_i

) = 2y

_iとすると次が得られる

.

1 ℘(z

1

) ℘

^′

(z

1

) · · · ℘

⁽ⁿ⁻²⁾

(z

1

) 1 ℘(z

2

) ℘

^′

(z

2

) · · · ℘

⁽ⁿ⁻²⁾

(z

2

)

.. . .. . .. . . .. .. . 1 ℘(z

n

) ℘

^′

(z

n

) · · · ℘

⁽ⁿ⁻²⁾

(z

n

)

= d

_n

×

1 x

1

y

1

x

12

x

1

y

1

· · · · 1 x

2

y

2

x

22

x

2

y

2

· · · · .. . .. . .. . .. . .. . . .. .. . 1 x

n

y

n

x

n2

x

n

y

n

· · · ·

(13)

但し右辺各行の末項は

n

が偶数のとき

x

_iⁿ²

, n

が奇数のとき

x

_iⁿ⁻²³

y

_iであり

, d

_n

= 1! 2! · · · (n − 1)!.

証明

. Hermite, Frobenius, Stickelberger

によって次の等式が与えられている

[8, p. 458].

c

_n

× σ(z

1

+

^・・・

+ z

n

) ∏

1≤s<t≤n

σ(z

s

− z

t

) σ(z

₁

)

ⁿ・・・

σ(z

_n

)

ⁿ

=

1 ℘(z

1

) ℘

^′

(z

1

) · · · ℘

⁽ⁿ⁻²⁾

(z

1

) 1 ℘(z

2

) ℘

^′

(z

2

) · · · ℘

⁽ⁿ⁻²⁾

(z

2

)

.. . .. . .. . . .. .. . 1 ℘(z

n

) ℘

^′

(z

n

) · · · ℘

⁽ⁿ⁻²⁾

(z

n

)

(14)

但し

c

_n

= ( − 1)

^{(n−1)(n2 −2)}

1! 2!

・・・

(n − 1)!.

さらに等式

[8, p. 451]

σ(z + y)σ(z − y)

σ(z)

²

σ(y)

²

= − ℘(z) + ℘(y)

より次が得られる

.

∏

1≤s<t≤n

σ(z

_s

+ z

_t

)σ(z

_s

− z

_t

)

σ(z

s

)

²

σ(z

t

)

²

= ∏

1≤s<t≤n

( − ℘(z

_s

) + ℘(z

_t

)) (15)

(14)

^の左辺を

(15)

^{の左辺で割る}

. c

n

× σ(z

1

+ · · · + z

n

) ∏

1≤s<t≤n

σ(z

s

− z

t

)

σ(z

₁

)

ⁿ

· · · σ(z

_n

)

ⁿ

× ∏

1≤s<t≤n

σ(z

s

)

²

σ(z

t

)

²

σ(z

_s

+ z

_t

)σ(z

_s

− z

_t

)

= c

n

× ∏ σ(z

1

+ · · · + z

n

)

1≤s<t≤n

σ(z

s

+ z

t

) × σ(z

1

)

²⁽ⁿ⁻¹⁾

· · · σ(z

n

)

²⁽ⁿ⁻¹⁾

σ(z

1

)

ⁿ

· · · σ(z

n

)

ⁿ

= c

_n

× σ(z

₁

+ · · · + z

_n

)

∏

1≤i≤n

σ(z

i

)

²⁻ⁿ

∏

1≤s<t≤n

σ(z

s

+ z

t

)

= c

n

× Ψ

v

(z) (

^但し

v = (v

1

, · · · , v

n

) = (1, · · · , 1))

よって定理の

(12)

の左辺を得る

. (14)

の右辺を

(15)

の右辺で割れば明らかに

(12)

の右辺である ため

(12)

が示された

.

次に

(13)

を示す

.

楕円曲線の定義式

y

²

= x

³

+ Ax + B

と

℘

関数の性質

℘

^′

(z)

²

= 4℘(z)

³

− g

₂

℘(z) − g

₃

(16)

より対応

℘(z

_i

) = x

_i

, 1

2 ℘

^′

(z

_i

) = y

_i がわかる

.

まず

,

ある定数があって

(13)

が成り立つことを示し

,

その後定数が

d

_nであることを示す

. (13)

と後に出てくる

(17)

を帰納法を用いて示す

. n = 1

の場合は明らかである

.

n = 2

の場合

,

1 ℘(z

₁

) 1 ℘(z

2

) =

1 x

₁

1 x

2

^であり

, n = 3

の場合

,

1 ℘(z

₁

) ℘

^′

(z

₁

) 1 ℘(z

2

) ℘

^′

(z

2

) 1 ℘(z

3

) ℘

^′

(z

3

)

=

1 x

₁

2y

₁

1 x

2

2y

2

1 x

3

2y

3

= 2

1 x

₁

y

₁

1 x

2

y

2

1 x

3

y

3

なので

(13)

^{は成立する}

.

次に

n = 2k − 2

と

n = 2k − 1

の場合

(13)

を仮定する

.

列基本変形を行うことを考慮して具体的 には定数

α, β

を用いて

 

 

 



 

 

 

℘

^(2k−4)

(z) =

k−1

∑

i=0

α

_2k−4,i

℘(z)

ⁱ

+

k−3

∑

j=0

β

_2k−4,j

℘(z)

^j

℘

^′

(z) (17a)

℘

^(2k−3)

(z) =

k−1

∑

i=0

α

_2k−3,i

℘(z)

ⁱ

+

k−2

∑

j=0

β

_2k−3,j

℘(z)

^j

℘

^′

(z) (17b)

と表せると仮定する

.

ある行について成立することが示されれば十分なので

z

iを単に

z

^と表記す る

.

^実際

, (17a)

^{を項別微分すると}

(17b)

の形で表すことが出来る

.

^{微分の計算の中で}

(16)

^とこれ を微分して得られる

℘

^′′

(z) = 6℘(z)

²

− g

₂

2

を用いる

. (17b)

^{を項別微分すると}

,

℘

^(2k−2)

(z) =

k−1

∑

i=1

iα

2k−3,i

℘(z)

ⁱ⁻¹

℘

^′

(z) +

k−2

∑

j=1

β

2k−3,j

{j℘(z)

^j−1

℘

^′

(z)

²

+ ℘(z)

^j

℘

^′′

(z)}

=

k−1

∑

i=1

iα

2k−3,i

℘(z)

ⁱ⁻¹

℘

^′

(z)

+

k−2

∑

j=1

β

_2k−3,j

{ j℘(z)

^j−1

(4℘(z)

³

− g

₂

℘(z) − g

₃

) + ℘(z)

^j

(6℘(z)

²

− g

₂

2 ) }

=

k−1

∑

i=1

iα

_2k−3,i

℘(z)

ⁱ⁻¹

℘

^′

(z)

+

k−2

∑

j=1

{ β

_2k−3,j

(4j + 6)℘(z)

^j+2

− β

_2k−3,j

(g

2

j + g

2

2 )℘(z)

^j

− jβ

_2k−3,j

g

3

℘(z)

^j−1

}

= β

2k−3,k−2

(4(k − 2) + 6)℘(z)

^k

+ {℘(z)

^{k−1以下の項}

} + {℘(z)

^k−2

℘

^′

(z)

^以下の項

}

となり

, ℘(z)

^k以外の項は適当な列で列基本変形を行えば消去できるためまず

n

が偶数の場合成り 立つことがわかった

.

^つまり

℘

^(2k−2)

(z) =

∑

k i=0

α

_2k−2,i

℘(z)

ⁱ

+

k−2

∑

j=0

β

_2k−2,j

℘(z)

^j

℘

^′

(z)

と表せるので

,

これをさらに項別微分する

.

℘

^(2k−1)

(z) =

∑

k i=1

iα

_2k−2,i

℘(z)

ⁱ⁻¹

℘

^′

(z) +

k−2

∑

j=1

β

_2k−2,j

{ j℘(z)

^j−1

℘

^′

(z)

²

+ ℘(z)

^j

℘

^′′

(z) }

= kα

_2k−2,k

℘(z)

^k−1

℘

^′

(z) + { ℘(z)

^k以下の項

} + { ℘(z)

^k−2

℘

^′

(z)

以下の項

}

となり

, ℘(z)

^k−1

℘

^′

(z)

以外の項は適当な列で列基本変形を行えば消去できるため

n

が奇数の場合 も成り立つことがわかる

.

よって

(17)

が成り立つことがわかり

,

ある定数

d

_nに対して

(13)

が成り 立つ

.

最後に定数

d

nを決定する

.

℘(z) = 1

z

²

+ ∑

ω∈L,ω̸=0

( 1

(z − ω)

²

− 1 ω

²

)

で定義していたので

,

これを微分することで次を得る

.

℘

^(k)

(z) = ( − 1)

^k

(k + 1)!

z

^k+2

+ · · · (18)

ここで

n = 2k

のとき

(17a)

よりある定数

d

^′_2kに対して

℘

^(2k−2)

(z) = d

^′_2k

x

^k

+ · · ·

^{と表すことでき} るが

, (18)

より

℘

^(2k−2)

(z) = (2k − 1)!

z

^2k

+ · · · (19)

であり

,

x

^k

= ℘(z)

^k

= 1

z

^2k

+ · · · (20)

である

.(19)

と

(20)

を比べると

d

^′_2k

= (2k − 1)! (21)

となることがわかる

.

さらに

n = 2k + 1

のとき

(17b)

よりある定数

d

^′_2k+1に対して

℘

^(2k−1)

(z) = d

^′_2k+1

x

^k−1

y + · · ·

^と 表すことできるが

,

℘

^(2k−1)

(z) = − (2k)!

z

^2k+1

+ · · · (22)

であり

,

x

^k−1

= ℘(z)

^k−1

= 1

z

^2k−2

+ · · · , y = 1

2 ℘

^′

(z) = − 1 z

³

+ · · ·

より

x

^k−1

y = − 1

z

^2k+1

+ · · · (23)