数理解析研究所講究録 1420 巻 2005 年 41-62

41A Weil Descent Attack against
Elliptic Curve Cryptosystems over
Quartic Extension Fields
Institute of tnf.ofmationSecurity
SeigoArita(長尾 (関東学院大).. 松尾 (IISEC)* 志村 (中大) 各氏との共同研究)目次
1. Introduction
DLP
Gaud\gamma 法
Wei{ desoent at{ack2,Scholten form [of )Definition
Eltiptic curves in Scholten forms

3. 禍$\mathrm{E}\mathrm{C}$$\mathrm{e}\mathrm{i}\mathrm{l}$

.

d伽

廿下

$\mathrm{s}\epsilon \mathrm{e}\mathrm{n}\mathrm{t}-\mathrm{a}$$\mathrm{c}\mathrm{k}$for genus 2HEC

42$\mathrm{f}$. In\S r 屋 d 火$\mathrm{e}\xi^{\sim}\dot{\S}Q\mathrm{n}$離散対数型暗号$\mathrm{G}$: 有限アーベル群$\mathrm{G}\ni \mathrm{g}$を固定指数関数 E

離散対数問題$<\mathrm{g}>\ni \mathrm{h}$に対して$\mathrm{E}(\mathrm{n})=\mathrm{h}$となる$\mathrm{n}$を求めよ

離散対数問題が困難ならば,
群 G を用いて公開鍵暗号が構成できる (ElGamal)

43

超楕円曲線暗号
GF(\psi 上の種数 g の超楕円曲線$\mathrm{H}(\mathrm{g}\ll \mathrm{q})$$\mathrm{y}^{2}=\mathrm{f}(\mathrm{x})=\mathrm{x}^{2\mathrm{g}+1}+\mathrm{a}_{1}\mathrm{x}^{2\mathrm{g}+}.$

超楕円曲線 H のヤコビ群.

$,$$+\mathrm{a}_{2\mathrm{g}+1}(\mathrm{a}_{\mathrm{i}}\in \mathrm{G}\mathrm{F}(\mathrm{q}))$$\mathrm{J}_{\mathrm{H}}$$\mathrm{J}_{\mathrm{H}}=\{(\mathrm{u}(\mathrm{x}), \mathrm{v}(\mathrm{x}))|\deg \mathrm{v}<\deg \mathrm{u}\leqq \mathrm{g}, \mathrm{v}^{2}=\mathrm{f}(\mathrm{m}\mathrm{o}\mathrm{d} \mathrm{u})\}$.

$\#\mathrm{J}_{\mathrm{H}}^{\cdot}=$$\mathrm{q}^{\mathrm{g}}$超楕円曲線 H 上の離散対数問題 (DLP)$\mathrm{J}_{\mathrm{H}}\ni \mathrm{D}_{1},$$\mathrm{D}_{2}$に対して$\mathrm{D}_{2}=\mathrm{n}\mathrm{D}_{1}$となる を求めよ$\mathrm{n}$–POIIard の rho アルゴリズム$\mathrm{J}_{\mathrm{H}}\ni \mathrm{D}_{1},$$\mathrm{D}_{2}$random walk によって$\mathrm{D}_{1}$, D2 のランダムな線形和瓦を計算していく$\mathrm{R}_{\mathrm{i}}=\alpha_{\mathrm{i}}\mathrm{D}_{1}+\beta_{\mathrm{i}}\mathrm{D}_{2}$衝突 Ri$=\mathrm{R}_{\mathrm{j}}$$(\mathrm{i}=1,2,3,\ldots)$が起きると$’..\mathrm{D}_{2}=(\alpha_{\mathrm{i}}-\alpha_{\mathrm{j}})/(\beta_{\mathrm{j}}\alpha_{\mathrm{i}}\mathrm{D}_{1}+\beta_{\mathrm{i}}\mathrm{D}_{2}=\alpha_{\mathrm{j}}\mathrm{D}_{1}+-\beta_{\mathrm{i}})\mathrm{D}_{1}\beta_{\mathrm{j}}\mathrm{D}_{2}$$\ovalbox{\tt\small REJECT}$$(\#\mathrm{J}_{\mathrm{H}})^{1/2}$

step が必要44$\mathrm{G}\mathrm{a}\mathrm{u}\mathrm{d}\mathrm{r}\mathrm{y}^{f}\mathrm{s}$$\mathrm{J}_{\mathrm{H}}\ni \mathrm{D}$法が smooth

D が定義体上の有理点の和: 超楕円曲線 H 上の全ての有理点$\mathrm{F}\mathrm{B}=\{\mathrm{P}_{1}, \mathrm{P}_{\underline{?}}, \ldots, \mathrm{P}_{\mathrm{w}}\}$

を計算しておく$\mathrm{J}_{\mathrm{H}}\ni \mathrm{D}_{1},$$\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}_{0\mathrm{l}}\mathrm{n}$$\mathrm{D}_{2}$walk によって$\mathrm{D}_{1}$, D2 のランダムな線形和$\mathrm{R}_{\mathrm{i}}=\alpha_{\mathrm{i}}\mathrm{D}_{1}+\beta_{\mathrm{i}}\mathrm{D}_{2}$smooth な$(\mathrm{w}.=.\mathrm{q}, \mathrm{O}(\mathrm{q}))$$\mathrm{R}_{\mathrm{i}}$$\mathrm{R}_{\mathrm{i}}$を計算 :$(\mathrm{i}=1,2,3,\ldots)$

を集める

Gaudry’s 法 (2)smooth な瓦がみつかると:($\mathrm{g}!$個に一つは snlooth)$\mathrm{R}_{\mathrm{i}}=(.\mathrm{u}(\mathrm{x}), \mathrm{v}(\mathrm{x}))$$\mathrm{u}(\mathrm{x})=$垣$(\mathrm{x}- \mathrm{x}_{\mathrm{i}})$:GF(q) 上 1 次の既約因子に分解$(\mathrm{O}(\mathrm{q}))$$\mathrm{y}_{\mathrm{i}}=\mathrm{v}(\mathrm{x}_{\mathrm{i}})$焦$(\mathrm{i}=1,..\iota’ \mathrm{g})$$=(\mathrm{x}_{1},\mathrm{y}_{1})+(\mathrm{x}_{2},\mathrm{y}_{2})+\ldots+(.\mathrm{x}_{\mathrm{g}}, \mathrm{y}_{\mathrm{g}})$$=\Sigma_{\mathrm{k}}$勇,$\mathrm{P}_{\mathrm{k}}$$\mathrm{k}$このようにしてsmooth な$\mathrm{R}_{\dot{\tau},\wedge}$$[\Re_{1}.,’ \mathrm{m}_{\mathrm{i},\underline{?}},\ldots., \mathrm{m}_{\mathrm{i},\mathrm{w}}]$

45

Gaudry’s 法 (3)smooffi な$\mathrm{R}_{\mathrm{i}}=\mathrm{Z}_{\mathrm{k}}\mathrm{m}_{\mathrm{i},\mathrm{k}}\mathrm{P}_{\mathrm{k}}$が:$\mathrm{M};=(\mathrm{m}_{\mathrm{i},\mathrm{k}})$$(\gamma_{\mathrm{i}})\in \mathrm{K}\mathrm{e}\mathrm{r}\mathrm{M}$を求めて$\mathrm{w}’(>\mathrm{w})$個あつまると$\mathrm{w}’ \mathrm{x}\mathrm{w}$$(\mathrm{O}(\mathrm{q}^{2}))$

:

行列, 疎

$(\mathrm{O}(\mathrm{q}^{2}))$$\Sigma_{\mathrm{i}}\gamma_{\mathrm{i}}\mathrm{R}_{\mathrm{i}}=0$,$\mathrm{D}_{2}=\lambda \mathrm{D}_{1}$.

$\Sigma_{\mathrm{i}}\gamma_{\mathrm{i}}(\alpha_{\mathrm{i}}\mathrm{D}_{1}+\beta_{\mathrm{i}}\mathrm{D}_{2})=0$を代入すると$\lambda=(-\Sigma\gamma_{\mathrm{i}}\alpha_{\mathrm{i}})(\Sigma\gamma_{\mathrm{i}}\beta_{\mathrm{i}})^{-1}$$\ovalbox{\tt\small REJECT}$.

Gaudxy 法

超楕円曲線上の DLP に対する攻撃法$\mathrm{r}\mathrm{h}\mathrm{o}$アルゴリズムに因子基底を導入
, 種数
(定義体:

$\mathrm{O}(\mathrm{q}^{2}\log^{\mathrm{c}}(\mathrm{q}))$$\mathrm{G}\mathrm{F}(\mathrm{q})$種数を大きくしても,$\mathrm{q}$$\mathrm{s}$)は小さくできない !

Cab 曲線や superelliptic 曲線に対してもGau 的’ 法は有効$\mathrm{g}\ll \mathrm{q}$$4\mathrm{G}$Cab 曲線とCab 曲線 :$\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{e}||\dot{|}\mathrm{p}\mathrm{t}\mathrm{i}\mathrm{c}$曲線$(\mathrm{a},\mathrm{b})=1$$\sum_{0\leq i\leq b,0\leq j\leq \mathrm{a},ai+bj\leq ab}\alpha_{i,j}x^{i}y^{j}=0$superellipfic 曲線:$(\mathrm{n}, \delta)=1$$\mathrm{y}^{\mathrm{n}}=\mathrm{a}_{\delta}\mathrm{x}^{\delta}+\ldots.+\mathrm{a}_{0}$明らかに,superelliptic 曲線$\subset$

Cab 曲線実装実験 一パラメータ
有限体
定義方程式
1 +24740
種数6. ヤコビアンの位数
43- 806897062301623960531898661’ 自己同型の位数3$\mathrm{G}\mathrm{F}(84211)$–$\mathrm{x}-7+32427\mathrm{y}^{\Lambda}3--\wedge 0.$.

$\cdot$$\cdot 7$

17 ビットの素体上の 93 ビット C37
自己同型$\phi$$\phi(\mathrm{x}, \mathrm{y})=\dot{(}\xi_{7}\mathrm{x},$$\xi_{3}\mathrm{y})$: 位数 21

よって$\#\mathrm{F}\mathrm{B}=84211/21=4010.\cdot*$.
$7^{!}|$

47

結果

実装実験

有理点の収集 (PA.RI-GP)—–
スムー な要素の収集
一次方程式の求解$.(\mathrm{C})$$\lambda.$.

5 分 13 秒.t.
2 時間 33 分 6 秒.
$\cdot$$-(\mathrm{C})--$.-....–32 分 2 秒.

3 時間

合計17 ビットの素二上の 93 ビット
Pentium II
266$\cdot.$$\mathrm{C}_{37}$$.\mathrm{t}1$.

分$2\mathrm{t}$秒曲線に対する Gaudry’s variant の適用.

$\mathrm{M}\mathrm{H}\mathrm{z}$禍 eil descent attack$K=\mathrm{F}_{\mathrm{q}\mathfrak{n}}$$H.\cdot$.

$/k=\mathrm{F}_{\mathrm{q}}$an alg.e 化 raiC CUiVe

over

$k$

48

The concept : Frey ‘98(some of]over char. 2: Gau& y,Hess,over char. 2
fieids: Galbraith ‘00(some of)over char. 3: Arita ’00(some of]
, HCC over odd char. fmite fields : Diem$\mathrm{E}\mathrm{C}\mathrm{C}$$\mathrm{f}\mathrm{n}\dot{\mathrm{u}}\mathrm{t}\mathrm{e}\mathrm{f}_{1}\mathrm{e}1\mathrm{d}\mathrm{s}$$\cdot$$\mathrm{S}\mathrm{n}\mathrm{l}\mathrm{a}\overline{\dot{\mathrm{L}}}\mathrm{t}’ 00$$\mathrm{f}_{1}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}$$(_{\backslash }\mathrm{s}\mathrm{o}\mathrm{m}\mathrm{e}\mathrm{o}\mathfrak{h}\mathrm{H}\mathrm{C}\mathrm{C}$$\mathrm{E}\mathrm{C}\mathrm{C}$$\mathrm{f}_{1}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{f}_{1}\mathrm{e}1\mathrm{d}\mathrm{s}$$\mathrm{E}\mathrm{C}\mathrm{C}$$\dot,00$

Our contributions$k=\mathrm{G}\mathrm{F}l_{\backslash }^{\wedge\backslash }q),$$\mathrm{c}\mathrm{h}(\mathrm{q})\neq 2,3$$k_{2}:\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{d}\mathrm{r}\mathrm{a}^{\mathrm{r}}.\mathrm{i}\mathrm{c}\mathrm{e}\mathrm{x}_{\backslash }\mathrm{t}.\mathrm{O}^{\mathrm{f}}k,$$E:\mathrm{e}||\dot{\{}\mathrm{p}\mathfrak{i}\mathrm{i}\mathrm{c}$curve ove$k_{4}$: quartic$\mathrm{e}\mathrm{x}\mathrm{t}$

. of

$k$

$k_{4}$$E.:\mathrm{v}\underline’=u^{3}-\acute{\tau}\alpha \mathcal{U}\urcorner^{-\beta}\}$$(\alpha,\beta\in k_{4}\grave{)}$垣$\uparrow|$.

$H\cdot.j^{2}=x^{6}+ax^{5}+bx^{4\neq}$ $cx^{3}+h^{2}+ex+f$$\mathrm{f}\mathrm{l}=\supset$

GHS a 廿 aCk$(\mathrm{a}_{f}b,\mathrm{c}_{J}d_{f}\mathrm{e}_{y}f\in\ovalbox{\tt\small REJECT}$. In thiswe show that
elliptic curve cryptosystems over quartic degree finite fie1ds
come under Weil descent attack.
$\mathrm{t}\mathrm{a}\ddagger \mathrm{k},$$\iota \mathfrak{n}\mathrm{a}\mathrm{n}\mathrm{y}$48$\mathit{2}_{*}$

Scholten form

Scholten form

Scholten showed.

.

$\Pi_{\mathrm{k}4|\mathrm{k}2}\mathrm{E}_{\mathrm{n}}\sim \mathrm{S}_{\mathrm{k}2}(\mathrm{H})$$\mathrm{E}/\mathrm{k}_{4}$has full($\exists$

H.. genus 2 HEC)
has Scholten form

$2- \mathrm{t}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\Rightarrow \mathrm{E}$We clarify conditions to be Scholten form.

50

Scholten form is covered by$\mathrm{H}$$E_{n}:\mathrm{v}^{2}’=\alpha u^{3}+\beta u^{2}+\beta^{q2}u+\alpha^{q2}$$(\alpha, \beta\in k_{4})$$\ovalbox{\tt\small REJECT}(.\iota\ell, \mathrm{v})=$垣$((X-\mathrm{c}.)^{2}/(X-\mathrm{c}^{q_{\sim}^{-}}.)^{\underline{7}}/, y/(\dot{.}X-\mathrm{c}^{q\mathit{2}})^{3})(C\in k_{4}- k_{2})$$H\cdot.y^{2}=\alpha$ $(\mathrm{X}- \mathrm{C})^{6}+\beta(\mathrm{x}.- \mathrm{c})^{4}(x- \mathrm{c}^{q\mathit{2}})^{2}+\beta^{q\mathit{2}}(x-\mathrm{c})^{2}(x-\mathrm{c}^{q\mathit{2}})^{4}$$+\alpha^{q^{\underline{7}}}(x-\mathrm{c}^{q^{\underline{2}}}..)^{6}$.. H.. defined overon
DLP on$\cdot$$\mathrm{k}_{2}$$\mathrm{D}\mathrm{L}\mathrm{P}$$\mathrm{E}_{\Omega}/\mathrm{k}_{4}arrow$When$\mathrm{E}_{\mathrm{w}}$:$\mathrm{y}^{2}=\mathrm{f}(\mathrm{x})$$\mathrm{E}_{\mathrm{W}}$$\mathrm{H}/\mathrm{k}_{2}$can be in @choIten form ?.

: Weierstrass form$/\mathrm{k}_{4},$$\mathrm{f}(\mathrm{x}).\cdot$

irreducible$\mathrm{E}_{\mathrm{n}}.\cdot \mathrm{y}^{2}=\mathrm{F}(\mathrm{x}).\cdot$

Schoften$\mathrm{x}arrow \mathrm{A}\mathrm{x}+\mathrm{B}$$\mathrm{y}arrow \mathrm{C}\mathrm{y}$$\delta.\cdot$

aroot of$(\mathrm{A},\mathrm{B},\mathrm{C}\in \mathrm{k}_{4})$$\mathrm{F}(\mathrm{x})=\mathrm{a}\mathrm{x}^{3}+\mathrm{b}\mathrm{x}^{2}+\mathrm{b}^{\mathrm{q}2}\mathrm{x}+\mathrm{a}^{\mathrm{q}2}$$\delta- \mathrm{q}2\in\{\delta, \delta^{\mathrm{q}4}, \delta^{\mathrm{q}8}\}$$\delta^{- \mathrm{q}2}=\delta\Rightarrow\delta^{\mathrm{q}4- 1}=1\Rightarrow\delta\in \mathrm{k}_{4}$$\delta^{- \mathrm{q}2}=\delta^{\mathrm{q}4}\Rightarrow\delta^{\mathrm{q}2}=\delta- 1\Rightarrow\delta\in \mathrm{k}_{4}$..

$\delta^{1+\mathrm{q}6}=1$$/\mathrm{k}_{4}$$\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}/\mathrm{k}_{4}$51
P『U-暇 U-歌 uiU-i\tilde l2$\mathrm{E}_{\mathrm{w}}..\mathrm{y}^{2}=\mathrm{f}(\mathrm{x}).\cdot$$\Leftrightarrow \mathrm{E}_{\mathrm{w}}$Weierstrass$\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}/\mathrm{k}_{4},$$\mathrm{f}(\mathrm{x}).\cdot \mathrm{i}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{i}\mathrm{b}1\mathrm{e}/\mathrm{k}_{4}$is isomorphic to Scholten form$\exists \mathrm{A}(\neq 0)\in \mathrm{k}_{4},$$(*)$$\gamma=\mathrm{A}\delta+\mathrm{B},$$\mathrm{E}_{\mathrm{n}}$over$\mathrm{k}_{4}$$\mathrm{B}\in \mathrm{k}_{4}$($\delta^{1+\mathrm{q}6}=1$$\gamma.\cdot$

a root of$\mathrm{f}(\mathrm{x})$

)

