数学アルゴリズム問題の研究調査

２００２年度「数学アルゴ リズム問題の研究調査」

1 はじめに本文書は楕円暗号の安全性の根拠である楕円曲線離散対数問題について、
公開鍵暗号の安全性評価の際の基礎資料として用いられることを前提とした調査報告書である。

本報告書に於いて「現在」とは 2002 年 8 月を指す。
記号：p を素数、N を自然数とし 、q = pN とおく。本稿に於いて p, q, N は常にこの関係を満たしているものとする。q 個の要素からなる有限体を Fq と書く。
Fq 上定義された楕円曲線 E と Fq の有限次拡大体 k に対して E の k 有理点のなす群を E (k ) と書く。E の無限遠点を O, 自己準同型環を End(E ) により表す。E 上の X 座標関数、および Y 座標関数はそれぞれ  ,  と書かれる。n 2 N に対して pn 乗 Frobenius 射を Frpn と書く。n が N の倍数のとき（ すなわち、pn が q のベキとなるとき）は Frpn 2 End(E ) となる。
一般に、群 G と g1  : : :  gn 2 G に対してそれらが生成する G の部分群を
hg1  : : :  gn i と書く。

2

楕円曲線離散対数問題

E を Fq 上定義された楕円曲線とする。楕円曲線離散対数問題とは一般の可換群に対する離散対数問題を E (Fq ) に適用してできる問題であり、具体的に書くとB 2 E (Fq ), A 2 hB i が与えられたとき A = mB となる整数 m (0  m < ) を求めよ（ここで  は base point B の位数。）となる。既に述べたように楕円曲線離散対数問題は一般的な離散対数問題のなかの一つの問題であるから一般的な離散対数問題の解法が適用できることはいうまでもない。特に Pohlig-Hellmanの解法が適用できないために(*)  は大きな素数であり、 2 は E (Fq ) を割らない1

2002.8.29

2としてよい。ここでは楕円曲線離散対数問題に固有の解法について考察する。
楕円離散対数問題の解法（＝楕円曲線暗号・署名への攻撃）は以下のように大別される(1) ほとんど すべての楕円曲線に適用できる。
(2) 特定の楕円曲線に適用できる、あるいは特定の楕円曲線の場合に特に効率良く楕円曲線離散対数問題を解くことができる。この場合さらに解法の適用対象となる楕円曲線に関して以下のような状況に分類される。

(A) 必要条件が分かっている。
(A+) 必要十分条件が分かっている。
(B) 必要条件は分かっていないが 、十分条件は分かっている。
(C) 必要条件も十分条件も分かっていない。
このどの場合に該当するかで楕円曲線離散対数の困難性を維持するための方策が異る。現在までに 、(1) 型の解法で 、楕円曲線暗号に対して脅威となる

方法は筆者の知る限り得られていない。(A) あるいは (A+) の場合、楕円曲線暗号の安全性という立場からは、必要条件を満たさない曲線を採ることでこの解法の適用を逃れることができる。(B) の場合、少なくとも十分条件に合致する楕円曲線は採用すべきではない。ただし 、必要条件が分からない以上、十分条件に合致しないからといってこの解法が全く適用できないということにはならないことに注意を要する。(C) の場合、今後さらに研究が必要
である。

2.1

乗法群への埋め込み

これは上記分類では (A+) 型である。k :=min n とおいたとき hB i の離散対数を Weil pairing あるいは Tate pairing を用いて Fqk の離散対数問
題に帰着させる。後者には現時点で既に index calculus 法という「 q k に関して」準指数時間のアルゴリズムがある。Weil pairing を用いる方法は Menezes,
Okamoto, Vanstone24], Semaev32] らにより、Tate pairing を用いる方法はFrey, Rueck9] による。k の値が小さくなることが MOV reduction の必要条件であることが Balasubramanian, Koblitz2] により証明されている。
k の値を求めることは一般には自明ではないが、k の値が少なくとも O(log q)
ではないことは簡単に検証できる。超特異曲線に対しては常に k  6 となる。
 j(qn ;1)

ランダムに選んだ楕円曲線に対して k の値が有界な範囲に属する確率はおおpq) である。

よそ O(1=

2002.8.29

2.2

3

加法群への埋め込み

これは上記分類では (A+) 型であり、（ 条件 (*) の下で ）適用可能となる必要十分条件は  = p である。Tr(Frq )  1 mod p であるとき、E (Fq ) は自明

ではない p torsion 部分群を持つ。この p torsion 部分群に対する離散対数問
題は Fq への多項式時間埋め込みを使って効率良く解くことができる。この埋め込みは現在のところ大きく分けて二つの方法がある。

(1) 代数幾何的方法 (Semaev33])(2) 数論的方法 (Smart37], Satoh-Araki28, 29])
後者の方が多少高速であるが 、楕円曲線離散対数の困難性という観点からこの二つの方法の計算量の差は無視でき、いずれの方法でも、E 上の点の加法を O(log q ) 回実行する時間で離散対数が解かれる。特に素体上の楕円曲線に対しては Tr Frp = 1 となるとき  = p となり楕円離散対数は多項式時間で完全に解かれてしまう。このような楕円曲線は Mazur22] に従って anomalous

curve と呼ばれる。

解法の概要は以下のようなものである。E , B , A を p 進体 Qp に持ち~ , A~ とする。pB~ に対応する local parameter
上げ たものをそれぞれ E~ , B

B := ; (pB~ )=(pB~ ) が 0 mod p2 なら別の持ち上げを取る。そうでなけれ~)=(pA~) も 0 mod p2 ではなく m := A =B が A = mB とば A := ; (pA
なる m を与える。この方法で正しい答が求まることを示すときに B の位数
が p がであることが随所で使われ 、そうでない場合に一般化するのは困難であろうと思われる。
（ そもそも、hB i から Fp への群準同型はすべて 0 写像となってしまう。）この解法を回避するため、 = p すなわち pB = O となる E を用いてはならない。ランダムに選んだ Fp 上の楕円曲線が anomalouspになる確率は O(1= p) である。

2.3

自己同型写像による高速化

この方法は (B) 型である。可換群 E (Fq ) の（ 可換群としての ）自己同型

写像のなす群を A とする。
（これは代数曲線 E の自己同型群 Aut(E ) ではな

い。A は Aut(E ) よりも遥かに大きな群であり、Aut(E ) が小さいことと Aが小さいことの間には何の関係もない。）A は E (Fq ) に左から作用しているが 、A の各元は E (Fq ) の各点の位数を変えないから条件 (*) の基で hB i は

A 不変、すなわち任意の f 2 A に対して f 2 Z で f (B ) = f B となるものがある。

A の部分群 G で(i) hB i の点が G n hB i のどの軌道に入るかを判定する時間が E 上の加法に要する計算時間に比して無視できる2002.8.29

4(ii) f 2 G に対して f が既知であるというものがあれば 、Pollard の一般の群に対する法を hB i に適用したときの計算時間はp#G になることが Wiener,

法の計算時間に比べて 1=

Zuccherato39], Gallant, Vanstone12] により指摘されている。どのような楕
円曲線に対しても T := h;1i は上記条件を満たすことに注意する（このとき;1 = ;1, #T = 2 である）。ここでは、これを「自明な改良」と呼ぶことにする。

