(57)【特許請求の範囲】
【請求項１】
楕円曲線パラメータの楕円曲線暗号使用における安全性を高速に判定する高速判定装置において、
安全性を判定しようとする上記楕円曲線パラメータを入力する第１の入力手段と、
楕円曲線の有理点群の位数の安全性条件を入力する第２の入力手段と、
予め指定された複数の計算方式について、上記第１の入力手段により上記楕円曲線パラメータが入力される都度、当該入力された楕円曲線パラメータをもとに計算に必要な時間計算量および空間計算量を計算実行前にそれぞれ予測し、予測した時間計算量を相互に比較し、また予測した空間計算量が予め設定した上限値を超えないよう考慮することにより、複数の計算方式の中から、時間計算量および空間計算量の観点から最良な計算方式を選択する選択手段と、
上記選択された計算方式によって、上記入力された楕円曲線パラメータに係る楕円曲線の位数の候補を計算する計算手段と、
上記計算された位数の候補の中から、上記入力された楕円曲線パラメータに係る楕円曲線の真の位数を求め、当該求めた真の位数が上記第２の入力手段により入力されて与えられた安全性条件を満たしているかを判定する判定手段と
を備えたことを特徴とする楕円曲線パラメータの安全性高速判定装置。
【請求項２】
コンピュータを、
安全性を判定しようとする上記楕円曲線パラメータを入力する第１の入力手段と、
楕円曲線の有理点群の位数の安全性条件を入力する第２の入力手段と、
予め指定された複数の計算方式について、上記第１の入力手段により上記楕円曲線パラメータが入力される都度、当該入力された楕円曲線パラメータをもとに計算に必要な時間計算量および空間計算量を計算実行前にそれぞれ予測し、予測した時間計算量を相互に比較し、また予測した空間計算量が予め設定した上限値を超えないよう考慮することにより、複数の計算方式の中から、時間計算量および空間計算量の観点から最良な計算方式を選択する選択手段と、
上記選択された計算方式によって、上記入力された楕円曲線パラメータに係る楕円曲線の位数の候補を計算する計算手段と、
上記計算された位数の候補の中から、上記入力された楕円曲線パラメータに係る楕円曲線の真の位数を求め、当該求めた真の位数が上記第２の入力手段により入力されて与えられた安全性条件を満たしているかを判定する判定手段と
して機能させるためのプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線上の離散対数問題として安全なパラメータを高速に判定する高速強度判定装置に関するものである。近年のコンピュータセキュリティの重要性の増大に伴い、暗号技術の更なる進歩が要求されている。次世代暗号として最も期待されているものの１つとして、楕円曲線を利用した暗号や鍵配送があるが、それらの安全性を判定するためには、基礎となる楕円曲線の性質、特にその有理点のなす群の位数を具体的に求め、その位数に関するいくつかの安全性の判定条件を調べる必要があり、これを高速に行うことが望まれている。
【０００２】
【従来の技術】
従来の安全な離散問題を構成する楕円曲線のパラメータを決定する方式は、楕円曲線のパラメータをランダムに生成し、そのパラメータを持つ楕円曲線について安全性を確かめる方法と、現在知られている安全基準を満たすようにパラメータ自身を計算する方法の２種類がある。前者は楕円曲線の有理点のなす群の位数を計算し、その値に対して安全性を判定する方法であり、具体的には位数計算法としてスクーフ法が使われる。後者は予め、安全と判定される位数を生成し、その位数を持つように楕円曲線パラメータを計算する方法であり、ＣＭ法(Complex Multiplication:虚数乗算法）と呼ばれる方式がそのパラメータ計算に使われる。従来技術に関する文献として下記のものがある。
【０００３】
1．Atkin.ElkiesらによるSchoofアルゴリズム改良の実装について:信学技報Vol.97、No.461、p1〜p12(電子情報通信学会技術研究報告、１９９７年１２月１９日発行、社団法人電子情報通信学会発刊)
2.数理アルゴリズムとその応用:情報処理Vol.34、No.2、p180〜P188(1993.2発行、社団法人情報処理学会発刊)
3.Schoof's algorithm and isogeny cycles:Lecture Notes in Computer Science、877、p43〜58(May 1994)
4.Construting Elliptic Curves with Given Group Order over Large Finite Fields:Lecture Notes in Computer Science、877、p250〜263(May 1994)
5.Counting the number of points on elliptic curves finite fuilds、strategies and performances:Lecture Notes in Computer Science、921、p79〜94(May 1995)
6.Counting Points on elliptic curves over finite fiilds:Journal de The'orie des Nombres:de Bordeaux 7(1995),219-254
【０００４】
【発明が解決しようとする課題】
しかし、後者のＣＭ法では、高速に計算できる位数が偏っており、結果として生成されるパラメータは数学的に偏った性質を持っている。そこで、現在知られている位数に関する安全基準を満たしていても、将来に渡っても安全性であるかどうか問題が残る。
【０００５】
一方、前者のスクーフ法は、最も安全なパラメータを生成できるが、生成時間がかかるという欠点がある。
従って、楕円曲線として最も安全な離散対数問題を与えるパラメータを生成しようとするとスクーフ法を使うこととなり、非常に時間がかかってしまう。逆に、高速に生成しようとしてＣＭ法を使うと、安全性に疑問が残るパラメータしか生成できないという問題が生じている。
【０００６】
本発明は、これらの問題を解決するため、楕円曲線上の離散問題としてのパラメータの安全性について、スクーフ法に沿って最適な計算方式を選択し計算を行い、楕円曲線のパラメータの安全性を高速に判定することを目的としている。
【０００７】
【課題を解決するための手段】
図１を参照して課題を解決するための手段を説明する。
図１において、処理装置１１は、プログラムに従い各種処理を行うものであって、ここでは、楕円パラメータ入力手段１、位数条件入力手段２、計算方式選択手段３、計算手段４、および位数安全性判定手段５などから構成されるものである。
【０００８】
楕円パラメータ入力手段１は、調べたい楕円曲線のパラメータを入力するものである。
位数条件入力手段２は、楕円曲線の有理点群の位数に関する条件（位数条件：安全な離散対数問題を保証する位数の条件）を入力するものである。
【０００９】
計算方式選択手段３は、入力された楕円曲線のパラメータおよび位数条件をもとに最適な計算方式を選択するものである。
計算手段４は、選択された計算方式（計算方式Ａ、Ｂ、Ｙ、Ｚ）に従って位数に関する情報を計算するものである。
【００１０】
位数安全性判定手段５は、計算手段４によって計算された位数に関する情報について、安全性を判定するものである。
次に、動作を説明する。
【００１１】
楕円パラメータ入力手段１が安全性を判定しようとする楕円曲線のパラメータを入力し、位数条件入力手段２が楕円曲線の有理点群の位数条件を入力し、計算方式選択手段３が入力されたパラメータおよび位数条件をもとに、次に実行する位数の計算の計算資源の最良な計算方式を選択し、計算手段４が選択された計算方式によって位数に関する情報を計算し、位数安全性判定手段５が計算された位数に関する情報について、安全性を判定するようにしている。
【００１２】
この際、計算方式選択手段３が最良の計算方式を選択するに必要な情報を事前に計算して保持し、選択時に使用するようにしている。
従って、楕円曲線上の離散問題としてのパラメータの安全性について、スクーフ法に沿って最適な計算方式を選択し計算を実行することにより、楕円曲線のパラメータの安全性を高速に判定することが可能となる。
【００１３】
【発明の実施の形態】
次に、図２から図５を用いて本発明の実施の形態および動作を順次詳細に説明する。
【００１４】
図２および図３は、本発明の動作説明フローチャートを示す。これらは、図１の構成の動作を詳細に説明するフローチャートである。
図２において、Ｓ１は、パラメータを入力する。これは、楕円曲線暗号パラメータとして、
・係数：ａ1、ａ2、ａ3、ａ4、ａ6
・基礎となる有限体の情報：ＧＦ（ｑ）（元の係数がｑ個の有限体であるこ
とを表す表記）
を入力として受け付ける。ここで、楕円曲線は、
ｙ2＋ａ1ｘｙ＋ａ3ｙ＝ｘ3＋ａ2ｘ2＋ａ4ｘ＋ａ6・・・・・・（式１）
で与える。その係数［ａ1、ａ2、ａ3、ａ4、ａ6］をパラメータと呼ぶ。楕円曲線が定義される有限体ＧＦ（ｑ）の情報は、
（１）  有限体の位数ｑが素数の場合には、素数ｑ
（２）  素数巾位数ｑ＝ｐsの場合には、素数ｐ（標数と呼ぶ）とＧＦ（ｐ）
からＧＦ（ｑ）を定義する多項式（１つまたは複数）の組み
とする。
【００１５】
Ｓ２は、位数条件を入力する。例えば楕円曲線有理点群の位数条件として
・位数が素数である
を入力する。
【００１６】
Ｓ３は、ＭｕｌＭＡＸ、ＳｃｈｏｏｆＭＡＸの計算を行う。
Ｓ４は、４√ｑ＜Πｌikiであるか判定する。これらＳ３、Ｓ４は、
・４√ｑ／（それまでの位数に関する情報を得た素数ｌまたは素数の巾ｌkの積）、nextL、isogL、SchoofMAX、MulMAX、modular equationの有無などの情報をもとに、次に行う予定の各計算方式の計算資源（計算時間、計算空間）を計算量解析に基づいて予測し、その中から「最良」の計算方式を選択する（後述する図５参照）。
【００１７】
ここで、位数に関する情報は位数をOrderとした場合、各、小さな素数ｌについて、
（１）  Order mod l、または
（２）  Order mol lkの候補（取り得る値）、または
（３）  既にOrder mod lK、０＜ｋが求まっているｌに対してOrder mod lk+1のいずれかである。４√ｑ／（それまでの位数に関する情報を得た素数ｌまたは素数の巾ｌkの積）が１より小さくなった時点で、小さな素数ｌ1、ｌ2・・・に対するこれらの情報をまとめて
Order mod l1k1、Order mod l2k2、・・・Order mod lsks
の値を各々の候補から選び、中国人剰余定理を用いて位数の候補を生成し、真の位数であるかを適当に選んだ楕円上の有理点Ｐを用いて判定して最終的に位数を計算する。以下では、この判定を「試しステップ」と呼ぶことにする。
【００１８】
上記の各情報については、
（１）はSchoofオリジナル方式、またはElkies方式により求まる。
（２）はAtkin方式、Virtual Atkin、またはVirtual Elkies方式により求まる。
【００１９】
（３）はisogeny cycle方式を使い求まる。
nextLはまだ使われていない素数で一番小さいもの、isogLは既にOrd mod lkを計算した素数ｌでOrd mod lk+1の計算が可能なものの全体、SchoofMAXはSchool法を適用する最大の素数の大きさ、MulMAXは試しステップにおける候補の個数の上限値を表し、これらの情報より次に計算を行う方式を以下より選択する。
【００２０】
・Schoofオリジナル方式
・Alkin-Elkies方式
・Elkies方式のみ
・Alkin方式のみ
・isogeny cycle方式
・virtual Atkin方式
・virtual isogeny方式
ここで、「Atkin-Elkies方式」、「Elkies方式のみ」、「Atkin方式のみ」では、まず、modular polynomailと呼ばれる多項式を因数分解し、その情報よりAtkin方式を実行するか、Elkies方式を実行するかを決める。「Elkies方式のみ」は、決してAtkin方式を選択しないことを、「Atkin方式のみ」は決してElkes方式を選択しないことを表す。「virtual Atkin方式」は計算せずに、{0,1,・・・l-1}をmod l候補とするもので、「virtual isogeny方式」は位数がmod lkでｔであることが分っている場合に、mod lk+sの値を、isogeny cycleを計算せずに、{t,t+li，t+2lk，・・・t+(lS−１）lk｝をmod lk+sの候補とするものである。  MulMAX、SchoofMAXは有限体ＧＦ（ｑ）の位数ｑの大きさにより計算される。MulMAXにおいては、既に蓄積された候補の個数がMulMAXを越えた場合には、候補が増えないような情報のみを取り扱うことになり、「Elkies方式のみ」を採用したり、計算量的に有効な候補のみの選択が行われる。SchoofMAXでは、それ以下の極めて小さい素数にのみ、Schoofオリジナル方式を行う(なぜなら、極めて小さい素数の場合のみSchoofオリジナル方式は効率良く計算できる)。一方、nextL、isogLは毎回更新されていく情報である。
【００２１】
Ｓ５は、計算方式の選択を行う。これは、Ｓ３、Ｓ４で最良の計算方式と選択された計算方式を選択する。
Ｓ６は、Ｓ５で選択された最良の計算方式（Ｓ７ないしＳ１１の計算方式）を用いて後述する図５に示すように計算する。
【００２２】
ここで、
Ｓ７のＳ：Schoofオリジナル方式
Ｓ８のＡＥ：Alkin-Elkes方式
Ｓ９のＩ：isogeny cycle方式
Ｓ１０のＶＡ：virtual Atkin方式
Ｓ１１のＶＩ：virtual isogeny方式
の計算方式をそれぞれ表す。
【００２３】
Ｓ１２は、候補の中から位数を決定する。
図３のＳ１３は、条件に素数判定があるか判別する。ＹＥＳの場合には、Ｓ１４、Ｓ１５あるいはＳ６をいずれか１つ以上を行う。
【００２４】
Ｓ１４は、Miller-Rabin法により素数判定を行う。
Ｓ１５は、Jacobi和法により素数判定を行う。
Ｓ１６は、小さな素数により試し割りを行う。例えば１０００００以下の素数で試し割りを行い、割り切れないときに素数と判定する。
【００２５】
Ｓ１７は、その他の条件の判定を行う。例えば「有限体の位数と異なる方が良い」という条件の判定などを行う。
Ｓ１８は、安全なパラメータ「ａ1,ａ2,ａ3,ａ4,ａ6」の決定を行う。
【００２６】
以上の手順により、図１の構成のもとで入力されたパラメータおよび位数条件をもとに位数計算に最適な計算方式を選択して計算し、その結果が素数でないことを判定などし、安全なパラメータ「ａ1,ａ2,ａ3,ａ4,ａ6」の決定を高速に行うことが可能となる。以下具体例について詳細に説明する。
【００２７】
図４、図５および図６を用いて具体例について詳細に説明する。
［１］  パラメータ入力（図２のＳ１）：［ａ1,ａ2,ａ3,ａ4,ａ6］と大きな有限体の定義を入力する。有限体の位数が大きな素数ｑの場合にはｑがそのまま定義として入力する。有限体が小さな素数ｐを位数とする別の有限体の拡大である場合には、ｐと拡大を与える多項式（複数でも可）を定義として入力する。
【００２８】
尚、ｐが大きな素数の場合には、ａ1＝ａ2＝ａ3＝０でよい。ｐ＝２の場合には、ａ1＝１、ａ3＝ａ4＝０でよい。
例として、［ａ1,ａ2,ａ3,ａ4,ａ6］＝［０，０，０，０，０，６］
ｑ＝２155＋１５
とする（有限体はＧＦ（ｑ）で書き表される）。楕円曲線の式は以下となる。
【００２９】
ｙ2＝ｘ3＋ｘ＋６
［２］  位数条件入力（図２のＳ２）：離散対数問題として安全になるための楕円曲線の有理点のなす群の位数に関する条件を入力する。例として
・条件１：（楕円曲線の有理点のなす群の位数）が素数である。但し２以上
・条件２：（楕円曲線の有理点のなす群の位数）が（定義する有限体の位数のある巾−１）を割り切るならば、その巾は所定値より大きい。例えば、１００００以上
・条件３：（楕円曲線の有理点のなす群の位数）が（定義する有限体の位数）に等しくない。
【００３０】
ここで、条件１は、一般離散対数問題として求められる条件である。位数は、図４の条件１の説明に記載したように、楕円曲線上の黒丸の有理点の総数ＧＦ（ｑ）に無限遠点を加えた総和Ｏである。素数は、１以外では自分自身の数以外で割り切れない数である。
【００３１】
条件２は、Menezes-Okamoto-Vanstone帰着と呼ばれる楕円離散対数問題への解法に対して安全であるための条件である。以下ではＭＯＶ判定と呼ぶ。この条件２の意味は、図４の条件２の説明に記載したように、（ｑｒ−１）をＯで割ると余りがゼロとなり、その値ｒが所定値（例えば１００００）より大きいことを表す。
【００３２】
条件３は、Smart-Satoh-Arakiの攻撃法に対して安全であるための条件である。以下ではＳＳＡ判定と呼ぶ。この条件３の意味は、図４の条件３の説明に記載したように、Ｏ≠ｑである（位数の数Ｏがｑに等しくないことを表す）。
【００３３】
〔３〕  計算方式選択（図２のＳ３ないしＳ５）：
〔３−１〕  MulMAX, SchoofMAXの計算（図２のＳ３）：
入力されたパラメータより、MulMAXを組み合わせ上限テーブルから、SchoofMAXをスクーフ法上限テーブルから計算する。
【００３４】
○組み合わせ上限テーブル(実験値)
楕円曲線の有理点のなす群の位数は最後の計算局面では、その候補がいくつか生成され、その中から決める。この候補の個数の上限値をMulMAXとして設定する。
【００３５】
例として、有限体の位数のビット長log2（ｑ）を計算し、その値に６／１６０を掛けた値６log2(q)/160を１０のベキとする値、即ち、
MulMAX=10exp((6 log2(q))/160)
となる。また、理論値より関数を求めることもできる。この場合、計算量を解析して行う。
【００３６】
○スクーフ上限テーブル（実験値）：
どこまで、小さな素数ｌを使ったスクーフ法を行うかどうかを決める。この素数の上限値をSchoofMAXとして設定する。
【００３７】
例として、階段関数により計算する。有限体の位数のビット長log2(q)を計算し、その値が
・160未満ならばSchoof法は行わない。
【００３８】
・160以上240未満ならば5以下の素数について行う。
・240以上300未満ならば7以下の素数について行う。
また、理論値により関数を決めることもできる。この場合、計算量を解析して行う。
【００３９】
［３−２］  計算方式の選択（図２のＳ５）：
楕円曲線の有理点のなす群の位数の情報を得るために次に行う計算の方式を選択する。この選択は、予想される計算量から、その中で最良のものを選択する。
【００４０】
（１）  Schoof方式
（２）  Atkin-Elkes方式(Atkinのみ、Elkiesのみも含む)
（３）  Isogeny cycle方式
（４）  Virtual Atkin方式
（５）  Virtual isogeny cycle方式
例として、各計算方式において、計算時間が最も大きな部分の計算量を計算して比較する。
【００４１】
（１）Schoof方式では、素数ｌに対して、その予想計算量（時間）を
（ｌ2−１）2／４
とする。
【００４２】
（２）Atkin-Elkes方式では、素数ｌに対して、その予想計算量（時間）を
（ｌ＋１）2
とする。
【００４３】
（３）Isogeny cycle方式では、素数ｌに対して、既にElkies方式で計算済みであるが、その時の結果の副産物として、Isogeny cycle方式で計算される多項式の次数が予測される。この次数をＵとすると、
(l-1)/2≦ U ≦l(l-1)/2
である。この時、予想計算量(時間)を
U2＋(l-1)2／４
とする。
【００４４】
（４）Virtual Atkin方式では、次の素数ｌがAtkin方式で計算されると考え、この場合の候補を全ての値、即ち、O mod l,1 mod l,・・・,l-1 mod lが全て起き得るとする(実際には計算しない)。今までに素数l1，・・・,lkksまで情報が得られたとして、
４√ｑ＞Πi=1s ｌiKi
であるが、次の素数ｌa+1＝ｌを持ってくると
４√ｑ＜（Πi=1s lIki）×ｌ
であり、可能な候補の組み合わせの個数がMulMAX値を越えないならば、計算量0とする。
【００４５】
（５）Virtual isogeny cycle方式は、（４）と同様に、Isogeny cycleを計算せずに、全ての可能性を候補とする。即ち、mod lkまで計算された素数ｌに対して、その値をｔとすれば、（t mod lkがわかっている）、t mod lk+S,t+lk mod lK+c,・・・,t+(ls-1)lk mod lk+cが全て可能とみなす。ここで、Ｃは１以上のある整数である。これを行う条件は、（４）と同様で、ｌ＝ｌiとして、
４√ｑ＞Πi=1S liKi
であるが、
４√ｑ＜（Πj=1sljkj）×lic
であり、可能な候補の組み合わせの個数がMulMAX値を越えないならば計算量0とする。
【００４６】
［４］  計算方式の選択の流れ：
q=2155+15, y2 = x3+x+6に対して
○素数2が選択され、mod 2の値が計算される。l1=2,k1=1とおく。
【００４７】
この場合は、Atkin-Elkies方式で計算される。
○次に、素数3が選択される。この時、3次のmodular polynominalと言われる多項式(以下M多項式と呼ぶ)
x4+36x3+270x2+23959043234932834724650571028135787207474304740x+729が計算され、このM多項式の因数分解により、根がＧＦ（ｑ）上に存在しないことがわかる。これより、Atkin方式が選択される。
【００４８】
計算の結果、位数のmod 3での値の候補が1または2であることが分かる。l2=3,k2=1とおく。
○次に、素数l=5が選択される。
【００４９】
素数3の時と同様に5次のmodular polynominalと呼ばれる多項式が計算され、
x6+30x5+315x4+1300x3+1575x2+23959043234932834724650571028135787207474304734x+125
となる。この多項式の因数分解により、根がＧＦ（ｑ）上に２個存在することがわかり、Elkies方式が選択される。
【００５０】
計算の結果、mod 5の値が3であることが分かる。
副産物として、次のisogeny cycle方式を行う場合の計算に使われる多項式の次数が5であることも計算される。l3=5,k3=1とおく。
【００５１】
○次の選択は、素数7でのAtkin-Elkies方式か素数5でのisogeny cycle方式であるか、計算量予測により、素数5でのisogeny cycle方式が選択される。
計算により、位数のmod 25での値が3であることが分かる。k3=2に変更される。
【００５２】
○次の選択は、素数7でのAtkin-Elkies方式になる。
○以下同様に計算を行い、素数53でAtkin-Elkies方式が採用され、53次のmodular polynominalの素因数分解より、Atkin方式が採用され、位数のmod 53の候補が計算される(この場合には6通りの可能性がある)。l16=53,k16=53とおく(53は素数2から数えて16番目の素数である)。
【００５３】
ここで、
4√q > Πi=116liki
であるが、
4√q >  ４（ Πi=116liki）
であることが判定される。また、候補の個数も４倍しても、MulMAX方式を越えないことも計算される。
【００５４】
○そこで、Virtual isogney cycle方式が選択され、l1=2でのベキk1=1がk1=3に変更され、mod 23での位数の候補が選択される。位数のmod 8での候補は、1,3,5,7である。
【００５５】
○最後に全ての候補に対して真の位数かどうかを判定する。候補の総数は13824個であり、結果として位数
45671926166590716193864980252764298780908515903
を得る。
【００５６】
［５］  安全性条件判定（図３のＳ１３からＳ１７）：
計算された位数に対して
（１）  素数判定
（２）  ＭＯＶ判定
（３）  ＳＳＡ判定
を行う。
【００５７】
○素数判定：素数判定としては、確率的ではあるが高速なMiller-Rabin法や確定的に判定を行うJacobi和法等がある。また、所定値より小さい素数での試し割り法で、小さい因子がある場合に高速に判定できる。例では、素数判定の結果
6977×6546069394666864869408768848038454748589439
なる2つの素数の積であることが分かり、条件を満たさないことが判明する。
【００５８】
○ＭＯＶ判定：これは、所定値までq mod位数のベキを試算して1になるかどうかを見ることにより判定する。
○ＳＳＡ判定：位数とｑを比較して判定する。
【００５９】
以上説明した例について、経過を表に分かり易くまとめると図５に示すようになり、その候補の結果例が図６に示すようになり、１３８２４通りの位数の候補の生成が実現されたこととなる。
【００６０】
［６］  他の例として、位数が素数となる例について、既述した[１］ないし［５］の手順により算出すると以下のように得られた。
y2 = x3+a4x+a6
GF(q)
a4= 817106656378579887843884849507167715215637613316
a6= 398915859521365555610945639970390500023603500497
q = 2033619312452117457114630623436704499052634420623
この時、楕円曲線の有理点のなす群の位数は、
2033619312452117457114629411330527591276760286229
となり、素数と判定された。条件2、条件3も計算により満たされることが判明した(尚、条件1の素数である判定については、計算方式選択手段において、「位数を小さな素数で割った余りが0」の情報を得た時点で全ての計算を終了するようにしてもよい)。
【００６１】
図５は、本発明の計算実行例を示す。これは、既述した［１］ないし［４］で説明した例について素数２、３、５、７・・・５３についていずれの方式で計算したかを示したものである。○は１つのみの場合あるいは複数の候補があったときに選択した１つを示す。◎は候補が複数ある場合を示す。ここで、左欄の略号
Ｓ：Schoofオリジナル方式
ＡＥ：Atkin-Elkies方式
Ｉ：isogeny cycle方式
ＶＡ：virtual Atkin方式
ＶＩ：virtual isogeny方式
の計算方式をそれぞれ表す。
【００６２】
上段は素数を示し左から右方向に計算した順序を示す。
図６は、本発明の候補の結果例を示す。これは、既述した［１］ないし［４］の例ついて、図５の計算実行例に示す計算方式により求めた候補の結果を示す。左側の欄は素数または素数べきを示し、中央の欄は位数の候補を示し、右側の欄は方式（計算方式、略号は図５の場合と同様）を示す。この例では、位数の候補の数の組み合わせとして、図示したように、１３，８２４通りの位数の候補が生成された。
【００６３】
他の実施形態として、ＧＦ（２n）の場合には、Atkin-Morain方式に代わり、Conveignes方式やLercier方式を使ってもよい。
また、modular多項式の代わりに、canonical modular多項式を使ってもよい。
【００６４】
【発明の効果】
以上説明したように、本発明によれば、パラメータを入力する入力手段と、楕円曲線の有理点群の位数条件を入力する入力手段と、入力されたパラメータおよび位数条件をもとに次に実行する位数の計算の計算資源の最良な計算方式を選択する選択手段と、選択された計算方式によって位数に関する情報を計算する計算手段とを設ける構成を採用しているため、楕円曲線上の離散問題としてのパラメータの安先性について、スクーフ法に沿って最適な計算方式を選択し計算を高速実行し、楕円曲線のパラメータの安全性を高速に判定できる。例えば既述した〔１〕ないし〔４〕で説明した例では、６倍以上の高速化を達成できた（旧方式では３８９．１秒であったものが、本発明では５８．３５秒に６分の１に短縮できた）。
【図面の簡単な説明】
【図１】本発明のシステム構成図である。
【図２】本発明の動作説明フローチャート（その１）である。
【図３】本発明の動作説明フローチャート（その２）である。
【図４】本発明の説明図である。
【図５】本発明の計算実行例である。
【図６】本発明の候補の結果例である。
【符号の説明】
１：楕円パラメータ入力手段
２：位数条件入力手段
３：計算方式選択手段
４：計算手段
５：位数安全性判定手段
１１：処理装置
【図１】
0003990793.tif 000002
【図２】
0003990793.tif 000003
【図３】
0003990793.tif 000004
【図４】
0003990793.tif 000005
【図５】
0003990793.tif 000006
【図６】
0003990793.tif 000007