Then,

a

$.\cdot=_{-}\mathrm{A}^{2- \mathrm{q}2}\delta^{1+\mathrm{q}4- \mathrm{q}2},$$\mathrm{b}.\cdot=arrow \mathrm{A}(\delta+\delta^{\mathrm{q}4}+\delta^{\mathrm{q}- 2\backslash }\int$$\mathrm{E}_{\mathrm{w}}arrow \mathrm{E}_{\mathrm{n}}.\cdot \mathrm{y}^{2}=\mathrm{a}\mathrm{x}^{3}+\mathrm{b}\mathrm{x}^{2}+\mathrm{b}^{\mathrm{q}2}\mathrm{x}+\mathrm{a}^{\mathrm{q}2}$($\mathrm{y}arrow \mathrm{a}\mathrm{y},$$\mathrm{x}\underline{.}$a$\mathrm{x}+\mathrm{B}$)–$\mathrm{f}(\mathrm{x}).\cdot \mathrm{i}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{i}\overline{\mathrm{b}}\mathrm{I}\mathrm{e}/\mathrm{k}_{4},$$\gamma.\cdot$

a root of$\mathrm{f}(\mathrm{x})$$\mathrm{d}(\gamma)..=(\gamma^{\mathrm{q}2+\mathrm{q}4}-\gamma^{\mathrm{q}_{\overline{\angle}^{\tau^{t}}}1})+(\gamma^{\mathrm{q}_{0}^{-+\mathrm{q}8}}-\gamma^{\mathrm{q}6+\mathrm{q}4})+$$(\gamma^{\mathrm{q}10\dot{*}1}-\gamma^{\mathrm{q}0+\mathrm{q}8}\acute{\mathrm{I}})$$(\gammarightarrow \mathrm{B})^{1+\mathrm{q}\hat{\mathrm{o}}}\in \mathrm{k}_{2}$$\Leftrightarrow(\gamma- \mathrm{B})^{\mathrm{q}2}(\gamma^{\mathrm{q}6}- \mathrm{B}^{\mathrm{q}6})^{\mathrm{q}^{\wedge}}\angle=(\gamma- \mathrm{B})(\gamma^{\mathrm{q}\hat{\mathrm{o}}_{-}}\mathrm{B}^{\mathrm{q}6})$$\mathrm{g}(\mathrm{B})=0$$\Leftrightarrow\{$$\mathrm{g}^{\mathrm{q}2}(\mathrm{B}^{\mathrm{q}2})=0$

B の連立 1 次方程式

52$\mathrm{E}_{\mathrm{w}}.\cdot \mathrm{y}^{2}=\mathrm{f}(\mathrm{x})$with$\mathrm{f}\mathrm{l}(\mathrm{x}):\mathrm{i}\mathrm{r}^{\mathrm{r}}\mathrm{I}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{i}\mathrm{b}\mathrm{I}\mathrm{e}/\mathrm{k}_{4},$$\gamma.\cdot$

a rool of$\mathrm{f}(\mathrm{x})$$\mathrm{d}(\gamma)=(\gamma^{\mathrm{q}2+\mathrm{q}4}-\gamma^{\mathrm{q}2+1})+(\gamma^{\mathrm{q}6+\mathrm{q}8}-\gamma^{\mathrm{q}6+\mathrm{q}4})+$$(\gamma^{\mathrm{q}10+1}-\gamma^{\mathrm{q}10+\mathrm{q}8})$$\mathrm{d}(\gamma)=0\Leftrightarrow \mathrm{j}(\mathrm{E}_{\mathrm{w}})\in \mathrm{k}_{2}\mathrm{r}$$\mathrm{j}(\mathrm{E}_{\mathrm{w}})\in \mathrm{k}_{2}$$\Leftrightarrow\gamma=\mathrm{A}\alpha+\mathrm{B}(\mathrm{A}, \mathrm{B}\in \mathrm{k}_{4}, \alpha\in \mathrm{k}_{6})$$\Leftrightarrow \mathrm{d}(\gamma- \mathrm{B})=0$$\Leftrightarrow \mathrm{d}(\gamma)=0$

When$\mathrm{E}_{\mathrm{w}}.\cdot \mathrm{y}^{2}=\mathrm{f}(\mathrm{x}).\cdot$.

$\mathrm{f}(\mathrm{x}).\cdot$$\mathrm{E}_{\mathrm{W}}$can be In Scholten form

Weierstrass

既約$\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}/\mathrm{k}_{4}$$/\mathrm{k}_{4}$$\mathrm{j}(\mathrm{E}_{\mathrm{w}})\in \mathrm{k}_{4}-\mathrm{k}_{2}$ならば、Ew は Scholten form[こ k4 上で変換される。
既約 2 次式
Ew は Scholten form で表されない。

$\sigma \mathrm{f}(\mathrm{x})=1$.

次式$\mathrm{x}$$/\mathrm{k}_{4}$: 完全分解Ew は常に Scholten form に k4 上で変換される。

$\mathrm{f}(\mathrm{x})$$/\mathrm{k}_{4}$

53

3.

attack forgenus 2$\mathrm{G}\mathrm{H}\mathrm{S}$$\mathrm{H}\mathrm{E}\mathrm{C}$GHS attack in our case
島=Fq2|$k=\mathrm{F}_{\mathrm{q}}$(of char.

$\neq 2\grave{)}j\sigma:$

Frob. Automorphisnl Of$k_{\mathit{2}}/k$$H:y^{\mathit{2}}=x^{\mathit{6}}+ax^{\mathit{5}}+bx^{\ell\acute{\prime}}+cx^{\mathit{3}}+\overline{d}x^{\prime \mathit{2}}.+ex+f(\dot{\mathrm{a}}_{f}b_{j}\mathrm{c}_{f}d_{l}.e,f\in\overline{k}l$a$x_{l}^{\mathit{5}}+bx_{l}^{\mathit{4}}+cx_{l^{\mathit{3}\neq}}\cdot dx_{l}^{\mathit{2}}+ex_{I}+f$$\mathrm{a}^{q}x_{\mathit{2}}^{\mathit{5}}+b^{q}x_{\mathit{2}}^{\mathit{4}}+\mathrm{c}^{q}x_{\mathit{2}}^{\mathit{3}[perp]},$$\cup$$x:=$ 目$d^{q}x_{\mathit{2}}^{\mathit{2}}+\mathrm{e}^{q}x_{\mathit{2}}+f^{q}$$=.\cdot \mathrm{r}_{2}\underline,$-section $D$ :$\mathrm{G}\mathrm{H}\mathrm{S}$$\{\begin{array}{l}y_{l}*’=x^{\dot{\mathit{6}}}+ax^{\mathit{5}}+bx^{\mathit{4}}\lrcorner_{-}.cx^{\mathit{3}}+dx^{\mathit{2}}+ex+fy_{\mathit{2}^{\mathit{2}}}^{\backslash }=x^{\mathit{6}}+a^{q}x^{\mathit{5}}+b^{q}x^{\mathit{4}}+cqx’+\mathit{3}d^{q}x^{\mathit{2}}+e^{q[perp]}x\ddagger f^{q}\end{array}$

54

Assumption for non-singuIarity
H.

$\cdot$$y^{\mathit{2}}=x^{\mathit{6}}+ax^{\mathit{5}}+bx^{\prime \mathit{4}}+cx^{-\partial}.+dx^{\mathit{2}}+ex$.

$+f$ on$k_{\acute{\mathit{2}}}=F_{q}^{\underline{p}}./^{\prime_{k=F_{q}}}$no non-frivial factor defined over .
$k^{T}$

then

$1|$

$\mathrm{G}\mathrm{H}\mathrm{S}rightarrow \mathrm{s}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}D$

Genus ofis non-singular as affine curve.

$\mathrm{G}\mathrm{H}\mathrm{S}$-section$D$-section D.

$\cdot$$\mathrm{G}\mathrm{H}\mathrm{S}$$\{\begin{array}{l}y_{l^{\sim=\chi^{\mathit{6}}+aX^{\mathit{5}\prime \mathrm{z}}}}^{2}\sim c-\ulcorner ox^{\mathit{4}}+^{\mathit{3}\prime}.x\urcorner^{-dx^{\mathit{2}}+c^{j}x+f}\prime Av_{\gamma}^{\mathit{2}}=x^{\mathit{6}}+a^{q}x^{\mathit{5}}+\dot{o}^{q}x^{\mathit{4}}+c^{q}x^{\mathit{3}}\dotplus d^{q^{\prime y}}x^{\sim}+e^{q}x\end{array}$$*|12$ ra-mification p\^uintsH.
$\cdot$Hurwitz$y^{\mathit{2}}=x^{\overline{\mathit{6}}|}-\ulcorner$$\mathrm{a}$$x^{\underline{\sigma}}+bx^{\oint}$\urcorner -$cx^{\mathit{3}}+d_{X^{\underline{J}}}\sim+\overline{\mathrm{g}}^{\prime l}x\urcorner^{-f}$$\acute{\mathrm{r}}\mathrm{o}\mathrm{r}\mathfrak{m}\mathrm{u}\mathrm{l}\mathrm{a}$’$2\mathrm{g}(\mathrm{D})- 2=[K(D).\cdot K(H)]\cdot\acute{(}2\mathrm{g}(\mathrm{H})- 2)+\Sigma(\mathrm{e}(\mathrm{P}’|\mathrm{P})- 1)\cdot\deg \mathrm{P}$$.\cdot*\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{u}\mathrm{s}$of GHS-section$\mathrm{D}=9;\mathrm{S}111411$

What we rteed to do is to construct-section $D$ .

$\mathrm{G}\mathrm{H}\mathrm{S}$$\mathrm{C}_{\mathrm{a}\mathrm{b}}$$\subset\Rightarrow$model over$k$Problemof$\subset>\mathrm{p}_{\ulcorner}\mathrm{o}\mathrm{b}1\mathrm{e}\mathfrak{m}2$$\mathrm{t}$55

Points at垣$\mathrm{k}2|\mathrm{k}\mathrm{I}\mathrm{I}\supset D$:$\inf^{\mathrm{I}}\iota \mathrm{n}\mathrm{i}\mathrm{t}\mathrm{y}$,;$P_{\mathit{3}}P_{\mathit{4}}\backslash /$$H$$t=x^{\gamma}\underline{.}/\acute{y}_{1}$$\mathrm{G}\mathrm{H}\mathrm{S}\approx \mathrm{s}\mathrm{e}\mathrm{c}\mathrm{t}^{\mathrm{z}}\mathrm{I}\mathrm{o}\mathrm{n}D$$\mathrm{G}\mathrm{H}\mathrm{S}-\sec\iota_{1\mathrm{O}\cap}^{*}$$x=x_{1}=x_{\angle}$$2\downarrow D$of$Q_{2}$$\mathrm{v}_{\mathrm{Q}\mathrm{i}}(x)=_{-}1,$: two points at infinity

嫁 ocal parameter at$Q_{\mathrm{A}}|$and)$x=\tau^{-1}+\alpha_{0^{(\mathrm{i})}}.+\alpha_{2}^{(\mathrm{i}_{\grave{J}}}t+\ldots$.

$y_{1}=t^{-3}+\beta_{-2}^{(\mathrm{i})}t^{\sim 2}\dotplus\beta_{-1}^{(\grave{1})}t^{-\mathrm{i}}\dotplus\ldots$

$x$

for

$y_{2}^{\prime=}-$or$\mathrm{k}2|\mathrm{k}’\supset D$:

at$Q_{\mathrm{i}}(\mathrm{i}=1,2)$$v_{\sim}^{\mathit{2}},=x^{\mathit{6}}+a^{q}x^{\mathit{5}}+b^{q}x^{\phi}$... atat$t^{-3}+\gamma_{-2^{(2\mathrm{i}- 1)}}.t^{-2[perp]_{1}}$$y_{2}=t^{-3}-\urcorner^{-}\mathrm{I}\gamma_{-2^{(2\mathrm{i})}}t^{-2}+...$

Points at垣.

second equation ,of GHS-section $D$ ,$\mathrm{i}\mathrm{h}\mathrm{e}$$+c^{q}x^{\mathit{3}}+d^{q}x^{\mathit{2}}+e^{q}x+f^{q}$$\mathrm{o}\mathrm{f}H$$Q,\sim$$\{$Substituting the above$\mathrm{v}_{\mathrm{Q}\mathrm{i}}(y)=_{-}3$$\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{n}^{1}\mathrm{t}y$of$\mathrm{P}_{2\mathrm{i}-1}(\mathrm{i}=1,2)$$\mathrm{P}_{2\mathrm{i}}(\mathrm{i}=1,2)$$\mathrm{G}\mathrm{H}\mathrm{S}$-section$x=x_{1}=x_{2}t=x^{\prime 2}\acute,y$$x=-t^{-1}[perp]_{1}\alpha_{0}^{l_{\backslash }1)+}\alpha_{1}\mathrm{t}\ddagger.\cdot {}^{\mathrm{t}}t[perp]_{\mathrm{I}}\simeq\cdot$.

$y_{1}=t^{-3}$ \dagger $\beta- 2t^{-2+}(1)\beta.1t^{-}(1)1+\cdots$$P_{1}$$\prime v_{2}=-t\sim-\lrcorner+\gamma_{rightarrow 4}^{\dot{[}1\dot{\}}}nt^{-\acute{l}}+r_{1}^{\mathrm{i}\acute{1})}’+r- 1$

A$X=-t.1\iota_{-}\urcorner\alpha_{0}^{(1\}}.+\alpha\backslash \iota^{\Gamma 1)|}t^{-\ulcorner}$$J’ 1\urcorner=t^{-3}+\beta_{\mathrm{z}^{(1)}},t^{\prime 2}$.

$\not\in*$.

$\cdot 1+\cdots$. $\cdot.3+Y_{-2}^{\{.2)\cdot 2}.t+\gamma_{-1}^{\dot{(}2)} t$$\prime v_{\dot{L}}.=\oint$.

$*$\dagger $\mathcal{B}_{1},(1\rangle*’\cdot 1\neq\ldots$$P_{2}$$x$..

$=t.1+\alpha_{0^{(\underline{?})}}+\alpha_{1}^{(\}}\underline’ t+*=$.

$\mathcal{Y}\iota=t^{-3}+\beta_{-2^{\{2)}}t^{-2}+\mathcal{B}_{-1^{(2\}\cdot 1}}\cdot\cdot t+\cdots$$lo_{3}$$y_{2}=- t^{-3}.+\gamma_{2}^{\langle 3\}}’-t^{2}’+\gamma_{-1}^{(3)}t^{-1}+\cdots$$\Gamma x=t^{-1}+\alpha_{0^{\langle_{\wedge}^{\prime y})}}+\alpha_{\iota^{(2\}}}r+\cdot\cdot*$$\prime v_{1}=t^{-3}+\beta.2^{\zeta 2)- 2[perp]_{\mathrm{I}}\beta.t+}t12)\cdot 1\cdots$$P_{4}$$\{$$\mathrm{J}_{\overline{A}}^{J}=t^{-3}+\gamma_{-2}^{(4)}t^{-2}+\gamma.\lrcorner.)t^{-1}(4+1\ldots$$.\mathrm{v}\mathrm{a}|\mathrm{u}\mathrm{e}’$of any polynomiaI$f(x\mathrm{i}\}_{\mathfrak{j}2}^{J}\gamma_{\tau})L\mathrm{a}\mathrm{t}_{\wedge j\prime}^{p}\sigma(P_{4})=P_{4}$