d が N の約数で E が F2d 上定義されている状況を考える。簡単のため、
d := Fr2d とおく。G := h;1 d i は上記条件を満たす。このとき #G はA の元として;1 2 h d i なら N=d, そうでなければ 2N=d である。また dの値は O(log q ) だから楕円曲線暗号に用いる N に対しては d は全数探索

pN=d 倍速く解くことができる. （なお、ここでは自明な改良さえ用いない、などで簡単に求まる。この場合、自明な改良に比べて離散対数問題を最大限一般の群に対する

法を比較の対象とはしない。）この解法がもっとも良く機能するのが d = 1 となる Koblitz 曲線 21] （ anomalous binary curve, 略

して ABC ）の場合である。このような G による解法を回避するためには Eの定義体が Fq の真の部分体とはならないようにすれば良い。また、何らかの事情により E の定義体が Fq の真の部分体となる場合は  を一般の場合に安全と見込まれる値よりもp

N 倍以上大きく取ることが必要である（が 、十分であるかど うかは分からない）。

また、ecient endomorphism を持つ楕円曲線については今後検討する必要がある。これは ecient endomorphism とは Gallant, Lambert, Vanstone13]により提唱された概念で、少ない計算量で計算できる自己準同型のことを指す。このような自己準同型を持つ曲線では曲線上の整数倍演算が高速に行える。

この結果は Park, Keong, Kim, Lim27], Sica, Ciet, Quisquater34] により厳密な証明がつけられ 、なおかつ一段の高速化が計られているが 、他方において自己同型写像による攻撃をも効率化する。Gallant, Lambert, Vanstone13]は（ 証明・数値例をつけずに ）「適用対象とならない」とだけ述べている。この点について、理論的な検証・数値実験等を行う必要があると思われる。
これ以外の場合に自己同型写像による方法の適用可能な場合を系統的に調べた文献を筆者は知らない。A は Aut(E ) よりもだいぶ大きな群であるが 、他方、あまり #G が大きくなると (i) のための計算時間が無視できなくなる可能性があり、今後この解法の適用範囲についてさらなる検討が必要と思われる。

2.4 Weil descent による方法
q 上の楕円曲線 E 上の離散対数問題を E を Fq 部分体に係数制限してでF

きる Abel 多様体に含まれる超楕円曲線 の Jacobian 上の離散対数に帰着させ2002.8.29

5

るものである。基本的な枠組は Frey8] により示され 、Galbraith, Smart10]により実行時間が準指数時間であることが示された。Gaudry, Hess, Smart15]では具体的な一つのアルゴ リズムが与えられた。これを 以下 GHS 法と呼ぶことにする。GHS 法を適用するための必要条件は Menezes, Qu23] により明らかにされたが 、Weil descent の枠組で論ぜられる一般のアルゴ リズムがどの場合に適用できるかは現在のところ知られていない。 GHS 法は (A) 型に分類されるが Weil descent 自体は (C) 型であるといえる。

以下、d を N の約数（ d 6= N とするが d = 1 は認める）とし 、n := N=d,k := F2d とおく。楕円曲線 E=Fq に対して A を E の k への係数制限とする。
A は n 次元の Abel 多様体である。このとき Gaudry, Hess, Smart15] は nが偶数のときすべての E に対して、また n が奇数でおおよそ半分の E に対して A と（ E に依存しない）n ; 1 個の超平面との共通部分の既約成分が超楕
円曲線 C になることを示し 、しかも E (Fq ) から C の Jacobi 多様体 JC (k )への計算可能な群準同型を与えた。もしこの準同型写像の hB i への制限が単射ならば hB i 上の離散対数を JC (k ) の離散対数に帰着できる。このようにして作られた C の genus g は E に依存するが 、もし JC (k ) 上の離散対数問題が解けるのなら hB i 上の離散対数問題も解けてしまう。JC (k ) 上の離散対数を解く方法には一般的な Pollard の 法以外にも Adleman, DeMarrais,
Huang1] による準指数時間アルゴ リズムや Gaudry14] など の方法がある。
上述のようにして構成された C に対して JC (k ) の離散対数問題が解けるとは限らないが 、hB i 上の離散対数を 法を用いて解くよりは速くなる場合があり得る。Menezes, Qu23] は GHS 法が適用できる場合を分析して、その適用対象は限定的であるとしている。たとえば n が素数の場合、Fn における2 の位数が小さい（ 現在のところせいぜい 13 以下）ことが必要である。（ もし 、この値が大きければこの N に対して Fq 上の全ての楕円曲線が GHS 法の適用対象とならない。）ただし 、これはあくまでも GHS 法そのまま適用した場合の結果であり Galbraith, Hess, Smart11] らは GHS 法を拡張し 、より多くの曲線が GHS 法の適用対象になりえることを示した。彼らによれば
ランラムに選ばれた F2155（ 注：155 = 5  31 ）に対して元の GHS 法が適用可能となる確率は 2;122 だが拡張された GHS 法を用いたときのこの確率は2;52 とのことである。
GHS 法を回避するだけならば N を素数でかつ FN における 2 の位数が小さくならないようなものとすればよい。
（ 160 から 600 までの素数はすべてこの条件を満たす。）しかし 特定の拡大次数 N が Weil descent の一般的な枠組にたいしてその適用対象となり得るかということについては現在のところ知られていない。N の約数が多ければそれだけ適用パターンが増えることから N を素数とすることが考えられるが 、これだけでは不十分（ たとえば N = 127 は GHS 法に対して弱いと考えられている）である。また、Weildescent 法では最終的には超楕円曲線上の離散対数問題を解くことになるの2002.8.29

6でその解析には楕円曲線のみならず超楕円曲線上の離散対数問題も合わせて考察することが必要である。

2.5 Xedni calculus
Xedni calculus は Silverman35] と Kim, Cheon, Hahn20] により独立に発見された確率的アルゴ リズムである。いまのところ、この方法がどの曲線に対して適用できるかは知られていない。従って (C) 型に分類される。

