"コンピュータが実行する楕円曲線生成方法であって、Brezing-Weng法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Brezing-Weng法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Brezing-Weng法に基づいて楕円曲線を生成することを特徴とする楕円曲線生成方法。前記判別式を算出する処理は、入力値kの倍数nのうち、オイラー関数φnの値が所定値以下となるnを選択し、円分体Qζnに含まれる虚2次体Kの定義多項式fx=x2axbを算出し、fxの係数a及びbから4b-a2の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする請求項1に記載の楕円曲線生成方法。ただし、ζkは、1の原始k乗根であり、fxは、K=Q[x]/fxとなる多項式である。Brezing-Weng法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Brezing-Weng法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する算出部と、前記算出部により算出された判別式と前記入力値とを用いて、Brezing-Weng法に基づいて楕円曲線を生成する生成部とを備えたことを特徴とする楕円曲線生成装置。コンピュータに、Brezing-Weng法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Brezing-Weng法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Brezing-Weng法に基づいて楕円曲線を生成する処理を実行させることを特徴とする楕円曲線生成プログラム。しかしながら、上記従来技術では、楕円曲線を効率良く生成することが難しいという問題があった。例えば、BW法で生成される整数の組t、r、qのそれぞれの値は、入力値である埋め込み次数k及び判別式Dによって変化するので、ペアリング暗号に適したサイズにならない場合があった。特に、部分群位数rの値はペアリング暗号の安全性に関わるパラメータであり、この部分群位数rが大きくなれば安全性は高まるが、あまりに大きな値になると、暗号化、復号化にかかる処理負荷が大きくなる。ここで、判別式Dが大きくなると部分群位数rも大きくなりやすいため、判別式Dには1を入力することが一般的である。そして、判別式Dに1を入力しても部分群位数rが適したサイズにならない場合には、部分群位数rが適したサイズになるまで埋め込み次数kに入力する値を変えていくことになる。しかし、埋め込み次数kはペアリング暗号の安全性に関わるパラメータであるため、現代のコンピュータの処理性能を考慮すると、埋め込み次数kとしては2~6程度が推奨される。このため、従来技術では、埋め込み次数k及び判別式Dとして入力される値の組合せは限られており、楕円曲線を効率良く生成することはできなかった。開示の技術は、上記に鑑みてなされたものであって、楕円曲線を効率良く生成することができる楕円曲線生成方法、楕円曲線生成装置及び楕円曲線生成プログラムを提供することを目的とする。本願の開示する楕円曲線生成方法は、Brezing-Weng法における埋め込み次数を入力値として受け付ける。また、楕円曲線生成方法は、受け付けた入力値に対して、Brezing-Weng法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する。また、楕円曲線生成方法は、前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Brezing-Weng法に基づいて楕円曲線を生成する。本願の開示する技術の一つの態様によれば、楕円曲線を効率良く生成することができるという効果を奏する。以下に、本願の開示する楕円曲線生成方法、楕円曲線生成装置及び楕円曲線生成プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。実施例1に係る楕円曲線生成装置の機能構成の一例について説明する。図1は、実施例1に係る楕円曲線生成装置の機能構成を示すブロック図である。図1に示すように、この楕円曲線生成装置100は、記憶部110と、制御部120とを有する。記憶部110は、算出データ111を有する。記憶部110は、例えば、RAMRandomAccessMemory、ROMReadOnlyMemory、フラッシュメモリFlashMemoryなどの半導体メモリ素子、ハードディスクや光ディスクなどの記憶装置に対応する。算出データ111は、後述する算出部122により算出された算出結果を示すデータである。例えば、算出データ111は、入力値である埋め込み次数kと所定値mと、算出結果である判別式Dとを対応づけたデータである。具体的には、算出データ111は、例えば、埋め込み次数k=3と、所定値m=8と、判別式D=1,3,5,15とを対応づけたデータである。つまり、算出データ111は、埋め込み次数k=3及び所定値m=8が入力値として算出部122に入力された場合に、4つの判別式D=1,3,5,15が算出されたことを示す。制御部120は、受付部121と、算出部122と、生成部123と、出力部124とを有する。制御部120の機能は、例えば、ASICApplicationSpecificIntegratedCircuitやFPGAFieldProgrammableGateArrayなどの集積回路により実現することができる。また、制御部120の機能は、例えば、CPUCentralProcessingUnitが所定のプログラムを実行することで実現することができる。受付部121は、各種情報の入力を受け付ける。例えば、受付部121は、埋め込み次数kと所定値mとを入力値として受け付ける。受付部121は、受け付けた入力値を算出部122に出力する。算出部122は、受付部121によって受け付けた埋め込み次数kと所定値mとを用いて、BW法における部分群位数多項式rxの次数が所定値m以下となる判別式Dを、埋め込み次数kと判別式Dに係る円分体の拡大次数に基づいて算出する。ここで、部分群位数多項式rxの次数が所定値m以下となる判別式Dを算出するのは、部分群位数rがペアリング暗号の安全性に関わるパラメータであり、選択できる値には制限があるからである。つまり、多項式rxの次数が大きい場合には、部分群位数rの値が大きくなってしまい、ペアリング暗号に適したサイズの部分群位数rを得ることができない。また、埋め込み次数kもペアリング暗号の安全性に関わるパラメータであり、選択できる値には制限がある。これに対して、判別式Dには、このような制限が無い。このため、発明者らは、多項式rxの次数に上限値を設定することで、ペアリング暗号に適したサイズの部分群位数rを出力する判別式Dを埋め込み次数kから求めることができ、楕円曲線を効率良く生成することができるという着想に至った。例えば、算出部122は、埋め込み次数kの倍数nのうち、オイラー関数φnの値が所定値m以下となる整数nを選択する。算出部122は、円分体Qζnに含まれる虚2次体Kの定義多項式fx=x2axbの係数a及びbを算出する。算出部122は、fxの係数a及びbから4b-a2の値を算出し、算出した値の非平方因子を判別式Dとして算出する。なお、ζkは、1の原始k乗根である。また、nは埋め込み次数kの倍数であるので、円分体Qζnはζkを含む。また、fxは、K=Q[x]/fxを満たす多項式である。以下において、算出部122の処理を詳細に説明する。ここでは、一例として、埋め込み次数k=3かつ所定値m=8の場合を説明する。なお、埋め込み次数k及び所定値mの値については、この例示に限定されるものではなく、楕円曲線生成装置100を利用する者が任意の値に設定して良い。まず、算出部122が整数nを選択する処理について説明する。例えば、算出部122は、埋め込み次数k=3の倍数n=3,6,9,12,15を求める。そして、算出部122は、求めた倍数nについて、下記の式1を用いてφnを算出する。なお、式1において、倍数nは正整数である。また、p1,p2piは、倍数nの相違なる全ての素因子である。φn=n1-1/p11-1/p21-1/pi1例えば、算出部122は、式1を用いてφ3=2,φ6=2,φ9=6,φ12=4,φ15=8を算出する。そして、算出部122は、φn≦mとなる倍数nを選択する。つまり、埋め込み次数k=3かつ所定値m=8の場合には、算出部122は、n=3,6,9,12,15,18,24,30を選択する。なお、以下では、説明の都合上、倍数n=15の場合を説明するが、算出部122は、選択した他の倍数nについても同様に処理するものとする。また、算出部122が倍数nを選択する方法は、上記の方法に限定されるものではない。例えば、算出部122は、φn≦mとなる値を算出した後に、算出した値のうち埋め込み次数kの倍数となる倍数nを選択するようにしても良い。具体的には、所定値m=8の場合には、算出部122は、φn≦8となる値として、2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,24,30を算出する。そして、算出部122は、φn≦8となる値のうち、埋め込み次数k=3の倍数nとして、3,6,9,12,15,18,24,30を選択する。このように、算出部122は、埋め込み次数kの倍数nのうち、オイラー関数φnの値が所定値m以下となる整数nを選択する。例えば、埋め込み次数k=3かつ所定値m=8の場合には、算出部122は、整数nとして、3,6,9,12,15,18,24,30を選択する。また、算出部122が、円分体Qζnに含まれる虚2次体Kの定義多項式fx=x2axbの係数a及びbを算出する処理について説明する。例えば、算出部122は、倍数n=15の場合には、円分体Qζ15に含まれる虚2次体Kの定義多項式fx=x2axbの係数a及びbを算出する。ここで、ガロア理論より円分体Qζnに含まれる虚2次体Kは群Z/nZの指数2の部分群に対応することが知られている。よって、算出部122は、群Z/nZを生成し、生成した群Z/nZの指数2の部分群を生成することで、虚2次体Kを生成することができる。以下で、虚2次体Kの定義多項式fx=x2axbの係数a及びbの具体的な算出方法を説明する。例えば、整数n=15を選択した場合を説明する。円分体Qζ15の次数は、φnに等しいので、φ15=8である。群Z/nZは、1~nの整数であり、かつ、nの素因数で割り切れる数を除外したものである。よって、算出部122は、1~15の整数うち、15の素因数3及び5で割り切れる数を除外して、群Z/15Z={1,2,4,7,8,11,13,14}を生成する。そして、算出部122は、生成した群Z/nZの指数2の部分群を生成する。ここで、群Z/nZの指数2の部分群を生成する処理について説明する。算出部122は、群Z/nZから元gを一つ選択し、選択した元gに元gを乗算する。算出した値が倍数nより小さい場合には、算出部122は、算出した値をそのまま取得する。一方、算出した値が倍数nより大きい場合には、算出部122は、算出した値が倍数nより小さくなるまで算出した値から倍数nを減算し、減算した値を取得する。算出部122は、取得した値に対してさらに元gを乗算し、算出した値を取得する。算出部122は、取得した値が1になるまで、取得した値に元gを乗算する処理を繰り返す。取得した値が1になった場合には、算出部122は、取得した値と選択した元gとを新たな元として部分群<g>を生成する。また、算出部122は、群Z/nZに含まれる他の元についても同様に部分群を生成する。例えば、群Z/15Zについて、算出部122が元g=2を選択した場合を説明する。算出部122は、2×2=4を算出する。4は15より小さいので、算出部122は、4を取得する。算出部122は、4×2=8を算出する。8は15より小さいので、算出部122は、8を取得する。算出部122は、8×2=16を算出する。算出された16は15より大きいので、算出部122は、16-15=1を算出し、算出した1を取得する。ここで取得した値が1であるので、算出部122は、取得した値と選択した元g=2とを新たなを元として部分群<2>={1,2,4,8}を生成する。なお、この部分群<2>に含まれる元の個数は4である。また、算出部122は、群Z/15Zに含まれる他の元についても同様に、指数2の部分群を生成する。例えば、算出部122は、群Z/15Zから元g=4を選択し、部分群<4>={1,4}を生成する。この部分群<4>に含まれる元の個数は2であるため、指数2の部分群にならないことに注意しておく。例えば、算出部122は、指数2の部分群<2>に対応する虚2次体Kを選択する。この場合、算出部122は、ガロア理論に基づき定義多項式fxの2つの解s及びs~を求める。この解sは、部分群<2>に含まれる元を用いると、s=ζζ2ζ4ζ8となる。また、解s~は、群Z/nZに含まれる元のうち、部分群<2>に含まれる元以外の元を用いると、s~=ζ7ζ11ζ13ζ14となる。なお、ここでは、ζ15をζと略記する。例えば、算出部122は、定義多項式fx=x2axbの2つの解と係数との関係式と、ζ15=1という性質とを用いて、係数a及びbを算出する。なお、この関係式は、下記の式2及び3によって表される。a=-ss~2b=s×s~3例えば、算出部122は、fxの2つの解s及びs~を式2に代入し、ζ15=1という性質を用いて演算することで、係数a=0を算出する。また、例えば、算出部122は、fxの2つの解s及びs~を式3に代入し、ζ15=1という性質を用いて演算することで、係数b=15を算出する。なお、算出部122は、部分群<4>を選択した場合、この部分群は指数2の部分群ではないので、定義多項式fxの2つの解s及びs~を求める処理を行わずに、他の部分群についての処理に移行する。このように、算出部122は、円分体Qζnに含まれる虚2次体Kの定義多項式fx=x2axbの係数a及びbを算出する。例えば、整数n=15を選択し、群Z/15Zの指数2の部分群<2>を用いた場合には、算出部122は、定義多項式fx=x2axbの係数a=0及びb=15を算出する。また、算出部122は、他の部分群についても同様に処理を実行し、他の部分群に対応する定義多項式fxの係数a及びbを算出する。また、算出部122が判別式Dを算出する処理について説明する。例えば、算出部122は、定義多項式fxの係数a及びbから4b-a2の値を算出し、算出した値の非平方因子を判別式Dとして算出する。例えば、算出部122は、下記の式4を用いて、判別式Dを算出する。なお、式4において、y2は、平方因子である。4b-a2=Dy24例えば、算出した係数がa=0及びb=15であった場合には、4b-a2=15×22となるので、算出部122は、非平方因子15を判別式D=15として算出する。また、算出部122は、定義多項式fxの係数a及びbを算出するごとに、判別式Dを算出する。以上のように、算出部122は、多項式rxの次数が所定値m以下となる判別式Dを算出する。例えば、埋め込み次数k=3かつ所定値m=8の場合には、算出部122は、オイラー関数φnの値が所定値m以下となる倍数n=3,6,9,12,15,18,24,30を選択する。算出部122は、選択した倍数nについて、円分体Qζnに含まれる虚2次体Kの定義多項式fx=x2axbの係数a及びbを算出する。そして、算出部122は、定義多項式fxの係数a及びbを算出するごとに、4b-a2の値の非平方因子を算出し、判別式D=1,3,5,15を求める。また、算出部122は、算出結果を算出データ111として記憶部110に格納する。例えば、算出部122は、埋め込み次数k=3と、所定値m=8と、判別式D=1,3,5,15とを対応づけて、算出データ111として記憶部110に格納する。生成部123は、算出した判別式Dと埋め込み次数kとを用いて、Brezing-Weng法以下、BW法と省略するに基づいて楕円曲線を生成する。例えば、生成部123は、記憶部110に記憶された算出データ111から埋め込み次数kと判別式Dとを取得する。そして、生成部123は、例えば、非特許文献1に記載されるように、取得した埋め込み次数kと判別式Dとを用いて楕円曲線を生成するBW法に基づいて、楕円曲線を生成する。出力部124は、各種情報を出力する。例えば、出力部124は、生成部123により生成された楕円曲線を示す情報を出力する。また、例えば、出力部124は、埋め込み次数kと、判別式Dと、楕円曲線を示す情報とを対応づけて出力するようにしても良い。次に、実施例1に係る楕円曲線生成装置100の処理手順について説明する。図2は、実施例1に係る楕円曲線生成装置の処理手順を示すフローチャートである。図2に示す処理は、例えば、楕円曲線生成装置100に電源から電力が供給されている間、所定時間間隔で実行される。図2に示すように、入力値である埋め込み次数k及び所定値mを受け付けるとステップS101,Yes、算出部122は、埋め込み次数kの倍数nのうち、オイラー関数φnの値が所定値m以下となる整数nを選択するステップS102。例えば、埋め込み次数k=3かつ所定値m=8の場合には、算出部122は、整数nとして、3,6,9,12,15,18,24,30を選択する。算出部122は、円分体Qζnに含まれる虚2次体Kの定義多項式fx=x2axbの係数a及びbを算出するステップS103。つまり、選択した整数nに対して群Z/nZを生成し、生成した群Z/nZの指数2の部分群を生成する。算出部122は、部分群に含まれる元の個数と、円分体Qζnの次数を虚2次体の次数で除算した値とが一致する場合に、虚2次体Kが存在すると判定する。虚2次体Kが存在する部分群について、算出部122は、ガロア理論に基づき定義多項式fx=x2axbの係数a及びbを算出する。なお、虚2次体Kが存在する部分群が複数存在する場合には、他の部分群についても同様に処理を実行し、他の部分群に対応する定義多項式fxの係数a及びbを算出する。また、選択した整数nが複数存在する場合には、他の整数nについても同様に処理を実行し、他の部分群に対応する定義多項式fxの係数a及びbを算出する。算出部122は、定義多項式fxの係数a及びbから4b-a2の値を算出し、算出した値の非平方因子を判別式Dとして算出するステップS104。なお、算出部122は、定義多項式fxの係数a及びbを算出するごとに、判別式Dを算出する。また、算出部122は、算出結果を算出データ111として記憶部110に格納する。生成部123は、算出した判別式Dと埋め込み次数kとを用いて、BW法に基づいて楕円曲線を生成するステップS105。例えば、生成部123は、記憶部110に記憶された算出データ111から埋め込み次数kと判別式Dとを取得する。そして、生成部123は、例えば、非特許文献1に記載されるように、取得した埋め込み次数kと判別式Dとを用いて楕円曲線を生成するBW法に基づいて、楕円曲線を生成する。なお、ステップS104の処理において、算出部122は、定義多項式fxの係数a及びbを算出するごとに判別式Dを算出するものと説明したが、これに限定されるものではない。例えば、ステップS103の処理において、定義多項式fxの係数a及びbを複数算出した後に、ステップS104の処理において、算出部122は、判別式Dを算出するようにしても良い。次に、実施例1に係る楕円曲線生成装置100の効果について説明する。楕円曲線生成装置100は、Brezing-Weng法における埋め込み次数を入力値として受け付ける。また、楕円曲線生成装置100は、受け付けた入力値に対して、Brezing-Weng法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する。また、楕円曲線生成装置100は、算出した判別式と入力値とを用いて、Brezing-Weng法に基づいて楕円曲線を生成する。このように、楕円曲線生成装置100は、多項式rxの次数に上限値を設定することで、ペアリング暗号に適したサイズの部分群位数rを出力する判別式Dを埋め込み次数kから求めることができ、楕円曲線を効率良く生成することができる。図3は、実施例1に係る楕円曲線生成装置の効果を説明するための図である。図3は、楕円曲線生成装置100により算出される判別式Dの値と、生成される楕円曲線の個数とを対応づけて示す。図3に示すように、埋め込み次数k=3かつ所定値m=8の場合には、楕円曲線生成装置100は、判別式D=1,3,5,15を算出する。この判別式D=1,3,5,15の値に対して、BW法において得られる多項式rxの次数は、それぞれ4,4,8,8となる。多項式rxの次数が多いほど生成される楕円曲線の個数は少なくなることが知られており、得られる楕円曲線の個数の比は、判別式D=1のときを1とすると、判別式D=1,3,5,15の値に対して、それぞれ1,1,0.5,0.5となる。従来のBW法においては、判別式Dには1を入力することが一般的であったため、得られる楕円曲線の個数の比は1である。これに対して、楕円曲線生成装置100により算出された判別式D=3,5,15を用いて楕円曲線を生成すると、得られる楕円曲線の個数の比は3となる。このため、楕円曲線生成装置100は、従来のBW法と比べて3倍多くの楕円曲線を得ることができ、楕円曲線を効率良く生成することができる。さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、その他の実施例にて実施されても良い。そこで、以下では、その他の実施例について説明する。実施例1において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。例えば、図2に示した処理手順は、受付部121が入力値である埋め込み次数k及び所定値mを受け付けた場合に自動的に開始されるものとして説明したが、楕円曲線生成装置100を利用する者が手動的に開始しても良い。この他、上述文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。例えば、算出データ111は、埋め込み次数kと、所定値mと、判別式Dとを対応づけると説明したが、所定値mを含む必要はない。つまり、算出データ111は、埋め込み次数kと、判別式Dとを対応づけたデータであっても良い。また、図1に示した楕円曲線生成装置100の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、楕円曲線生成装置100の分散統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散統合して構成することができる。例えば、図1に示した生成部123を楕円曲線生成装置100が有している必要は無い。つまり、楕円曲線生成装置100は、算出部122により算出された算出結果を算出データ111として記憶部110に格納しておき、格納した算出データ111を出力するようにしても良い。また、楕円曲線生成装置100は、楕円曲線生成装置100の各機能を既知の情報処理装置に搭載することによって実現することもできる。既知の情報処理装置は、例えば、パーソナルコンピュータ、ワークステーション、携帯電話、PHSPersonalHandyphoneSystem端末、移動体通信端末またはPDAPersonalDigitalAssistantなどの装置に対応する。図4は、楕円曲線生成プログラムを実行するコンピュータの一例を示す図である。図4に示すように、コンピュータ300は、各種演算処理を実行するCPU301と、ユーザからデータの入力を受け付ける入力装置302と、モニタ303とを有する。また、コンピュータ300は、記憶媒体からプログラム等を読み取る媒体読み取り装置304と、他の装置と接続するためのインターフェース装置305と、他の装置と無線により接続するための無線通信装置306とを有する。また、コンピュータ300は、各種情報を一時記憶するRAMRandomAccessMemory307と、ハードディスク装置308とを有する。また、各装置301~308は、バス309に接続される。ハードディスク装置308には、図1に示した算出部122及び生成部123の各処理部と同様の機能を有する楕円曲線生成プログラムが記憶される。また、ハードディスク装置308には、楕円曲線生成プログラムを実現するための各種データが記憶される。CPU301は、ハードディスク装置308に記憶された各プログラムを読み出して、RAM307に展開し、各種の処理を行う。また、これらのプログラムは、コンピュータを図1に示した算出部122及び生成部123として機能させることができる。なお、上記の楕円曲線生成プログラムは、必ずしもハードディスク装置308に記憶されている必要はない。例えば、コンピュータが読み取り可能な記録媒体に記憶されたプログラムを、コンピュータ300が読み出して実行するようにしても良い。コンピュータが読み取り可能な記録媒体は、例えば、CD-ROMやDVDディスク、USBメモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、LANLocalAreaNetwork、WANWideAreaNetwork等に接続された装置にこのプログラムを記憶させておき、コンピュータ300がこれらからプログラムを読み出して実行するようにしても良い。以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。付記1コンピュータが実行する楕円曲線生成方法であって、Brezing-Weng法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Brezing-Weng法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Brezing-Weng法に基づいて楕円曲を生成することを特徴とする楕円曲線生成方法。付記2前記判別式を算出する処理は、入力値kの倍数nのうち、オイラー関数φnの値が所定値以下となるnを選択し、円分体Qζnに含まれる虚2次体Kの定義多項式fx=x2axbを算出し、fxの係数a及びbから4b-a2の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする付記1に記載の楕円曲線生成方法。ただし、ζkは、1の原始k乗根であり、fxは、K=Q[x]/fxとなる多項式である。付記3Brezing-Weng法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Brezing-Weng法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出する算出部と、前記算出部により算出された判別式と前記入力値とを用いて、Brezing-Weng法に基づいて楕円曲線を生成する生成部とを備えたことを特徴とする楕円曲線生成装置。付記4前記算出部は、入力値kの倍数nのうち、オイラー関数φnの値が所定値以下となるnを選択し、円分体Qζnに含まれる虚2次体Kの定義多項式fx=x2axbを算出し、fxの係数a及びbから4b-a2の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする付記3に記載の楕円曲線生成装置。ただし、ζkは、1の原始k乗根であり、fxは、K=Q[x]/fxとなる多項式である。付記5コンピュータに、Brezing-Weng法における埋め込み次数を入力値として受け付け、受け付けた入力値に対して、Brezing-Weng法における部分群位数多項式の次数が所定値以下となる判別式を、埋め込み次数と判別式に係る円分体の拡大次数に基づいて算出し、前記判別式を算出する処理により算出された判別式と前記入力値とを用いて、Brezing-Weng法に基づいて楕円曲を生成することを特徴とする楕円曲線生成プログラム。付記6前記判別式を算出する処理は、入力値kの倍数nのうち、オイラー関数φnの値が所定値以下となるnを選択し、円分体Qζnに含まれる虚2次体Kの定義多項式fx=x2axbを算出し、fxの係数a及びbから4b-a2の値を算出し、算出した値の非平方因子を判別式として算出することを特徴とする付記5に記載の楕円曲線生成プログラム。ただし、ζkは、1の原始k乗根であり、fxは、K=Q[x]/fxとなる多項式である。"