58

.a

$\mathrm{C}_{\mathrm{a}\mathrm{b}}$modef ofWe constructbase point.

Suppose$P_{4}$

is$\mathrm{C}_{\mathrm{a}\mathrm{b}}$$\ulcorner,\mathrm{o}\mathrm{t}$$\mathrm{G}\mathrm{H}\mathrm{S}$-sectionmodel of $D$ wifh the pointat$P_{4}$$D$as$\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{i}\mathrm{n}\dot{|}\mathrm{f}\mathrm{y}$a Weierstrass point:

PoIe$\mathrm{n}\mathrm{u}\mathrm{n}\tau \mathrm{b}\mathrm{e}\mathrm{r}_{\mathrm{b}}^{\neg}$at$P_{4}=\backslash 1\prime 0,11,\ldots,19\sim/$.

$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}’.\mathrm{u}\mathrm{c}\mathrm{t}$with a unique pole of order at$19$ .
for $i=10,11,$a polynomial$\mathrm{i}$$f_{\tilde{l}}$$P_{4}$$\ldots,$$\acute{\mathrm{f}‘\underline{\mathrm{N}}}\mathrm{o}\mathrm{t}\mathrm{e}.\cdot\overline{\underline{t- \mathrm{e}}\mathrm{x}}\underline{\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{s}}\underline{\mathrm{i}\mathrm{o}}\underline{\mathrm{n}}\underline{o}\mathrm{f}\overline{\underline{P_{i}\mathrm{g}}\underline{\mathrm{i}}}\underline{\mathrm{v}\mathrm{e}\mathrm{s}}\underline{\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{v}}\overline{\underline{\mathrm{a}}1\mathrm{u}}\mathrm{e}\underline{\mathrm{a}\mathrm{t}}P_{\underline{i}}!\sim\sim---\cdot-\cdot\wedge\sim\sim-\sim’--\sim\sim-|---------------\wedge--------\sim-\neg$$f_{\lambda 0^{\backslash }\mathrm{t}}1,f_{11}$, $\ldots’.f_{19}-$&:=Tr 観 Ik(fi)$\mathrm{C}_{\tau,\mathrm{A}0,11,\ldots,19}$