Jacobson, Koblitz, Silverman, Stein, Teske18] はある定数 C0 があり、任意の E=Fp に対してこのアルゴ リズムが成功する確率は C0 =p 以下であることを証明した。しかし 、現在のところ C0 の値は非常に大きく楕円曲線暗号で用いられる程度の p に対しては C0 =p は無視できるほど 小さくはない（それどころか 1 より大きくなり得る）。 18] では各種の数値実験も行い暗号で用いられる p に対しても xedni calculus は適用できそうもないと結論しているが 、これはあくまでも実験の結果に基づく経験則に過ぎない。他方、E が与えられたときに xedni calculus にとって都合のよい持ち上げが存在しない

ことを示す定理もアルゴ リズムも知られていない。ところで 18] は素体上の楕円曲線についてのみ考察されている。小暮 40] は Xedni calclus を標数 2の体へ適用するための必要な変更を明らかにし 、実装実験を行っている。この結果を見る限りでは Xedni calclus が標数 2 の大きな有限体上の楕円曲線に対して適用できる可能性は大きくはなさそうである。しかしながら、実験に用いられた曲線の数が少ないため、今後さらに詳細な分析が必要であると
思われる。

3

楕円曲線の位数計算

E を Fq 上定義された楕円曲線とする。#E (Fq ) をできるだけ小さな計算量で求める方法について現在までに知られている方法は ` 進的方法と p 進的方法に大別される。前者はいわゆる SEA アルゴ リズムであり、後者は標準持ち上げを用いるもの、算術幾何平均を用いるものなどがある。以下、多項式乗算あるいは多倍長整数乗算に Karatsuba 法を用いる場合は素朴アルゴ リズムを用いる場合は:= log2 3 、:= 2 とおく。特に断りのない限り、時間計算量は bit 演算の数を表し 、領域計算量は必要とされるメモリーのサイズを表すものとする。

f 2 End(E ) に対して End(E ) の元として f 2 ; cf + q = 0 が成立するような c 2 Z がただ一つ存在する。この c を f の trace といい Tr(f ) により表す。このとき Hasse の関係式

#E (Fq ) = 1 + q ; Tr(Frq )(3:1)

2002.8.29
および Hasse の不等式

7pjTr(Frq )j  2 q(3:2)

が成立する。

3.1` 進的方法

Schoof, Elkies, Atkin らによるアルゴ リズムを総称して SEA アルゴ リズ
ムという。このアルゴ リズムは N が log p ないしその数倍程度のときは適用できないが 、楕円曲線暗号への応用に際しては p が大きく N は高々 10 以
下、あるいは p = 2 で N が 100 以上なので問題は無い。時間計算量は経験的に O((log q )2+2 ) と見積もられているがこのような評価を数学的に証明することはできそうに無い。しかしながら、この経験則は実験と良く合い、実
際にいろいろな q の値に対して Fq 上の楕円曲線をランダムに発生させるとSEA アルゴ リズムの所要時間の平均値は概ね O((log q)2+2 ) 程度であることが観察される。他方、これはあくまでも平均値であり、最小値と最大値の開きが大きいので real time 系への応用など 、最大時間を上から押えなければならない場合には注意を要する。

SEA アルゴ リズムの基本は Schoof のアルゴ リズム Schoof31] である。MQ `  4pq となる最小の自然数とするとを`M`6=p

M = O(log q)(3:3)

である (Chebyshev の定理 3])。p と異る小さな素数 ` = 2, 3, 5, : : :, M に対して Tr(Frq ) mod ` を求めれば Chinese remainder theorem と Hasse の不等式 (3.2) より Tr(Frq ) が求まる。すると Hasse の関係式 (3.1) から #E (Fq )が求まる。

Tr(Frq ) mod ` を求めるには Frq の E `] への作用を調べれば良い。素数 `と c 2 Z に対して Fr2q ; cFrq + q の E `] への制限が零写像である（ ` が素数だからこれは P 2 E `] かつ P 6= O で Fr2q P ; cFrq P + qP = O となるものが存在することと同値になる。）ならば c  Tr Frq mod ` である。ここでTr Frq mod ` を得るのに位数 `2 の群 E `] が用いられていることに注意する。
` 6= p のときは E `] の点が Frq でどのように動くかは E の ` 等分多項式使
い時間計算量 O((log q ) `2+1 ) で調べることができる。(3.3) より Schoof の方法のみを使って Tr(Frq ) を計算する場合の時間計算量は O((log q )3+2 ) であることが示される。

