代数曲線とその応用論文小特集
素数位数を有する楕円曲線の構成とその計算量評価
堀内 啓次†
笠原 正雄†
布田 裕一††
境
隆一・††† 金子 昌信††††
Construction of Elliptic Curves with Prime Order and Estimation of lts
Comprexity
Keiji HORIUCHIt， Yuichi FUTAtt， Ryuichi SAKAIttt， Masanobu KANEKOtttt，
and Masao KASAHARAt
あらまし 楕円暗号において，楕円曲線の群の位数は重要なパラメータである．特に，その位数が素数であ ることが望ましい．楕円曲線の位数を計算する方法としてSchoofのアルゴリズム及びそれを改良したElkies，
Atkinのアルゴリズムが知られている．本論文ではSchoofの改良アルゴリズムを用いた素数位数を有する楕円 曲線の効率的な構成法を示す．更に，楕円曲線の位数分布及び位数が素数である確率を導出した後，素数位数を 有する楕円曲線の構成に必要な計算量を評価する．また，法pの条件による計算：時間の違いについて考察する．
キーワード 楕円曲線，素数位数，計算量
1．まえがき
近年における情報化社会の急速な発展により，情報 通信システムを介した情報交換の重要性がますます高 まっている．これに伴い，情報内容や個人情報の保護 を目的とした情報セキュリティ技術の研究が活発にな われている．こうした流れの中，昨今，特に注目され ている方式として楕円曲線を利用した暗号方式（楕円 暗号）を挙げることができる．楕円曲線を利用するこ
とによる有利な点はその離散対数問題を解く準指数時 間のアルゴリズムが存在しないことである．
楕円暗号に対する攻撃法として，Baby−Step Giant−
Stepを用いた攻撃M．0．V Reductionを用いた攻 撃［1］，及び，anomalousな楕円曲線に対する攻撃［2］
†京都工芸繊維大学工芸学部電子情報工学科，京都市
Department of Electronics and lnformation Science， Kyoto Institute of Technology， Matsugasaki， Sakyo−ku， Kyoto−shi，
606−8585 Japan
††松下電器産業株式会社マルチメディア開発センター，門真市 Multimedia Development Center， Matsushita Electric ln−
dustrial Co．， Ltd．， 1006 Kadoma， Kadoma−shi， 571−8501
Japan
†††大阪電気通信大学工学部，寝屋川市
Department of Applied Electronics， Osaka Electro Commu−
nication University， Neyagawa−shi， 572−8530 Japan
††††九州大学大学院数理学研究科，福岡市
Graduate School of Mathematics， Kyushu University， 6−10−
1 Hakozaki， Higashi−ku， F ukuoka−shi， 812−8581 Japan
が挙げられる．素体Fp上の楕円曲線のFp有理点を 考える場合，これらの攻撃に対して安全であるための 条件は，＃E（Fp）がp， p＋1でないこと，及び，その 最大素因数が十分大きいことである．一方，楕円暗号 の効率を上げるためには，法pのサイズを小さくする ことが効果的である．したがって，一定の安全性を保 ちつつ暗号化及び復号の計算効率を上げるためには素 数位数の楕円曲線がより好ましい．素対］Fp上の楕円 曲線の位数を求める方法として，Schoofのアルゴリズ ム［3］が知られており，Elkies， Atkinらはこのアルゴ
リズムを改良している［4］〜［司．このアルゴリズムは SEAのアルゴリズムと呼ばれており，実用的な時間で の位数計算が可能である．最近，伊豆，小暮らはSEA アルゴリズムで用いるパラメータを適切に設定するこ とにより，高速な位数計算を実装している［7］．
本論文では，2．でSEAのアルゴリズムに基づいて，
素数位数を有する素体IFp上の楕円曲線を効率的に構 成する手法を考察する．2．2ではアルゴリズムの分岐 点での分岐確率を導出し，その証明を与える．また，
3．で楕円曲線の位数分布を明らかにし，位数が素数で ある確率を導出する．更に，4．で素数位数を有する楕 円曲線の構成に必要な計算量を求め考察する．また，
法pの条件による計算：時間の変化を2．及び3．での解 析結果に基づいて調べる．
2．素数位数をもつ楕円曲線の構成法
本章では，楕円曲線の位数計算法であるSch◎ofのアルゴリズム，及びその改良アルゴリズムであるSEA アルゴリズムについて，必要最小限の概要を2．1で紹 介する．また，2。2でSEAアルゴリズムの分岐点での 分鼓確率を導出し証明を与える．更に，2． 3で素数位 数を有する楕円曲線の効率的な構成法を示す。Sch◎of のアルゴリズム及びSEAアルゴリズムの詳細に関し ては付録を参照されたい．なお，以下において，素 数位数を有する楕円曲線をEPO（elliptic curve with prime order）と略記する．
2．1 Schoof及びSEA改良アルゴリズム
Schoofのアルゴリズムは，固有方程式暢一麺ρ＋T｝・＝
0のトレースtを楕円導線の9等分多項式を用いて，
t（med 1）を求めることによりt（ltl≦2v効を求 め，楕円曲線の位数＃E（Fp）＝p十1−tを求める アルゴリズムである．ただし，t mod 9の算出は素数
1＝2，3，5， 7，…の順に行う。
SEAアルゴリズムは， t （mod 1）を求める部分に，
ω（学）一・のとき脳・・のア・レゴリズム
（2）（孕）一一1のときAtkinのア／レゴリズム を適用する．また，t（m◎d 9）が確定した時点で
Isogeny Cycle法［8］を適用し， t （mod 12，13，…）を
ま求める．以下（が一4ρ 暑）が1，◎，一1の場合をそれぞれ Case一一Elkies， Case−Schoof， Case−Atkinと呼ぶことに
する．なお，Case−Atkinの手法はt （mod 1）の候補 を求めるものであり，t （m◎d 1）は確定しない．2．2 SEAアルゴリズムにおける分岐確率の導出 ここで，SEAアルゴリズムにおいてCase−Elkies，
Case−Schoofへ分岐し， t （modのが確定する確率を 求めておく．各1においてCase−Elkies，及びCase−
Sch◎◇fへの分岐確率をPEξ（9）と表記する．トレース t及び素数pをランダムに与えたとき，次の定理が成
立する。
［定理1】SEAアルゴリズムにおいて，9＝2の場合，
すべての素数pに対してPEI（の：1となる．1が奇 素数の場合，ランダムに与えたt及び素数pに対し て，PEt（のニ1／2である． 口
（証明）
i） ＝2のとき
（≒4P）（写）一・または・（t一・のとき）
電子情報通信学会論文誌ラ99／8 Vel．」82−A N◎．8
より，確率は1である．
ii）♂が奇素数のとき
tを固定，p＝◎，1，…，1 一1（mod 1）とすると t2−4Pは◎，1，…メー1 （mod 1）のすべての値を
とり得る・
it2 一 4p l）一・または◎となる雛 の数は（9 ＋1）／2である、p半0 （mod 9）であるので，それを除くと（i一・・一 1）／2である．したがって，pを
1，2，…，9−1 （m◎dt）の中でランダムに選ぶとき，（t2 一一 4p l）一・または◎となる鰍掛一1
である．これは任意のtに対して成り立つ． m tをランダムに与え，pを固定した場合の確率はp の条件により変わる．このとき，次の定理が成立する。
［定理2］（￥）＝1のとき，ランダムに与えたtに対
して・禰一睾となる・
（￥） ：一1のとき，ランダムに与えたtに対して，
（証明）
分岐確率p蝋のを求めるためには，（の ＝1とな る素数p，1に対し，
＃｛tEFi 1 （！i2r．．．ylz2ww4p）・ 1 or・｝（ユ）
を評価すればよい．
（￥）＝1．であるから，4p ・・ ＄2 （m◎d 9）を満たす
＄蔓躍が存在する．任意のSl，s2∈職（Sl≠s2＞に 対し，r∈恥をrs1…wr s2 （mod 9）とすると，
（≒り一（≒り（ギ）一（（鴎一謬）
（2）
と変形される．ゆえに，s1，、s2∈Fl（Sl≠s2）に対し，
孝個（≒り一1｝
一＃｛t ff ■1（≒り一・｝
が成り立つ．一方Zt ・t＋s，v ・・t一一sとおくと，
t2 一 s2 t
＃｛t∈F・・ s∈畷
・・ ＃｛耀∈畷号）G）
（1 一 1）2
一 （1 一 1）
2
︶︸
一・戟i∫・）
（3）
論文／素数位数を有する楕円懸線の構成とその計算量評懸 したがって，任意のs∈Frに対して，
＃｛妊畷≒82）一・｝
g−1
ご一3 ：一 一1＝
2 2
（4）
となり，これより，（2t）＝1となる素数 ，pに対し，
＃｛tffm 1 （g：2 f： s2） ，，，ioro｝
g−3
g十1
（5）
＝ 一 十2＝
2 一 2
が成り立つ・したがって二一睾となる洞門
にω司のとき・馴一場となる・□
2．3 E：POの構成法
本節では，SEAアルゴリズムを用いたEPOの効率 的な構成法を示す．EPOの構成法の概要は次のとお りである，まず，ランダムに選んだ楕円曲線に対して，
SEAアルゴリズムを適用する．ここで， SEAアルゴリ ズムの各ZにおいてCase−ElkiesまたはCase−Schoof へ分岐し，t（mod 1）が確定した場合，この時点で，
位数が9を因数にもっか否かの判定が可能である．位 数がεを因数にもっと戦定されれば，即座に楕円曲 線を選び直し．これをEPOが得られるまで繰り返 す（注1＞．なお，twistされた楕円曲線も同時に判定を行
う．以下にアルゴリズムの詳細を示す．
［アルゴリズム3］（EPOの構成アルゴリズム）
入力：素体軸
出力：楕円曲線E／Fp：＃E（葦㌔〉：素数
［Step 1］適当な素数pを選ぶ．
［Step 2］楕円曲線E（IFp）をランダムに選ぶ．
［Step 3］Eの位数＃EをSEAアルゴリズムによ。
て求めるがt （m◎d 9）が求まるたびにll＃Eを平 定する．この際，twistされた楕円曲線E に対しても 同様の判定を行う．
［Step 4］＃E，＃Efの両者がStep 3で合成数と判定 されればStep 2へ戻る。
［Step 5］＃Eまたは＃E が素数（十P）であれば終 了．そうでなければStep 2へ戻る．
3。楕円曲線の位数分布及びEPOの存在
確率
楕円曲線を構成する上で，楕円曲線の位数がHasse の範囲内でどのように分布しているかは，基本的かつ
重要な問題である．本章では，楕円曲線の位数分布を 導出し，更に，位数が素数である曲線EPOの存在確 率を見積もる．なお，個数を表すときは互いに同型な 楕円曲線を同一ecする．
3．1 楕円曲線の位数分布
本節では，楕円曲線の位数分布を導出する．
判別式D：VZ［i5 ： iiである位数x＝p＋1−t を有する楕円曲線の個数は，Kroneckerの忌数H（D）
に一致する．また，H（D）及び楕円曲線の総数は，次
式のように表せる｛11］．
面
ff（D）一 X h（f．；，）
幅1，妊21D
2＞／す（6）
総数一
更に，虚2次体の類tw h（D）はあたかも，
Σん（の一、8表3）D3／2
−D＜dく0
ユ h（D）〜OIDIs
（8）
（9）
のように振る舞うことが知られている［1◎！．ここで，
位数分布の平均値を求める．式（6）と式（9）より ユ
H（D）〜0 P蒼とし，Hasseの範囲で積分した値が楕 円曲線の総数2（p−1）ty 2pであることからH（D）の
平均値は，主D亮なる叫したがって請円曲線の
π
4P一（P十1−x）2 位数が￠となる確率密度関数は，
2πP となり，ここで，
p十1−x
cos e ＝
2＞歴
なる変数変換を行うと，確率密度関数は，
2 sifi2 e
T
（10）
（ll）
となり，佐藤予想との類似関係が得られる［12］．
素体Fp上での楕円曲線の位数分布と，その平均値 を図1に示す．これによると位数はHasseの範囲でほ ぼ一様に分布していることが確かめられる．この結果 より，EPOも偏りなく存在していることが予想でき るが，避寒でEPOの存在確率を導出する．
（注1）：Lercierによっても独立に提案されている［151．しかし，筆者 らの手法は，更に，計算時間を短縮するためにCase−Atikin， Isogeny Cycleの計算は可能な限り後回しにするという拳法である，
器≧きO置一一20﹂2∈コZ 10000
1OOO
100
to
p＋1−2sclrt｛P）
Number of ell． curves
D／pi 一一一
︑黛．導︑一バ︒
︑． 〜
・さ ▼
p＋t
Number of Point
p＋t＋2sqrt（p＞
図i 素体璽雪 （p ＝ 524287）での楕円懸線の位数分霧
晦1Di・t・ib・ti…f・rd…f・IL…．・v・・F。．
3．2 EPOの存在確率
本節では，EPOの存在確率を導出する．素体Fp上 定義された楕円曲線E（Fpの位数＃E（Fp）が素数1 で割り切れる確率をP（1），割り切れない確率をPa。（9）
とする．文献［13］によると，
（12）
である．ここで，誤差項0（毒）は十分小さい値であ
る．式（12）より，
t−2
1
P・・（1） N fi． ew ＋R−1）・（9＋1） （13）
となる．楕円曲線の位数が素数となる平均確率をPp，
任意に与えた正整数が素数となる確率をPp。i，neとし，
これらの比をとる。
なお，この値は1≦IO12において計算すると
0．50516．．に収束するように振る舞う．したがって，
瑞はPp［，t O．50517／leg pと近似する．図2に，1◎
進数9けた（32ビット）の素数標数の素体上において，
EPOの存在確率を示す．図2より明らかに瑞に対
し，EPOの存在確率は上下にばらつきがある．これ は，表1のようにp （mod 1）の値によってEPOの 存在確率が変化することによるものと考えられる。し たがって，EPOを構成する場合，特に小さな素数9に 対しp≡1 （mod 1）を満たす素数を法とする素体を 選べば効率が良いことがわかる．電子情報通信学会論文誌 99／8 Vo1． J82−A No，8
﹂①O﹂OΦ一ヒ＝α↑OΦO仁邸一〇う一XφいO診﹇需ΩσρO﹂血
O．028 0．027 0．026 g．e2s O．024 0．023 e．022
§．02壕 O．02
0．019 α創8
0．0唯7
巴コ
岱 峯 田 男
・：＋．；
買 十 昏
十
p：nonsquare（mod 3，5，7，11｝ e p＝1（mod 3） 一 薗．・雰：｛躍亨1隻
許、、轟搬溢
十壱 亀 壱
ロ
《・略・チ・㌦ ・．。，・o o e e e v eee?@．．．． r
@e
4，29497e＋09 4．29497e＋09 4．29497e＋09 4．29497e＋oo
Prime 図2 EPOの存在確率
Fig．2 Probability of existance of ell． cur． with prime
order．
表1p騰1（mod i）である場合の素数位：数となる確率
Ppとの比Table 1 Ratio of probability of existance of ell． cur．
with prime order aRd its avarage probability
Pp
P…1 （modの P≠1 （modの
」雛3 1ユ11 0，889
5 ユ。◎41 O．986
7 1，◎21 0，996
11 LOO8 0，999
4．計算量評価
2．3で示したEPOの構成法の計算量評価を行う．
また，法pの種類によりSEAアルゴリズムでのCase一
：Elkies， Case−Schoofへの分岐確率及びEPOの存在 確率が異なることを示したが，その計算時悶の違いに ついて考察する．
4．1 SEAのアルゴリズムの計算量
本論文では多項式乗算にKaratsuba法を用いる．
このことを考慮すると，最高次数Zの多項式乗算に
要する計算時間は0（12 6（log p）1 6）である． SEAア
ルゴリズムで用いる最大の9をしとする．法pが
160 bitの場合， Lは53となることをSEAアルゴリ ズムの平均値より確かめており，これを1◎gρで表すとし＝e．48 10g pと表すことができる．したがって，
本論文では，L ＝・ O．48 logpと仮定した．
4．2 EPOの構成に要する計算量
本節では，EPOの構成に要する計算量を求める．
EPOの構成に必要な計算量を求めるにあたって，考 慮すべき点は以下のとおりである．
論文／素数位数を有する楕円曲線の構成とその計算量評価 （1）各Zに対してt （mod 1）を求める計算量．
（2）位数が素数1で割り切れる確率几。（の，及び EPOの存在確率」ら．
（3）t（m◎d 9）の確定する確率P藤り．
（4）Schoofのオリジナルアルゴリズムを適用する 最大の素数Ls。h．
（5）SEAアルゴリズムで用いる最大の素数L．
まず，（1）に関して4。1より係数Kを用い，計
算時間をK（12 6 （log p）1 6）とする．〈3＞については，
法pはランダムに与えるものとし確率を1／2とする．
（5）については，Ls。h・5とし，以上より，EPOを 構成する計算量は，
1＝tLII；i3iSlntPav（s）
1・6@2 k2−6 2SleSL （15）
で与えられる．ただし，Σ，nは素数の範囲を動く．
これをSEAアルゴリズムの計算量 K（legp） 6 2 k2 6
2SkSL
（16）
で割るとSEAアルゴリズムに換算した回数が導出で きる。すなわち，EPOを構成する計算量はSEAアル ゴリズムをこの回数分計算した計算時間と等しい、以 降，この國数をSEA相当園数と呼ぶ．この値は，式
（15）， （烹6＞より，
歳Σり→＿｛1一瑞α 2）
2≦s≦五
＋歳蕊1＋争（の
・（ 1 ＋ Pav（Sll 1．t−15r・〉）避｝
（17）
で与えられる．法pが10進数1感けた（50ビット〉
から28けた（85ビット）の範囲で計算結果と式（17）
O篇而
12 11
槍 9 8 7
6 5
一て．
・
ee
Data e e
Theory 璽『 『冒一 e eシ／
シ〆 。。
ン／
ンx e4
50 55 60 65 70 75 80 85 90
Prime （bit）
図3EPOの構成時潤のSEA相当園数
F圭9．3Raもめ◎f c◇mputati◎難a玉も漁￠s f◎r fii｝diRg e歪L cur． witk prime order and SEA algorithm．
表2大きなビットサイズの標数pでのEPO構成時間の SEA相当回数
Irable 2 Ratio of computational times for finding ell．
cur． wkh higk prime order and SEA algo−
rithm．
法P
SEA相轟回数（実測値〉 SBA相当回数（理論値）
160bit
15．87回 17．03回170bit
16．94回 17．93回とを比較して図3に示す．高位ビットに関する比較は 表2に示す．なお，各法pに対してアルゴリズム100 回の平均値をとっている．多少のばらつきはあるが，
式（17）と実測値はほぼ一致しているといえる．
図3より，SEA相当回数は法pのビットサイズに
対し，ほぼ比例の関係があり，法pのサイズが92ビッ トならばSEA相当回数は10．4回，160 bitであれば SEA相当回数は17．0回と十分実用的な値となっている．
4．3 EPOの構成に適した標数p
以下の二つの確率（1）EPOの存在確率
（2）Case−Elkies， Schoofへの分岐確率
は，法pの条件によって変化する．本節では，これら の確率がEPOの構成アルゴリズムにどのような影響 を与えるのかを調べる．2．2で示したように，法pが p≡1 （mod 1）の条件を満たすとき，（1）の確率が 高くなる．3．2で示したように，（V）＝1の条件を満 たすとき，（2）の確率が高くなる磁）．ランダムに楕円
（注2＞：法pに条件を与えることによ珍，楕円暗号の安全性に差を生ず るという研究報告は，筆者らの知る限りではなされていない．この問題 の解明は今後に残された課題の一つである．
＞0⊆ΦコσΦ﹂﹂
350 3eo 250 200 t50 100 50 o g
﹂⁝しi亀茎一羊
k x
㌧／こ黙、
t都【ｾ
x
臼kies Prime（p＝1 mod3，5，7）ゆ一 Atkin Prime 一一一一
壌
㌻一唯、
一y．rAkh
．一 、 メ十，
letrtT一
目
20 3e 4g
X醗e｛sec◎轟d｝se
聾
6g
図4EPOの構成に要する時間の分布
F圭暮．4D三§願も疑も董。登◎f c◎mputation time｛for find圭窺9 e｝1． eur． with prime order．
曲線を選ぶ際EPOでなければ，楕円曲線を選び直す 必要がある．しかしCase−Atkinでは，位数が素数で あるか否かの判定が行えないためCase−Elkies， Sch◎◎f へ多く分岐させた方が効率が良い．また，Case−Elkies へ分岐した場合のみIsogeny Cycleが使用できるため，
これによる効率の向上も可能である．
図4に法p ＝ 260＋7035≡1 （mod 3，5，7）及び p＝26⑪＋7081≠1 （mod 3，5，7）としたときの素 数位数を有する楕円曲線の構成アルゴリズムを2◎0◎
回実行した場合の計算時間の分布を示す．図4より，
法pのタイプでの計算：時間の分布の差が確認できる．
また，平均時間はそれぞれ15．57（s），18．91（s）であり，
法pを変えるだけで約20％の計算時間の短縮が可能
である．
5．む す び
本論文で提案したEPOの効率的な構成法に関し，楕 円曲線の位数分布，EPOの存在確率を導出し， EPO 構成に必要な計算量の評価を行った．その結果，計算 量的に十分実用的であることがわかった。また，法p の条件を選択することにより，計算時間が20％程度短
縮された．
文 献
｛1］ A．」． MeRezes， T． Okarnoto， a！｝d S．A． Vanseene， Re−
ducing e盗ptic curve藍ogar玉thmsも。歪◎菖ariもh田s in a finite field， IEEE Trans． lnfo． Theory， vol，39，
pp．1639−1646， 1993．
［2｝ T．Saも◎k ak（i K。 A臓k圭， FermaもQ疑◎も壼e捻もs a捻（iもhe Polynomial Time Discrete Log Algorithm for Anoma−
lous Elliptic Curves， Public Release Ver．2 （97−10・一
電子情報通信学会論文誌 99／8 Vol， J82−A No．8
︼
3︷ ︼
4
﹇ ︼
5
﹇ ︸
﹇ ︷
6ア達 ユ
8
︹ ︼
︻
9［10］
悶
［121
1綱
岡
岡 岡 闘
118］
21），1997．
R．Schoof， Elliptic curves over finite fields and the c◎mputat沁R◎f square r◎ots m◎（圭P， Mathemaも三cs◎f Computation voL44， no．170， pp．483−494，1985．
R．Schoof， Counting points on elliptic curve over丘．
Rite fields， 」◎uma茎de Th6◎r量e des N◎憩bごes de 8◎r−
deux 7， pp219−254，1995．
N．D。 Elkies， Elliptic and modular curves over丘一 nite fields and re韮ated c◎mputational issues， Arner．
Math． S◎c．／夏P St疑（達， A（達v． Math．， 7，21−76警Prr◎v圭一 dence RI：Amer． Math． Soc．，1998。
F．Morain， Calcul du no㎜bre de points sur une c◎urbe e1引戸P型置eδa籍§UR・COTP§611量：Aspects algor圭癒一 miques， Journal de Th60rie des Nombres de Bordeux 7，pp．255−282，1995．
｛弄豆哲也，小暮 淳，野呂正行，横平和弘， 安全な楕円 曲線暗号パラメーター設計（Sch◎ofアル： ijズム改良〉，
SCIS，98，1998．
」 M．C◎uveignes and F． M◎rain， Schoof，s algorithm and isogeRy cyc茎es，，I Lect秘re N◎乞es泌C◎mpuもe Sc蚤一 ence 877， pp．43−58， Springer−Verlag，1994，
J．一M．Couveignes， L Dewaghe， and F． MQrain，
ls◎g￠総y cycles and旗e Sch◎of−E王kies−Aもk拠alg◎一 rithm， LIX Research Report LIX／RR／96／03，1996．
D．B． Zagier，片山孝次訳，数論入門，岩波書店，1990．
境 隆一，笠原正雄， 楕円懸線の位数分布と素数鍾数を
有する楕円繭線について， S1τA96，1996．三井孝美編， 佐藤の予想， 岩波数学辞典（第3版），205S，
P．550．
H．W． Lenstra，甑， FactOring In毛egers witk￡蟻ひ tic Curves， Annals of Mathematics 126， pp．649−673，
1987．
R．Lerc韮er aRd F． M◎ra圭篤 ℃ountiR菖the fiumber of points on elliptic curve◎ver finite盒e藍（圭s＝Strate−
gies and performances， EUROCRYPT，95， pp．79−
94，1995，
R．Lercier， Alg◎rithmique des courbes elliptiques
ノ
dans les corps finis，，， Th6se， Ecole Polytechnique−LIX，1997。
」．一M．C◎uveignes， L． Dewaghe， and F． M◎rain，
lsogeny cycles and the Schoof−Elkies−Atkin algo−
rithm， LIX Research Report LIX／RR／96／03，1996．
布田裕特境隆一一・・，笠療正雄， Scho◎fのアルゴリズム
に関する基礎的考察， 第19回情報理論とその応幣シン
ポジウム，pp．649−652，1996，堀内啓次，叡B裕一，境 隆一，笠原正雄， 素数位数を 有する楕円蕗線の携成とその計算量評癒について， 第二 回代数曲線とその応用シンポジウム，1998
付 録
1．SEAアルゴリズム
Elkies， Atkinによって改良されたScheofのアル ゴリズムを示す．文献［6］，［14］にこのアルゴリズムを
論文／素数位数を有する楕円曲線の構成とその計算量評価 Schoof， Elkies， Atkinの頭文字をとって， SEAアル ゴリズムとある．ここでもそれにならってそのように
記述する．
1．1準 備
必要となる定義，定理をまとめる．本論文では以下 の式で定義される楕円曲線を用いる．
E；y2＝X3十AX十B （A，BEFp） （A 1）
［定義3］（フロベニウス霞己準同型写像φρ〉
フロベニウス自己準同型写像晦を以下のように定
義する．
￠，：（X， Y）一（XP， YP） （A・2）
B このフロベニウス自己準同型写像は，以下の固有方程 式と呼ばれる方程式を満たす．
ip；一tr（gb，）・ip，＋n（di，） ex O （tr（ip，）EZ）
（A・3）
ここで，tr（φp），n（φp）はそれぞれ，φpのトレース及
び，ノルムであり，n（φp）：pである．簡単のため，以降tr（φp）をtで表すことにする．
［定理4］ （Hasse−Weilの定理）
Eを素体！Fp上定義された楕円懸線とする．このと き，E上のFpに座標成分を有する点の個数 ＃E （Fp）
は
＃E （Fp） ＝p十1−t （A 4）
一2v〈i5 St＄ 2v（P （A・5）
を満たす． ［1
［定義5］（チ不変量）
式（A・1）の楕円曲線に対して，チ不変量を以下の式
で定義する．
4a3
（A・6）o ＝ 1728
4a3 十 27b2
楕円曲線Eのチ不変量を」（E）で表す． ［コ あ不変量に対応する楕円曲線は以下のようになる．
鴫ず一詔3＋3王72島＋2ユ721−5
（A・7）
ただし，p＞3とする．
［定義6］（twistされた楕円曲線）
式（A・1）のような楕円曲tw E／Fpに対して以下の方 程式で定義される楕円曲＊X E をtwistされた楕円曲
線と呼ぶ．
E ：y2＝x3十ac2x十bc3 （A・8）
ただし・
［定理7］twisもされた楕円曲線の欝が有理点の綱
数は，
＃E （pt．）＝p十1十t （A 9）
である． 目 上の定理よil ，1回のSchoofのアルゴリズムを行う
ことで＝：つの楕円曲線の位数を求めることができる．
等分多項式は以下の磁化式により定義される．
［定義8］（等分多項式）
g12n （X， Y） ＝ Wn （Wn＋2WZ−1 一 Wn−2WZ＋i）
／2Y
W，n＋、（X，γ）瓢Ψ曜輔一鴫＋、Ψ。一、
（A・10）
pt．i（X， Y）＝一i， Wo（X， Y） ：O pt，（X， Y）＝1， pt2（X， Y）＝21Y
重、（X，y）＝3X解6蓋X2＋12βX一蓋2
pt4 （X， Y） ＝ 4Y （X6 ＋ sAx ＋ 2gBx3
−sA2x2 一 4ABx 一 sB2 一 A3）
o また，等分多項式を
fn（X）＝Wn（X， Y） （n：odd）
（A・11）
fn（X）＝＝Wn（X， Y）／Y （n：even）
と記述することにより，以下の定理が成立する．
［定理9］P＝（X，y）6E（IFI；）でP￠E［2］の点 に対し
nP ＝OO fn （X） rm：O （A42）
ここでFpは恥の代数閉包，8回は位数がnある
いはその約数である点全体の集合を表し，この集合の 任意の要素のn倍点は無限遠点となる。 9［定理IO｝点P＝（x， y）EE（Fp）をn倍した点
nP（nP≠0）はΨnを用いて，
篇P
と表される．
1．2 アルゴリズムの主要部
（A・13）
［アルゴリズム1］（SEAアルゴリズム）
入力：楕円曲線E／IFp：y2＝X3＋．4X＋B 出力：＃E（Fp）
［Step l｝ε←2，五←1とする．
［Step 2］Φ1（X，」（E））＝Φ（X）＝0のIFp上の解 を求める．その解の個数が2，1のとき，Case−Elkies として，L←Lxごとし， STEP 3日目0のとき，
Case−Atkinとして， STEP 4へ．
［Step 3］Elkiesのアルゴリズムを行う．（Case−
Elkies）
［Step 4］1≦LSchのときは， Schoofのオリジナル アルゴリズムを行う．それ以外は，Atkinのアルゴリ
ズムを行う．（Case−Atkin）
［Step 5］L＞4＞「pであればSTEP 7へ．
［Step 6］Z←（tの次の素数）とし， STEP 2へ．
［Step 7］素tw 1に対するトレースt （mcd 9）のす べてのデータから，Inatch and sortアルゴリズムを 行い，位数＃E（Fp）を求める．終了．
u 1．3 モジュラー多項式
SEAアルゴリズムでは，モジュラー多項式軌（E J）
を用いる．これはSEAアルゴリズムとは独立にあら かじめ求めることができる．一般にはモジュラー多 項式は二つのゴー不変量の関係式を表すが，ここでは，
Atkinによって定義されたもの［6］を表す．こちらのほ うが係数が小さくなる．詳しい特性，求める方法など については文献［6］の2節を参照されたい．本論文で はX。①上とXδ（1）上のモジュラー多項式もともに
Φt（瓦 」）で表す．
1．4 Atkinのアルゴリズム
ここではAもk盈のアルゴリズム［14！について述べ る．Atkinのアルゴリズムではt （mQd 1）の値が数 個の候補値として求まる．
［アルゴリズム2］（Atkinのアルゴリズム）
入力：楕円曲線E／Fp：y2＝X3＋AX＋B，♂
￠i（X，2 （E）） ：￠（X）
出力：t （mod l）の候補値
電子情報通信学会論文誌 99／8 Vol， J82−A No．8
［Step i］ （XP−X，Φ（X））が1でないrを求める．
［Step 2］1の原始r乗根をζとし， t＝［（ζ＋ぐ1＋
2）・p｝i／2 （mod 9）からt （m◎d 9）を求める．
1の原始r乗根はφ（r）個あり，可能な値の個数もそ れと等しい．tがとり得る値の個数はCase・Atkinが 多くなるほど大きくなる．この候補の値から正しい値 を見つけるアルゴリズムはmatch aRcl s◎rtアルゴリ ズムと呼ばれる．Baby steps and Giant stepsのアル ゴリズムと中国人の剰余定理に基づいて構成される．
詳しくは［15】を参照されたい．
1．5 Elkiesのアルゴリズム
Elkiesはフmベニウス写像φpの固有方程式を解く 際に用いる等分多項式fi（X）の代わりにそのファク ター9t（X）を用いることによって，アルゴリズムを高 速化している［5】．以下では91（X）について簡単に説 明する。求める方法など詳しくは文献［6］の3．を参照
されたい．
楕円曲線E ＝： C／（ωIZ＋ω2Z）一に対して，
〈S−1）／2
gi（X）＝fi（X−ge（kwi／1）） （A・14）
k ＝1
とおく．この式は1等分点の一部のX座標を解とし てもつ多項式である．」がElkies素数（Case−Elkies となる素数）であるとき，この式はFp（X）に還元で きる（係数をFpに属するようにできる〉．更に，9等 分点は固有方程式の解（フロベニウス写像の固有値）
に対する解空間に対応する．このことにより，等分多 項式f （X）の代わりにこの91（X）を用いて固有方程 式の解を求めることが可能になる．
等分多項式ゐ（X）の次数が（12 一1）／2であるのに 対し，91（X）のそれは（1−1）／2である．g1（X）を用 いることにより，アルゴリズムの高速化が可能になる．
以下にElkiesのアルゴリズムを示す．
［アルゴリズム6］（E｝kiesのアルゴリズム）
入力：楕円曲線E／Fp：γ2＝X3 ＋ AX ＋B，ε，ゴ（E＞
出力：t （mod l）
［Step 1］9i（X）を求める．
［Step 2］iPpP ＝kPが成立するような1≦k＜ε を求める．そのため以下の式の値を調べる．この値が 1となるときのkがφpの固有値である．
論文／素数位数を有する楕円曲線の構成とその計算量評価 gcd（（XP 一 X）fg（X3 十 AX 十 B）
＋fk−ifk＋i，9i（X）） （k：even）
gcd（（xP 一 x）fk2 十 fh−ifk＋i（x3 十AX十B），gi（X）） （k：odd）
（A・15）
［Step 3］t……（k2＋p）／k （modのを求める．
o MorainらはIsogeny cycle法により， Case−Elkies をより効果的に用いることに成功した．同種写像の連
鎖を考えることにより，t （mod t2）， t （mod t3…）
を求める多項式の次数を抑え，短時間で計算可能にす るものである．これにより，SEAアルゴリズムで用い る最大の素数Lを小さくでき，全体の計算時間が短
縮される．詳しくは文献［8】，［15］，［16］を参照されたい．
1．6 Schoofのオリジナルアルゴリズム
Case−Atkinが多いとき，match and sortアルゴ リズムの計算時間が増大する．そのため可能な限り，
Atkin Caseを減らす必要がある．ここではSchoofの オリジナルアルゴリズムについて説明する．これは，
改良前のSchoofのアルゴリズムである．計算量のオー ダが大きいが1が小さいときは計算時間も小さいため，
Case−Atkinに代わって行う．これにより，match and sortアルゴリズムの計算時間を短縮できる．
以下にそのアルゴリズムを示す．
［アルゴリズム5］（Schoofのオリジナルアルゴリズ
ム）
入力：楕円曲線E／Fp：Y2＝X3＋AX＋B， Z，」（E）
出力：t （mod l）
［Step 1］（φ2十P）（X）＝t tO（X） （mod．飢X））が
成立する1≦t ≦（1−1）／2を求める．［Step 2］（φ2＋p）（Y）ニt φ（y）が成立するとき， t ， しないとき，一t を出力する．終了．
D （平成10年12月28日受付，11年3月23日再受付）
堀内 啓次 （学生員）
平10京都工繊大・工芸・電子情報卒．楕
円曲線暗号などの研究に従事．に従事．
布田 裕一
平8京都工繊大・工芸・電子情報卒．平
10同大大学院工芸科学研究科電子情報工学専攻博士前期課程了．楕円曲線暗号など
の研究に従事．境 隆一 （正員）
平2京都工二大・工芸・電子卒．平4同
大大学院工芸科学研究科電子情報工学専攻
博士前期課程了．平7工芸科学研究科情報・生産科学専攻博士後期課程了．工博．
同年阪電通大講師として現在に至る，主に 暗号と情報セキュリティ，符号理論の研究
金子 昌信
昭58東大・理・数学卒．昭60同大大学 院理学研究科数学専攻修士課程了．昭63 同博士課程了．理博．同年阪大・理・助手．
平2京都工繊大・工芸・助教授．平8九大・
数理学研究科・助教授として現在に至る．
平5〜6ドイツケルン大数学教室客員教授，
ドイツマックスプランク数学研究所客員研究員．整数論，特に ガロア表現，楕円曲線，モジュラー関数，ベルヌーイ数，ゼー タ関数などの研究に従事．平9より日本数学会誌「数学」編集
委員．日本数学会，アメリカ数学会各会員．笠原 正雄 （正員）
昭35阪府大・工・電気卒．昭37阪大大
学院工学研究科通信工学専攻修士課程了．
昭40同博士課程了．工博．同年阪大・工・
助手．昭45同講師．昭47同助教授．昭62 京都工面大・工芸・教授として現在に至る．
昭42〜44米国ベル電話研究所客員研究員。
情報理論，符号理論，ディジタル通信システム，情報セキュリ ティ，音声・画像符号化，技術倫理などの研究に従事．昭60 本会情報理論研究専門委員会委員長．昭60本会評議員．昭61 本会通信グループ副委員長．平1本会情報セキュリティ研究専 門委員会委員長．平7情報理論とその応用学会長．平8本会基 礎・境界ソサイエティ会長．平9本会代数曲線とその応用研究 専門委員会委員長．平10本会基礎・境界ソサイエティ編集長．
IEEE SIT東京支部チェアマン．昭41年度本会稲田賞，昭59