modei over , of $D$$k_{\mathrm{A}}$$(\mathrm{T}_{\mathrm{A}}^{r_{\mathrm{k}2|\mathrm{k}}}\zeta f)=f+\sigma(O)$$g_{10},g_{11},\ldots,g_{19}-$$\mathrm{C}_{10,11_{:\cdots\backslash }19}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{e}_{1}^{\mathrm{I}}C$

over of$k$$D$$\mathfrak{l}^{---------}$’$\underline{||\mathrm{I}\mathrm{N}\mathrm{o}\mathrm{t}\mathrm{e}.\cdot}P_{\underline{4}}\underline{\mathrm{i}\mathrm{s}}\underline{\mathrm{f}\mathrm{I}}\underline{\mathrm{x}\mathrm{e}}\underline{\mathrm{d}}.\mathrm{b}\underline{\mathrm{y}\sigma}_{-\lrcorner}^{1}.’-----\dot{|}$.

$\mathrm{R}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{f}\mathrm{i}\mathrm{o}\mathrm{n}*$$\mathrm{H}arrow \mathrm{C}$$\mathrm{D}\underline{-\sigma=\acute{(}\mathrm{g}_{10},\mathrm{g}_{11},’\ldots,\mathrm{g}_{1^{\mathrm{Q}}}\grave{J}}\mathrm{C}\ovalbox{\tt\small REJECT}$$\pi 1$$\mathrm{H}$$\mathrm{g}^{*}$$\pi-\underline{1}(\mathrm{S}_{1})+\pi^{- 1}(\mathrm{S}_{2})-(\mathrm{P}_{1}+\mathrm{P}_{2}+\mathrm{P}_{3}+\mathrm{P}_{4}^{\cdot})\sim\Sigma \mathrm{R}_{\mathrm{i}}-\mathrm{n}\mathrm{P}_{4}arrow$$\pi_{h=\mathrm{S}_{1}+\mathrm{S}_{2}-(\mathrm{Q}_{1}+\mathrm{Q}_{2}\grave{\mathrm{J}}}^{*\mathfrak{s}},\in \mathrm{J}_{\mathrm{k}2}(’\mathrm{H}\grave{)}/^{/^{p_{\Pi_{1}^{*}}^{\nearrow}}}$$\mathrm{Z}\mathrm{g}(\mathrm{R}_{\mathrm{i}})-\mathrm{n}\infty$

$\mathrm{f}\mathrm{f}7$

仮 Wit 加 #. 何 ea!@$\mathrm{R}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{t}_{\dot{5}\emptyset \mathrm{f}\mathrm{f}\mathrm{i}}.\cdot \mathrm{g}\mathrm{r}$$\mathrm{k}_{2}(\mathrm{D})=\mathrm{k}_{2}(x,y_{l},y_{\mathit{2}})\underline{\mathrm{g}..*\cdot}$$\mathrm{k}_{2}(g_{l\theta},g_{ll:}\ldots,g_{\mathit{1}\mathit{9}})$1$\pi^{*}$$\mathrm{k}_{2}(\mathrm{H})=\mathrm{k}_{\gamma,\sim}(x,y_{\mathit{1}},)$$w:=h\cdot \mathrm{g}$–$\mathrm{o}\mathrm{f}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{I}\mathrm{a}l\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{a}\mathrm{n}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{a}1v\subset \mathrm{k}_{2}[\mathrm{g}_{10},\mathrm{g}_{11},\ldots,\mathrm{g}_{19}]$$\mathrm{C}\mathrm{k}_{2}[x_{\mathrm{J}}y_{\mathit{1}^{P}}y_{\mathit{2}}]$$\mathrm{g}_{10}(\mathrm{x},\mathrm{y}_{1},\mathrm{y}_{2})_{\epsilon 11},\sigma(\mathrm{x},\mathrm{y}_{1},\mathrm{y}_{2}),\ldots$’$\mathrm{g}_{19}(\mathrm{x},\mathrm{y}_{1},\mathrm{y}_{2})\mathrm{m}\mathrm{o}\mathrm{d} w$$(\mathrm{v}_{\mathrm{P}\mathrm{i}}(\mathrm{g}^{r})\geqq 1\mathrm{i}=1,2,3)$$\exists$

an ideal$\mathrm{i}_{\mathrm{V}}‘=\mathrm{g}^{*}1_{----\cdot--}|..(\mathrm{w})=\ulcorner 1*(\mathrm{h}.)\mathrm{L}..\mathrm{I}$.

$h$$\mathrm{C}\mathrm{k}_{\underline{\gamma}}[x.,y_{\mathit{1}}]$$\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{e}\mathrm{d}\alpha c\mathrm{f}\dot{5}\mathfrak{Q}T8\cdot.\mathrm{g}\infty$$C:\mathrm{C}_{\mathrm{a}\mathrm{b}}$model over of$k$仮$\mathrm{G}\mathrm{H}\mathrm{S}\sim \mathrm{s}^{a}.\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}D$

甲:$\Psi$

reduces DLP on$E/f\sigma_{4}$to DLP on $C/k$.

.

,

58

Exa 暇 lle41: Tr I-I\approx -価 『 tf.\breve ^l-l
paIindrome form.

$k\cdot$field of char. $q=p=71$. byquadraticofby: quartic$\mathrm{p}\mathrm{r}\dot{|}\mathrm{m}\mathrm{e}$$k_{2}:$$k_{4}$.

$l\wedge 1$$0^{2}- 20^{[perp]_{\mathrm{I}}}7$$\mathrm{e}\mathrm{x}\mathrm{t}$$\mathrm{e}\mathrm{x}_{1}‘.$$k$$\mathrm{r}^{2_{-}}\mathrm{o}\mathrm{r}+1$$E_{\iota}\sqrt{}’k_{\acute{4}}:v_{1}^{2}+70u_{1}^{3[perp]_{1}}(0^{2_{-}}.\mathrm{r}[perp]‘ 0^{4231})\mathrm{n}58u_{l}+0^{3375}\mathrm{r}+0^{2069}=0$$b=0^{3519}\mathrm{r}+\mathrm{o}^{2654}a=0^{2258}\mathrm{r}+0^{214}$2$\mathrm{f}|\Pi_{\underline{\mathrm{o}}^{t}}^{l}\mathrm{l}$)$\mathrm{r}\iota’\simeq_{\mathcal{L}\acute{l}\mathrm{t}’}^{-arrow 1}ll=‘\- 1\mathrm{t}\iota_{\mathrm{I}}t_{1^{\neq \mathcal{B}_{\underline{\gamma}}\mathit{1}}}\backslash \cdot$$:\xi$$\beta_{2}=0^{4167}\mathrm{r}+0^{3302}$