Elkies の方法 5] は E `] が Fq 上定義された位数 ` の部分群 V を持つときは Tr Frq mod ` が V から求まることに着目したものである。なお、E の部分集合 S は Frq S = S のとき Fq 上定義されているという。
（これは S の

各点 P に対して Frq P = P となることではない）このような V がある場合、` を E に対する Elkies 素数という。Tr Frq mod ` を計算するアルゴ リズム

2002.8.29

8の概要は以下のとおり：

E, `Output: E `] が Fq 上定義された位数 ` の部分群を持つときは Tr Frq mod `Input:

Procedure:

1: ` が E に対する Elkies 素数であるかど うか判定し 、そうでなければ終了
2: E と `-isogenus な楕円曲線 E 0 を求める。
3: E から E 0 への `-isogey の核 V （これが Fq 不変な E `] の部分群となる）を求める。

4: P 2 V , P 6= O に対して Frq P を求める。
5: Frq P = P となる 2 F` を求める。
6: + q= を返して終了
V を定義する方程式の次数は O(`) であり、Tr Frq mod ` を返すまでの上記アルゴ リズムの実行時間は O((log q ) `+1 ) でありその dominant step は
Frq P の計算である。 を求める部分を高速化する Dewaghe4] の方法が知られているが全体の時間計算量のオーダーを変えるものではない。Step 1 は具
体的には ` 次 modular 多項式 ` を用いて` (j (E ) X ) = 0 が Fq 内に解を持てば Elkies 素数であると判定する。ここで ` が必要であるが 、Elkies のアルゴ リズムの計算量を評価するときに ` を求めるための計算量は含めない。` は個々の E や q には依存しない整数係数多項式であるからただ一度計算しておけば良い。

問題はこのアルゴ リズムをどの範囲の ` に対して実行せねばならないかである。` が E の Elkies 素数となるのは ` が End(E ) の商体 K において分解するか分岐するときである。 E を K の判別式とすると、mod E では

おおよそ半分の ` が Elkies 素数となる。しかし 、一般には E は O(q ) であり、他方、ここで必要なのは適当な定数 c1 , c2 に対して ` < c1 (log q )c2 の範囲にどの程度 Elkies 素数があるかということである。このような（ q に比べて非常に ）狭い範囲で素数がどのように振舞うかは今のところ良く分かっていない。E を止めたときに ` が Elkies 素数となるのがランダ ムに起こるのならY`:Elkies prime`<M` > 4pq0となる M 0 の最小値は O(log q ) であることが期待され 、位数計算全体の計算量は O((log q )2+2 ) となることも期待される。

しかし ながらこのような評価は証明できそうにない。これは一般化されたリーマン予想 (GRH) の下で以下のことが証明できるからである (Mont-gomery25, Th 13.5])：ある定数 c > 0 pがあり、mod d での最小平方剰余がc log d log log d 以上となる虚二次体 Q( ;d) が無限個存在する。（ 厳密にいうと Montgomery の結果は平方非剰余について述べたものだが 、平方剰余についても全く同じ方法で証明される。）現在のところ GRH はあくまでも予想に過ぎないが 、その成立は多くの数論研究者が確信しているものである。自2002.8.299

己同型環の商体がこのような体になってしまう楕円曲線に対しては後述する

Elkies の方法が小さな素数 ` に対しては全く適用できず、M 0 = O(log q) とはなり得ない。

楕円曲線暗号で用いられる程度の q を止めて、ランダムに Fq 上の楕円曲線を生成し Elkies のアルゴリズムの時間計算量を計測すると概ね O((log q )2+2 )となることが観察される。しかし 、特定の楕円曲線に対して（ 後述の Atkinのアルゴ リズムを併用しても）実行時間は大きく変動することもあることには注意すべきである。なお、このことは Elkies のアルゴ リズムが確率的アルゴ リズムであることを意味しない。一旦入力となる楕円曲線 E が与えられた

場合、その実行過程は（ 有限体上の多項式の因数分解を除き）deterministic

である。

3.2 Atkin の方法` が Elkies 素数でないとき Elkies の方法では Tr Frq mod ` について何の情報も得ることができなかった。すなわち、Tr Frq mod ` がとり得る値は `個ある。Atkin はこのような場合でも Tr Frq mod ` の候補を得る方法を示した。Frq の固有方程式 X 2 ; (Tr Frq )X + q = 0 の根 に対して r を r 2 Flとなる最小の自然数とする。このとき Tr Frq の可能な値は '(r)=2 個（ここでQ' は Euler 関数：'(r) = r (1 ; d;1 ), d は r の素因数を渡る）である。異るdAtkin 素数 `1 , `2 , : : :, `m が得られたときに Tr Frq mod `1    `m の可能な値の個数は m について指数関数的に増加するが 、m がさほど 大きくない場合はこれら候補の個数も計算機で扱えないほどではない。これにより Tr Frq を決定するのに必要な Elkies 素数の数を減らすことができる。この方法の詳細

は、Atkin 自身による論文は発表されていないようであるが 、Muller26] に詳しく解説されている。

3.3

p 進的方法

p を止めて N ! 1 としたとき現在得られている p 進的方法による楕円曲線の位数計算の時間計算量は漸近的に O(N 2+1 )（ N にのみ依存する事前計算を認めれば O(N 2+0:5 ), ONB が存在する場合だけでよければ (N 2+1=(+1) ) ）であり、` 進的方法よりも増大度が小さい。実用上は p はせいぜい数十程度が限度と見られ楕円曲線暗号への応用を考えたとき適用可能な場合は p = 2に限られるが 、p = 2 は p 進的方法が最も効果的に扱える場合でもある。
p 進的方法は有限体 Fq 上の楕円曲線 E を何らかの意味で剰余体が Fq になる完備離散的付値体 K に持ち上げ る。現在知られている速い位数計算ア
ルゴ リズムでは K として p 進数体 Qp の不分岐 N 次拡大体（ 同型を除いて一意に定まる）が用いられる。以下、K をそのようにとり R を K の付値

2002.8.2910環とする。K=Qp の Frobenius 置換（ これは Gal(K=Qp ) の生成元となる）

は  と記す。 は K 上の等長写像であり特にすべての m 2 N に対して環

R=pm の自己同型を導く。この導かれた写像も同じ記号  により表す。また考える楕円曲線はすべて非超特異であるとする。

E の K への持ち上げは多数あるが 、Frq も自己準同型として持ちあがる
ものは同型を除いて一意に定まる。これを E の標準持ち上げといい E " により表す。K 上の楕円曲線 E1 , E2 に対して Abel 群として Hom(E1  E2 ) =Hom(E1"  E2" ) であり左辺の元 f に対応する右辺の元を f " により表す。さらに環としてEnd(E ) = End(E " )

(3:4)

となる。

End(E ) において Fr2q ; Tr(Frq )Frq + q = 0 が成立するが 、(3.4) は同型だから End(E " ) において Fr"q 2 ; Tr(Frq )Fr"q + q = 0 が成立する。これはTr(Frq ) = Tr(Fr"q ) を意味する。Fr"q は標数 0 の体上の楕円曲線の自己準同型であり、E " の定義方程式は Tr(Fr"q ) を計算するのに十分な情報を含んでいる、といのが p 進的方法の基本的なアイデ ィアである。

3.4

算術幾何平均法

算術幾何平均は事前計算を認めず、すべての拡大次数に適用できるという条件の下で現在知られているアルゴ リズムのうち最も高速なものである。これは Harley et al16]. において発表された。なおこのアルゴ リズムは ArgoTech
社が特許を保有している。

a  b mod 8 を満たす a, b 2 R に対して

r !

a + b a b
M(a b) :=2a（ ここで平方根の符号は

pb=a  1 mod 4 となるように定める ）とおく。

M(a b) を a と b の算術幾何平均という。Eab を y2 = x(x ; a2 )(x ; b2 )により定まる楕円曲線とする。このとき Eab は EM(ab) と 2-isogenous であり、j (Eab )  j (E " ) mod 2t ならば j (EM(ab) )  j ( (E )" ) mod 2t+1 となる。ゆえに a0 , b0 を Ea0 b0 が E の持ち上げになるように定め (an  bn ) :=1
M(an;1  bn;1) により数列 fang1
n=1 , fbn gn=1 を定めると

lim j (Ean bn ) ; j (n (E )" ) = 0

n!1

(3:5)

である。ここで a0 , b0 を上のようにとると a0 =b0 2 1 + 8R となり、極限

lim a , lim b は存在しない（これは Henniart, Mestre17] の結果であるが 、(3.5) において fj ( n (E )" )g1
n=1 は明らかに収束しないことからも分か
n!1 n n!1 nる。）ことに注意する。算術幾何平均法の概要は以下のようになる2002.8.29
Input:

11

E : y2 + xy = x3 + c (c 2 Fq )Output:Tr Frq

Procedure:

1: a, b 2 R を Eab が E の持ち上げになるようにとる
2: M = (N + 1)=2] + 3
3: 以下を M 回繰り返す
4: (a b) = M(a b)
5: (c d) = M(a b)
6: t  NK=Q2 (a=c) mod 2M かつ jtj  2pq となる整数 t を返す
このアルゴ リズムの時間計算量は O(N 2+1 ) であり、かつ O-constant は極めて小さい。領域計算量は O(N 2 ) である。R の算術演算（ 加法、減法、乗法、および可逆元の逆元を求めること。当然のことながら実装にあたってはすべての計算は適切に定められた精度で行われる。）と Norm 計算がが既に使える（ 数式処理システム等にすでに組み込まれている、あるいは、C, C++からリンクできるライブラリが使用可能である）ならば上のアルゴ リズムを実装するのは容易である。

3.5 Norm 計算アルゴリズム
現在知られている標数 2 の有限体上楕円曲線の位数計算アルゴ リズムではいずれのものも最終段階で c 2 1 + 4R, c mod 2M が与えられたときに

NK=Q2 (c) mod 2M （ ここで M = N=2 + O(1) ）を計算する必要がある。
Satoh, Skjernaa, Taguchi30] は時間計算量 O(N 2+0:5 ) 、領域計算量 O(N 2 )のアルゴ リズムを与えた。従来法と異りこのアルゴ リズムでは解析的手法を用いて計算する。

exp(x) :=およびlog(y) :=1 1
Xnn=0 n!

1 (;1)n;1
X
n=1

n

x

(y ; 1)n(3:6)

とおくとこれらは x 2 4R, y 2 1 + 2R のとき収束し 、（ 考えている値が収束する限り）通常の指数関数、対数関数と同様な関係式を満たす。なお、上記

無限級数の収束は K において考えているのであり、exp の収束半径は無限大ではない。また、 は連続であり、 n1 2 Q

Q

2 だから  (log(y )) = log  (y )である。c 2 1 + 4R という条件（これは以下に現れる級数の収束を保証する）の下で

NK=Q2 (c) =

NY
;1
j =0

0N ;1
1
X
j (c) = exp @ log(j (c))A = exp(TrK=Q log(c))
j =022002.8.29

12となる。TrK=Q2 の値は Q2 に属するので exp の計算量は無視できる。TrK=Q2の計算は 、本質的には足し 算であり、この計算量も無視できるほど 小さい。
このアルゴ リズムの主要項は log(c) の計算であり、(3.6) をそのまま計算すると時間計算量 O(N 2+1 ) となってしまう。

c  1 mod 4 を満たす c 2 R が mod 2M の精度で与えられているとき t  0
ttに対して c2  1 mod 22+t かつ c2 mod 2M +t は well-dened である。したt
がって log(c2 ) mod 2M +t を計算するには (3.6) を O((M + t)=(t +2)) 項計算tすれば良い。この値が求まれば log c mod 2M は 2;t log(c2 ) として得られる。
p
この計算量は O(N  M  max(t (M + t)=(t +2))) であるから、t = O( M ) ととり時間計算量 O(N  M +0:5 ) 、領域計算量 O(NM ) で log c mod 2M が求まる。なお、この部分は time-space tradeo が効き、領域計算量が O(NM 4=3 )まで増大しても良いのなら時間計算量を O(N  M +1=3 ) まで押えることができる。
（これは R. Harley の注意による。）

楕円曲線の位数計算において norm 計算を行うときは M = N=2 + O(1) であったので時間計算量 O(N 2+0:5 ), 領域計算量 O(N 2) で norm 計算は終了

xする。また、30] では log 11+;x = 2速化が行われている。

3.6

1
P

1

n=1 2n;1x2n;1 を用いてさらに若干の高事前計算を認める場合の高速計算

K は Qp 上有限次拡大だから K = Qp () となる 2 R がある。 の monic

な Qp 上の最小多項式を F とする。
（ 実用上は  は F のゼロでない係数の2 R で q;1 = 1
かつ  mod p を満たすものが一意的に存在して R = Zp  ] となる。
は一の巾根だから  は R に  ( ) = p により作用している。よって
Cm ( ) := ;1 ( m ) とおくと;1 の R への作用は具体的に数ができるだけ小さくなるように選ばれる。）このとき

 ;1

NX;1
i=0

と書ける。以下、

0
1
! pX
;1
X
ai i = @apk+m k A Cm ( )m=0 0pk+m<Nの monic な Qp 上の最小多項式 G と C1 , : : :, Cp;1 が事前計算されているものとする。これは N と  にのみ依存する。なお、この事前計算は、N  600 程度に対しては容易に実行でき、現在楕円曲線暗号で用いられる楕円曲線に対しては問題とならない。R = Zp X ]=hGi であるがG は一般に密な多項式であり Zp X ]=hGi の乗算は Zp X ]=hF i の乗算に比べて 3 倍ほど 遅いことに注意する。

楕円曲線 E=Fq が j (E ) 62 Fp2 を満たしているとする。このとき、Ver-

cauteren, Preneel, Vandewale38] のアルゴ リズムを多少修正して j (E " ) modpM を時間計算量 O(N  M 1+ ), 領域計算量 O(NM ) で求めることができる。
具体的手順は：

2002.8.29

13

j (E )Fq , M 2 N,"
M
Output: j (E ) mod p
Input:

Procedure:

1: x1 := any lift of a to R 
2: for (i = 1  i < M  + + i) f
3: p (bi  xpi ) = 0 かつ bpi  xi となる bi を求める。
4: xi+1 := ;1 (bi ) 
5: g
6: return xM 
ここで Step 4 で  ;1 を作用させた結果、xi+1  xi mod pi が成立するから
di+1 := xi+1 ; xi とおくと di 2 pi R となる。よって@1 p (bi;1  xi;1 )(di+1 ) + @2 p (bi;1  xi;1 )di  0 mod p (3:7)となる。
（ @i は i 番目の変数に関する偏微分。）xi+1 は mod pi+1 でしか意味を持たないから Koroecker relation を用いて xi+1 を求めるには p;i di mod p

だけが本質的であることが分かる。従って (3.7) においてすべての計算を本質的に mod p の精度で（すなわち Fq で）済ませることができるので計算時間が短縮される。しかし 、この考えをおし進めて xM = x1 + d2 +    + dM を用いてxM を求めようとすると di 達は mod pM の精度で計算せねばならず、かえって計算量が増えてしまう。Satoh, Skjernaa, Taguchi30] は適当な W をとり、
x(n+1)W を xnW から計算するのに dnW +1 のみを mod p(n+1)W で、dnW +2 ,: : :, d(n+1)W を mod pW で計算することによりこの問題を解決した。このW は理論上は時間計算量を最小にするように選択するべきであり、楕円曲線の位数計算においては M = N=2 + O(1) であるから W = O(N =(+1) ) ととるべきである。j (E " ) mod pM +O(1) を求める時間計算量は O(N 2+1=(+1) )である。しかし 、楕円曲線暗号で用いられる楕円曲線の位数計算においてはW を N に関係なく CPU の語長（の整数倍）ととるのが実際的である。
j (E " ) が求まったあと、Fr"p の双対同種写像 Vp" を局所パラメーターで展開したのときの１次の係数 c を求める必要がある。c が求まれば Tr Frq はt  NK=Qp (c) mod pN=2+O(1) かつ jtj  2pq を満たす整数である。c の計算は、特に p = 2 のとき、数学的には難しい問題であるが現在 Fouquet, Gaudry,Harley6] による方法、Skjernaa36] による方法が知られておりいずれも計算
時間は O(N 2 ) であり他の部分に比べて無視できるほど 高速である。以上を総合して、事前計算を認める場合、位数計算の時間計算量は O(N 2+0:5 ) と

なる。

3.7

特殊な拡大次数に対する高速計算

Kim et al.19] は Fq =Fp が Gauss 周期により生成される正規底（ この
重要な一例が type I および type II の ONB である）を持つ場合に Satoh,2002.8.29

14

Skjernaa, Taguchi30] で必要であった事前計算が不要となり、かつ norm 計算の時間計算量が O(N  log N ) で済むことを示した。彼らは Fq =Fp が Gauss
周期により生成される正規底を持つとき K=Qp も Gauss 周期により生成される正規底を持ち、正規底による表現と標準基底による表現の間を高速に変換することで R の算術演算を O(N 2 ) で行えることを示した。この結果として得られる楕円曲線の位数計算アルゴ リズムの時間計算量は O(N 2+1=(+1) )である。

 1 だからこれは前節の方法よりも漸近的には高速である。しかし 、実用上は R の乗算が前節で示した場合よりも 3 倍（ type I のとき）あるいは 1.5 倍（ type II のとき）速いことの寄与のほうが大きい。なお、type

I の ONB を持つ場合、N は必ず合成数となる。しかし 、type II の素数次
ONB を持つような体上の楕円曲線暗号への応用では有効である。

3.8

楕円曲線離散対数との関連

楕円曲線暗号にとって真に必要とされることは楕円曲線の位数を求めることではなく、楕円曲線暗号に適する曲線を求めることである。与えられた楕
円曲線 E に対して位数計算により E 上の離散対数の解法のうち少なくともPohlig-Hellmann, 乗法的埋め込み、加法的埋め込みが適用できるかど うかを示すことはできるが 、その他の攻撃に対しての安全性について何らかの見解を示すものではない。その意味で 、E の位数を求めることは E 上の離散対数の困難性に対する必要条件ではあるが十分条件ではない。

` 進的方法においては与えられた楕円曲線 E に対してアルゴ リズムの実行
途中で Tr Frq  0 mod ` となったならその時点で E は楕円曲線暗号に適さないと判断され 、直ちにこの曲線を棄却することができる。この技法は early

abort strategy と呼ばれる。p 進的方法はこのような性質を持たないが 、それでも小さな ` に対して ` 進的方法を使って E の位数が ` で割れないことを確かめてから位数計算を行うほうが高速であることが Fouquet, Gaudry,Harley7] により報告されている。この文献の表 3 および表 6 において同一の
platform で ` 進的方法と p 進的方法を比較した結果が載っている。それによれば p = 2, N = 155 および N = 197 対しては p 進的方法は ` 進的アルゴ リズムよりもおおよそ 3 から 4 倍程度高速である。なお、この文献が書かれた当時から ` 進的方法はさほど 進歩していないが本報告書で記載した p 進
的アルゴ リズムは当時よりも 4 から 6 倍程度速くなっている。従って、現在

では標数 2 の有限体上で楕円曲線暗号に適する楕円曲線を選ぶ時間は大きな標数の素体上のそれに比して遥かに速いのであるが 、他方において、素体上の楕円曲線と標数 2 の有限体上の楕円曲線に対する離散対数の困難性の比較に関する結果は現在のところ得られていない。

前述した 3 つの p 進的アルゴ リズムを同一の platform （と同一の演算ラ

イブラリ）を使って比較した結果は見当たらないが 、Kim et al.19, Table 1]

2002.8.29

15に各々のアルゴ リズムの提案者による実装結果が platform と共にまとめられており、参考になる。

4

特殊なクラスの楕円曲線
特殊なクラスの楕円曲線を楕円曲線暗号に用いることの是非については様々な議論がある。超特異曲線、anomalous 曲線などはそれらが提案された当時はそれらの安全性は特に問題がないと思われていた。しかし 、実際には後になってからそれらの上の楕円離散対数問題が弱いことが判明した。特定の曲線に対してのみ適用できる攻撃法が発見される可能性はすべての楕円曲線に適用できる攻撃法が発見される可能性よりも遥かに大きい。これに対して、
ランダムに楕円曲線を発生させる場合、その曲線が既存の攻撃法の適用対象ではないことを確かめてから使う必要があり、適切な曲線が見つかるまで少なくとも位数計算を繰り返す必要がある。また、「ランダムに選ばれた」とされる曲線が本当にランダムに選ばれているのかをど う検証するのか、本当に既存の攻撃に対する検討が済んでいるのかを誰が確認するのかという問題が残る。しかし 、これは PKI の問題であり、特殊なクラスの楕円曲線を（いくつか固定して ）使うことを支持する数学的理由は見当たらない。

なお、標数 2 の有限体上の楕円曲線の位数計算に関しては現在、実用上十分高速である。そのため、位数計算に伴うコストは以前と比べて非常に小さくなっている。ただ 、素体上の楕円曲線と標数 2 の有限体上の楕円曲線に対する離散対数の困難性の比較に関する結果は現在のところ得られていないことを考慮するする必要がある。

Koblitz 曲線 21] はもともとスカラー倍演算の高速化のために導入された曲線である。Menezes, Qu23] によれは Koblitz 曲線には GHS 法が適用できない。しかし 、F2 上で定義されているため前節に見たように Wiener,

Zuccherato39], Gallant, Vanstone12] の方法に対しては Koblitz 曲線は弱い。N ビットの一般的な楕円曲線を法により解くのと同程度の困難性をKoblitz 曲線に持たせるには N + log2 N + 1 ビット以上の体を用いることとなろうが 、このとき他の攻撃法の対象とならないかど うか慎重に考慮する必要がある。小暮 40] は Xedni calculus が一般の楕円曲線については適用できなくても Koblitz curve には適用できるかも知れないとの着想から実験を試みている。これによれば今のところ Koblitz curve が特に xedni calculus に対して脆弱であるという結果は得られていない。しかしながら 40] においては xedni calculus を標数 2 に適用するために修正する際 Koblitz curve の性質を用いてない。したがって Koblitz curve のみに適用できる xedni calculus

がどのような性質を持つかということについては未だ明らかにはされていない。繰り返しになるが 、現在知られているすべての攻撃法について考慮したとしても、将来 Koblitz 曲線に対する攻撃法が発見される可能性はランダム2002.8.29

16に選ばれた楕円曲線に対する攻撃法が発見される確率よりも遥かに大きいことはいくら強調しても強調しすぎ ることはない。

参考文献
1]

Adleman, L., DeMarrais, J., Huang, M.-D.: A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperellipitc curves over nite elds, Algorithmic
number thoery (Ithaca, NY, 1994), Lect. Notes in Comput. Sci., 877,
28-40, Berlin: Springer, 1994.

2]

Balasubramanian, R., Koblitz, N.: The improbability that an elliptic
curve has subexponential discrete log problem under the MenezesOkamoto-Vanstone algorithm. J. Cryptology 11 (1998) 141-145.

3]

Chebyshev, P.L.: Memoire sur les nombres premiers. J. Math. Pures
Appl. 17 (1852) 366-390 (!uvres, I-5).

4]

Dewaghe, L.: Remarks on the Schoof-Elkies-Atkin algorithm. Math.
Comp. 67 (1998) 1247-1252.

5]

Elkies, N.D.: Elliptic and modular curves over nite elds and related
computational issues, Computational perspectives on number theory(Chicago, IL, 1995), AMS/IP Stud. Adv. Math., 7, 21-76, Providence,
RI: AMS, 1998.

6]

Fouquet, M., Gaudry, P., Harley, R.: An extension of Satoh's algorithm and its implementation. J. Ramanujan Math. Soc. 15 (2000)
281-318.

7]

Fouquet, M., Gaudry, P., Harley, R.: Finding secure curves with the
Satoh-FGH algorithm and an early-abort strategy, Advances in Cryptology - Eurocrypt 2001 (Innsbruck, Austria, May 2001), Lect. Notes
in Comput. Sci., 2045, 14-29, ed. Ptzmann, B., Berlin, Heidelberg:
Springer Verlag, 2001.

8]

Frey, G.:
How to disguise an elliptic curve (Weildescent),(1998) Talk at ECC98 (available at
http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98/slides.html).

9]Frey, G., Ruck, H.-G.: A remark concerning m-divisibility and thediscrete logarithm in the divisor class group of curves. Math. Comp.
62 (1994) 865-874.

2002.8.29

17

10] Galbraith, S., Smart, N.P.: A cryptographic application of Weil descent, Codes and Cryptography, Lect. Notes in Comput Sci., 1746,
191-200, Berlin: Springer, 1999.
11] Galbraith, S.D., Hess, F., Smart, H.P.: Extending the GHS Weildescent attack, Advances in cryptology { Eurocrypt 2002, Lect. Notes
in Comput. Sci., 2332, 29-44, Berlin: Springer, 2002.
12] Gallant, R., Lambert, R., Vanstone, S.: Improving the parallelized
Pollard lambda search on anomalous binary curves. Math. Comp. 69(2000) 1699-1705.
13] Gallant, R., Lambert, R., Vanstone, S.: Faster point multiplication on
elliptic curves with ecient endomorphisms, Advances in cryptology- Proceedings of CRYPTO 2001, Lect. Notes in Comput. Sci., 2139,
190-200, ed. Kilian, J., Berlin: Springer, 2001.
14] Gaudry, P.: An algorithm for solving the discrete log problem onhyperellipitc curves, Advances in cryptology { Eurocrypt 2000, Lect.
Notes in Comput. Sci., 1807, 19-34, ed. Preneel, B., Berlin: Springer,2000.
15] Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facetsof Weil descent on elliptic curves. J. Crypto. 15 (2002) 19-46.
16] Harley, R.: Counting points with the arithmetic-geometric mean
(joint work with J.-F. Mestre and P. Gaudry), Eurocrypt 2001, Rumpsession, 2001.
17] Henniart, G., Mestre, J.-F.: Moyenne arithmetico-geometrique padique. C.R. Acad. Sci. Paris Ser. I Math. 308 (1989) 391-395.
18] Jacobson, M.J., Koblitz, N., Silverman, J.H., Stein, A., Teske, E.:
Analysis of the xedni calculus attack. Des. Codes Cryptogr. 20 (2000)
41-64.
19] Kim, H., Park, J., Cheon, J., Park, J., Kim, J., Hahn, S.: Fast elliptic
curve point counting using Gaussian normal basis, Algorithmic number theory (Sydney, Australia, July 2002), Lect. Notes in Cimput.
Sci., 2369, 292-307, ed. Fieker, C., Kohel, D., Berlin: Springer, 2002.
20] Kim, H.J., Cheon, J.H., Hahn, S.G.: Elliptic curve lifting problem
and its applications. Proc. Japan Acad. Ser A Math. Sci. 75 (1999)
166-169.

2002.8.29

18

21] Koblitz, N.: CM-curves with good cryptographic properties, Advances in cryptology|CRYPTO '91 (Santa Barbara, CA, 1991), Lecture Notes in Comput. Sci., 576, 279-287, Berlin: Springer-Verlag,
1992.
22] Mazur, B.: Rational points of Abelian varieties with values in towersof number elds. Invent. Math. 18 (1972) 183-266.
23] Menezes, A., Qu, M.: Analysis of the Weil descent attack of Gaudry,
Hess, and Smart, Topics in Cryptology - CT-RSA 2001, Lect. Notes
in Comput. Sci., 2020, 308-318, Berlin: Springer, 2001.
24] Menezes, A. J., Okamoto, T., Vanstone, S. A.: Reducing elliptic curve
logarithms to logarithms in a nite eld. IEEE Trans. Info. Theory
39 (1993) 1639-1646.
25] Montgomery, H.L.: \Topics in multiplicative number theory". Lect.
Notes in Math., 227. Berlin, Heidelberg: Springer 1971.
26] Muller, V.: Ein Algorithmus zur Bestimmung der Punktanzahl elliptischer Kurven uber endlichen Korpern der Charakteristik grosser
drei, (1995) Dissertation der Universitat des Saarlandes.
27] Park, Y.-H., Jeong, S., Kim, C., Lim, J.: An alternate decompositionof an integer for faster point multiplication on certain ellipitc curves,
Proceedings of PKC 2002, Lect. Notes in Comput. Sci., 2274, 323334, ed. Naccache, D., Paillier, P., Berlin: Springer, 2002.
28] Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Commentarii Math.
Univ. St. Pauli. 47 (1998) 81-92.
29] Satoh, T., Araki, K.: Errata to the paper "Fermat Quotients andthe Polynomial Time Discrete Log Algorithm for Anomalous Elliptic
Curves". Commentarii Math. Univ. St. Pauli. 48 (1999) 211-213.
30] Satoh, T., Skjernaa, B., Taguchi, Y.: Fast Computation of CanonicalLifts of Elliptic curves and its Application to Point Counting, (2001)
preprint.
31] Schoof, R.: Elliptic curves over nite elds and the computation ofsquare roots mod p. Math. Comp. 44 (1985) 483-494.
32] Semaev, I. A.: On computing logarithms on elliptic curves. Diskret.
Mat. 8 (1996) 65-71 (Russian, English translation in Discrete Math.
Appl. 6(1996), 69-76).

2002.8.29

19

33] Semaev, I. A.: Evaluation of discrete logarithms in a group of ptorsion points of an elliptic curves in characteristic p. Math. Comp.
67 (1998) 353-356.
34] Sica, F., Ciet, M., Quisquater, J.-J.: Analysis of the Gallant-LambertVanstone method on ecient endomorphisms: elliptic and hyperelliptic curves, Proc. SAC 2002, 2002.
35] Silverman, J.H.: The xedni calculus and the elliptic curve discrete
logarithm problem. Des. Codes Cryptogr. 20 (2000) 5-40.
36] Skjernaa, B.: Satoh's algorithm in characteristic 2, (2000) preprint,(to appear in Math. Comp.).
37] Smart, N. P.: The discrete logarithm problem on elliptic curves oftrace one. J. Cryprology 12 (1999) 193-196.
38] Vercauteren, F., Preneel, B., Vandewalle, J.: A memory ecient version of Satoh's algorithm, Advances in Cryptology - Eurocrypt 2001
(Innsbruck, Austria, May 2001), Lect. Notes in Comput. Sci., 2045,
1-13, ed. Ptzmann, B., Berlin, Heidelberg: Springer Verlag, 2001.
39] Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems, Selected areas in cryptography (Kingston, ON, 1998),
Lect. Notes in Comput. Sci., 1556, 190-200, Berlin: Springer, 1999.
40]

小暮淳: Xedni calculus method について（ 標数 2 の場合）, 「暗号理論とそれを支える代数曲線理論」（ 2002 年 8 月 27 日、中央大学）.

補遺
楕円曲線離散対数問題に関連したアルゴリズム：2002 年 8 月〜2003 年 1 月末の新しい進展
以下、文献番号は報告書のもの
A. 楕円離散対数を求める効率の良い方法、あるいは既存の方法の改良に関しては、知り得た限り、特に記述すべきものは見当たらない。
B. 有限体上の楕円曲線の位数を計算する方法については下記の進展があった。
B-1: P. Gaudry: A comparison and a combination of SST and AGM[AsiaCrypt 2002 で発表；報告集 Springer Lect. Notes in Comput. Sci. 2501]は Harley et al.[15] の算術幾何平均(AGM)法に
Satoh, Skjernaa,Taguchi[28] による収束の加速法を組合せ位数計算をさらに高速にした。AGM 単
独の場合に比べて 163bit で約 4 倍、239bit で約 5 倍の高速化が達成されている。適用可能な体のサイズに制限はないが、SST と同様の（暗号への応用では問題とならない）事前計算を必要とする。
B-2: R. Lercier と D. Lubciz は標準持ち上げを求める上で新たな加速法を提案した（preprint.
Eurocrypt 2003 で発表予定）Newton の求根法は 2 乗収束であるが、微分可能な関数にしか適用できない。標準持ち上げを求めるためには Φ(x,Σ(x))=0（ここで Φ は多項式、Σ は Frobenius 置換）という型の方程式の根を求めなければならないが、Σ は微分できないので Neweton 法を直接適用することはできなかった。彼らは Σ(x)=ax+b （ここで a, b は適当な定数）という歪一次方程式が素早く解けるのなら、これを Newton 法に組み込み、収束を加速できることを示した。実際の漸近的計算量は Σ のベキの作用をどれだけ早く計算することに依存する。正規底が存在する場合には
Σ のベキは O(1) で計算でき、 FFT が有効に効くサイズでは位数計算全体の時間計算量の増大度は bit 長の 2 乗である。一般の場合、理論上は bit 長の 2.69 乗でこれは SST の 2.5 乗よりも遅い。しかし、楕円暗号の応用においてはこの FFT を使うという仮定は妥当ではなく、また当該論文に納められている実装結果は 1000bit 以上の体に対するものである。従って、この方法について
は（特に、タイプが小さい正基底が存在しない場合に）今後実装を含めてさらに調査が必要である
ものと思われる。
B-3: R. Harley は何らの事前計算を必要としない（正確にいうと事前計算の計算量が本計算の計算量よりも小さい）、すべての拡大次数に適用できる加速方法を発表した。
（氏の学位論文に掲載予定；
NMBRTHRY メーリングリストでアルゴリズムの詳細とともにアナウンスされた）FFT の元で時間計算量の増大度は bit 長の 2 乗であり、197bit での計算結果を見る限り、楕円暗号に用いられるサイズでも十分有効であると判断される。この方法は SST のように単一精度を用いて収束を加速するのではなく 2 乗収束させるよう細かく精度を制御して高速化を達成している。
楕円暗号に用いられるサイズで B-1 と B-3 の方法のいずれが速いかは実装依存である。
（漸近的な速度は B-3 の方が bit 長の 0.5 乗だけ速く、その優位は明らかである。
）
B-4: 下記の文献が出版された：[28] Finite Fields and Their Appl. 9(2003)89-101[33] Math. Comp. 72(2003) 477-487
以上