1$E_{\mathrm{n}}/k_{4}:v^{2}=au^{3}+bu^{2}+b^{\mathrm{q}^{\underline{0}}}u+a^{\mathrm{q}2}$$=(\mathrm{o}^{2258}\mathrm{r}+0^{214})u^{3}+(\mathrm{o}^{3519}\mathrm{r}+0^{2654}\grave{)}u^{2}+$$(\mathrm{o}^{ggg}\mathrm{r}+0^{3103}\dot{)}u+0^{4\overline{/}78}\underline{\mathrm{r}}+0^{35\hat{3}}$ExampIel : Covering by
hypereIIiptic curve$E_{\mathrm{I}\mathrm{z}^{\prime K}4}^{\prime J}:v^{2}=au^{3}+bu^{2}+b^{\mathrm{q}2}u+a^{\mathrm{q}2}$$=(_{\hat{\mathrm{u}}^{22_{\backslash }58}}\mathrm{r}+0^{214})u^{3}+(\mathrm{o}^{3519}\mathrm{r}+0^{2\mathit{6}_{\backslash }54}\ddot{)}u^{2}+(\mathrm{o}^{999}\mathrm{r}+0^{370_{\backslash }3}.)u+\mathrm{o}^{4778}\mathrm{r}+0^{3_{\backslash }\overline{\backslash }5}$垣,.、$(2_{:}^{\mathrm{s}},\{\begin{array}{l}\mathrm{t}t---(\lambda_{0}.-\mathrm{t}^{\mathrm{r}}.\cdot J.\acute{\prime}.\langle_{\vee}\mathrm{r}_{\mathit{0}^{-}}\mathrm{c}^{\mathrm{q}^{\underline{?}}}.,l^{\underline{\tau}}\backslash \mathrm{t}^{*=}\prec y_{\mathrm{f}\ddagger}/,\{_{\backslash }\lambda_{\mathrm{U}}.-\cdot\cdot\cdot\acute{\iota}^{\iota]_{\wedge}^{\tau\neg}}’\dot{)}l-^{\mathrm{Y}}\end{array}$$\uparrow|^{1}$$H_{0’}^{/}\not\in:y_{0}^{2}=a_{1}^{f}x_{0^{-}}c)^{6}+b(x_{0}arrow c)^{4}(x_{0^{-}}c^{\mathrm{q}2})^{2}+b^{02}.(x_{0^{-\vee}}^{\mathrm{r}})^{2}(\check{x}_{0}-c^{\mathrm{q}2})^{4[perp]_{1}}a^{\mathrm{q}2}(x_{0^{-}}c^{\mathrm{q}2})^{6}$$=0^{14\mathit{6}3_{X_{\mathrm{Q}}}6}-\mathrm{I}$「$0^{6\mathit{6}6}\sim x_{0’}^{5}+0^{2070_{X_{0}}.4}-^{1}$「$\mathit{2}|4$研$k_{\overline{\angle}}.$:賞$0^{1093_{X_{0}}3}+\mathrm{o}x_{I_{\sim}\mathrm{I}}+794\sim 20^{3\underline{1}5}\vee x_{0_{-}}’+0^{193^{\mathrm{Q}}}$$\prime \mathrm{r}_{\vee}\sim,\cdot..$$- \mathrm{d}\urcorner \mathrm{t}_{\sim}^{\mathrm{i}\}}$;)$arrow\{^{i/j},\underline{.)}$$\mathrm{t}.\mathrm{x}^{\tau}=1^{l}1_{1}^{;=\mathrm{F}^{\neg}(/\mathit{3}.\cdot \mathit{3}}’(_{J}\mathrm{t}_{0}- B\grave{l}(f_{\{\mathrm{J}}^{-}-f^{\simeq})^{-\dot{\mathrm{J}}^{\mathrm{Y}}}.1_{l\lrcorner}.’$$H_{0}.\cdot y_{0^{2}}=F(\mathrm{x})c=\mathrm{r}\beta=3$$y_{1}^{2}=x^{6}+\mathrm{o}^{21\overline{/}\overline{/}}x^{5}+\mathrm{o}^{4311}x^{4}+\mathrm{o}^{2447}x^{3}+\mathrm{o}^{566}x^{2}.+\mathrm{o}^{3\acute{\mathrm{o}}64}x+0^{3747}$

喜, $:=$ 垣 ’$\acute{\iota}^{1)}$垣 $22^{(3)}(2)\ulcorner_{1:H}-E_{\mathrm{w}}$59$\mathrm{E}\mathrm{x}\mathrm{a}\mathrm{I}\eta_{1}$暇$1_{\mathrm{r}}^{\mathrm{A}}1\cdot \mathrm{P}-.ir_{1}\mathrm{t}^{\underline{\mathrm{g}}}\tilde{a}\mathrm{t}\#.\mathrm{f}\mathrm{l}\mathrm{f}\mathrm{i}\overline{\iota\iota}\mathrm{i}_{\mathrm{t}}^{1}y-.\mathrm{f}$$\mathrm{G}\mathrm{H}\mathrm{S}$-section$D$$\Pi_{\mathrm{k}2|}{}_{\mathrm{k}}H\supset D:\mathrm{x}=x_{1}=x_{2}t=x^{2}/,v$$P_{1}\mathrm{I}_{\mathfrak{s}^{y_{1}=t^{-}\frac{\mathrm{q}}{}1\mathrm{o}^{2177}t^{-2_{1}}\mathrm{o}^{411}\frac{\mathrm{I}}{}t^{-1\iota}0^{\underline{3}867}\downarrow 0^{3086}t\}\cdot*}}^{x=70t^{1}+0^{4_{\ }^{\mathrm{q}}65}+\mathrm{o}^{261}t+\mathrm{o}_{\mathrm{I}}i^{A}+\mathrm{o}^{2836}t^{3}+}\mathrm{L}^{y_{2}=70t^{-3}+\mathrm{o}^{2713}t^{-2}+\mathrm{o}^{4163}t^{-1}+0^{3058}+\mathrm{o}^{4_{\mathrm{A}}’99}t+}.11453s\circ,\cdot..\cdot.$.

$x=70r^{-1}+0^{426^{\epsilon\neg}}\lrcorner\dotplus \mathrm{o}^{\angle 61}t+0^{453^{\epsilon}}\lrcorner t^{2}+0^{2836}t^{3}+\cdots$$y_{1}=t^{-3}+0^{2177\cdot\underline{9}}\wedge t+\mathrm{o}^{4111}t^{-1}\tau^{\mathrm{J}}0^{3867}+0^{3086}t+**\mathrm{r}$$P_{2}$.

$y_{2}=t^{-3}+0^{193}t^{-2}+0^{1643}t^{rightarrow 1\neq}$ $0^{538}+0^{1779}t+\cdots$’$P_{3}$$X=r-$ }$+0+42_{\acute{0}\acute{.2}}\mathrm{o}^{2_{J81}^{\neg}}\mathrm{A}t+\mathrm{o}^{453\mathit{5}2}t\dotplus \mathrm{o}^{31_{\acute{0}}\mathrm{i}}t+\cdots$\dagger$y_{1}=t^{\prime 3}\dagger\overline{.}4697t^{-\underline{)}}+0^{4\iota\iota\iota}\prime t^{-!}.+\mathrm{O}^{1347|}-\urcorner^{-}\mathrm{O}^{3086}t$$\cdot\epsilon$$y_{2}=70t-3+\mathrm{o}^{193- 2}t+0^{4163}t^{-1}+0^{538}+0^{4299}t+$$\cdot$.
..

$x=t.1+0^{4265}+\mathrm{o}^{2781}t$ 十 $\mathrm{o}^{\mathrm{a}535}t^{2}+\mathrm{o}^{316}t^{3}+4\ldots$$P_{4}$$y_{2}=t^{-3}y_{1}=t^{-3469^{7},-741\mathrm{I}1-1}\ddagger_{\mathrm{o}^{2713}t^{\sim 2}+\mathrm{o}^{1643}t^{-1}+\mathit{0}^{3058}+\mathrm{o}^{1779}t+}^{\dot{o}t^{\sim}+\dot{\mathrm{o}}t^{\mathrm{A}}+0^{1347}+\mathrm{o}^{3\{\mathrm{J}86}t\dotplus}’.\cdot.\cdot.\cdot$.value” of any polynomiaI$f\cdot(x,y_{1},y_{2})$at$P_{\mathrm{i}}$modeI of GHSExamplel :section$\mathrm{C}_{\mathrm{a}\mathrm{b}}$$D$a polynomial wifh a unique pole of order at$i$$P_{4}$:$g_{i}=\mathrm{T}\mathrm{r}_{\mathrm{k}2|\mathrm{k}}(f_{i},)$$\delta 1\mathrm{i}\mathrm{o}10\sigma=\sigma=0^{1386}.x^{3}y_{1^{2}}^{r}+x^{3}y_{1}y_{2}+0^{2108}.x^{3}y_{1}+\cdot+\mathrm{o}^{630}y_{\underline{\prime}}^{\mathrm{z}_{\Gamma}}\mathrm{o}^{1264_{\gamma}\cdot 3}\vee\vee y_{\mathrm{i}}^{\underline{7}}+3x_{-}^{3}\}^{r_{1}}y_{2}+0\frac{0}{}713x_{1}y_{1}+.\cdot.\cdot\cdot+\mathrm{o}^{1\overline{/}54}\mathrm{J}_{2}’$$\xi$$\mathrm{t}$$g_{19}=_{\mathrm{O}^{3534}\tilde{\iota}^{3},y_{1}^{2}+41x^{3}y_{1}y_{2}+0^{3210_{x_{3}y_{1}}[perp]_{\iota}}}$Relations amcng$g_{10},g_{11},$...

.

$[perp]_{\mathrm{I}\mathrm{o}^{1622}y_{2}}$$\cdots,g_{19}.\cdot$.
$\ovalbox{\tt\small REJECT}$$g_{11}g_{12}-(26g_{10}g_{13^{\urcorner}}g_{1}aeg_{\mathrm{l}1}^{2}-(5g_{1}g12+42g_{\mathrm{t}\mathrm{t}}g_{11}+18g10^{2*\cdot.+.25)=0}g_{12}g_{19}- \mathrm{t}9g_{16^{2}}1g_{11}+62g_{10^{3}}+10g_{\tau}[perp] ae19-+\cdot++2\mathrm{S})=0\iota_{-3812*+58).=0}+\cdot$$\mathfrak{s}_{\mapsto}$$\mathrm{C}_{10,11,..r19}$,

curve over

$k$

in

$g_{10}-- g_{11}-\ldots--g_{19}$space$\epsilon \mathrm{o}$EX 下家暇 I 伽 1

R 伽何鯛 Cfi 屋 a$\{^{A}\mathrm{B}\}$$E_{\mathrm{w}}\ni G=(\mathrm{o}^{387}\mathrm{r}+0^{397}, \mathrm{o}^{166}\mathrm{r}+0^{1205})$

From the definition of$\prod_{2}$$J_{1}=\urcorner_{2}^{*}1(G)$$=\{a((\betarightarrow c)x+1)^{2}-(G_{\mathrm{x}}+\beta\underline,)((\beta-c^{\mathrm{q}2})x+1)^{2}$$a\alpha 1/2y_{1}- G_{\mathrm{y}}((\beta- c^{\mathrm{q}2})x+1)^{3}\}$$=\{(\mathrm{o}^{353}\mathrm{r}+0^{4196})x^{2}+(\mathrm{o}^{1900}\mathrm{r}+0^{1805})x+\mathrm{o}^{1922}\mathrm{r}+0^{2318},$$(\mathrm{o}^{3720}\mathrm{r}+0^{1533})x^{3}+$$l_{\backslash }\mathrm{o}^{1693}\mathrm{r}+0^{4323}.)x^{2}+(.\mathrm{o}^{3636}\mathrm{r}+0^{1592})y_{1}+(.\mathrm{o}^{125\dot{b}}\mathrm{r}+0^{3701})x+\mathrm{o}^{268\dot{6}}\mathrm{r}+0^{3725}\}$

To computeuse elimination ideal.

$\cdot$$\Pi_{1(J),\mathrm{w}\mathrm{e}}^{*}$$.J_{2}arrow \mathrm{E}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{e}(.J_{1}+(g_{10^{-}}g_{10}(x,y_{1},y_{2}),g_{11^{-}}g_{11}(x,y_{1},y_{2}),\ldots$$g_{19^{-}}g_{19}(x,y_{1},y_{\underline{7}}),$,$\{x,y_{1},y_{2}\})$$g_{18}+\underline{7}4\sigma+27+31+64\sigma+\cdot \mathrm{z}\cdot+64\}\mathrm{c}517g_{16}g_{15\epsilon 14}$

SimilarIy, $m=25415194$ -times pointis$\mathrm{t}\mathrm{r}\mathrm{a}\cap \mathrm{s}\mathrm{f}\mathrm{e}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{d}$$G_{\mathrm{m}}=(\mathrm{o}^{637}\mathrm{r}+0^{224}, \mathrm{o}^{1671}\mathrm{r}+0^{3481})$to$’\tilde{J_{\iota \mathrm{n}}}=\{g_{17^{2}}+6g_{17}+70g_{16}+66g_{15}+15g_{14}+\cdots+68$,$g_{1}g_{17}+5g_{17}+20g_{16}+56g_{15}+16g_{14}+\cdot**+11$$g_{18}\neq_{l}23g_{17}+34g_{16}+65g_{15}+18g_{14}+\cdots+4\}$

We verified$J_{\mathrm{m}}=m\cdot J$

on .
$C$

fl Gaudry method,of$\mathrm{G}$,$1$\mathrm{E}\kappa \mathrm{a}\mathrm{m}\mathrm{p}\overline{:}\mathrm{e}\mathit{2}$$k$: prime field of char.

($\mathrm{S}60\mathrm{b}\dot{\mathrm{i}}_{1}^{l}@$lengt 加)$p=2^{40}- 2^{35_{\mathrm{r}}}1$:quadratic ext of by $0^{2}+352619714346$: quartic ext of by $\mathrm{r}^{2}+7027532045730+465976829831$$k$$h_{-}$$k$$\mathit{1}\mathrm{c}_{4}$$E_{\mathrm{w}}$:elliptic curve over$k_{\mathit{4}}$$v_{1^{2}}=u_{1^{3}}+((7735699290470+698785454132)\mathrm{r}+8924687926970\dotplus 773390597884)u_{1}+$$(2450226574830+657619174138)\mathrm{r}+7211879400680+865450731541$
bits prime)$\mathrm{t}\# E(k_{4})=128720040665092860_{\mathfrak{Q}}9777376029597716043015507861907:160$$C:\mathrm{C}_{10,11,\ldots\backslash 19}$

curve over$g_{11^{2}}rightarrow(671010913434g_{10}g_{12}+306446345201g_{10}\mathrm{g}_{11}+$205461673669$g\iota 0^{2*\mathrm{r}}+\cdot+675147796101$) $=0$$k\ovalbox{\tt\small
REJECT}$$g_{11}g_{12^{-}}(752537421825g_{10}g_{13}+.1016531429604g_{\mathit{1}0}g_{12}+897328181722 \mathrm{g}_{10}g_{11}+\cdot\cdot+1053682994222)=0\prod \mathrm{G}\mathrm{a}\mathrm{u}\mathrm{d}\mathrm{r}\mathrm{y}$method$g_{12}g_{1)}‘-(128634052382g_{10^{2}}g_{\mathfrak{l}1}+950367786029g_{10^{3}}+$$( 457707828730 g_{1\mathrm{J}},g_{19}+\cdot\cdot*+665817232135)=0$.

–$\mathrm{E}@\mathrm{t}\dot{\mathrm{f}}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{e}$of$\mathrm{c}\oplus \mathrm{f}\mathrm{f}\mathrm{l}\mathrm{p}\ovalbox{\tt\small REJECT} \mathrm{f}\mathrm{a}\not\in_{i6\mathrm{f}\mathrm{l}\mathrm{a}5}^{*}$

a 家 ov$\prod \mathrm{f}\mathrm{s}$.Computational amounts of Gaudry method againstiscurve of genus $g$ over$\mathrm{G}\mathrm{F}(q)$$\mathrm{C}_{\mathrm{a}\mathrm{b}}$$\mathrm{O}(q^{2\mathrm{g}/(\mathrm{g}+\mathrm{I})+\epsilon}.)(qarrow\infty)$$.\mathrm{S}\mathrm{o}$, computational amounts of our WeiI descent attack(g–9):$q^{18/10}=q^{9/5}(<\mathrm{q}^{2})$$(qarrow\infty)$$\mathrm{i}$amounts of PofIard’s:
elIiptic curves on$\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{P}\mathrm{u}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathfrak{l}$$\mathrm{G}\mathrm{F}(q^{4})$$\mathrm{r}\mathrm{h}\mathrm{o}$method against

$\mathrm{B}2$

荻 o『 e$\mathrm{p}\mathrm{r}\mathrm{e}\epsilon\S \mathrm{s}\mathrm{e}\mathrm{e}\mathrm{s}\mathrm{t}*\dot{\mathfrak{x}}\mathrm{m}\mathrm{a}\mathrm{f}\mathrm{e}$.Computational amounts of Gaudry method against
genus $g$ defined on:(: parameter)$\mathrm{C}_{\mathrm{a}\mathrm{b}}$curves of$\mathit{1}\geqq]$$\mathrm{G}\mathrm{F}(q)$Minimum w.r.t. of$l$.

$\mathit{1}^{\mathrm{g}\sim 1}*g^{3}\cdot g!\sim q\cdot(.\log_{2}(.q^{\wedge}.))^{3}$$+l^{- 2}\cdot g^{3}$.ComputafionaI amounts of

eIIiPtiC curves on$\mathrm{G}\mathrm{F}(q^{4})$15.

$\mathrm{P}\mathrm{o}11\mathrm{a}\mathrm{r}\mathrm{d}’\mathrm{s}$:$q^{2}\cdot(\log_{2}(q))^{2}$

rho method against$q^{2}\cdot(\log_{2}(q^{4}))^{2}$$\mathrm{P}\mathrm{o}\mathrm{f}5\mathrm{a}\mathrm{r}\mathrm{d}\mathrm{w}.\mathrm{s}$.屋$\mathrm{u}r$禍$\mathrm{e}\dot{\mathrm{B}}\mathrm{f}$desceflt–$\mathrm{p}_{\mathit{0}}||\mathrm{a}\mathrm{r}\mathrm{d}’\mathrm{s}p$methOd–Our WeiI descent$\dot{|}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$point:

210 bits
method is stronger
in the reat size parameters.
$\beta$bit length of group order