(57)【要約】安全な超楕円曲線を迅速に決定するための方法を提供するために、適当な超楕円曲線が虚数乗法の方法を用いて構成されるべきことが提唱される。本発明の方法は、暗号用途に適する、大きな標数を有する有限体上の種数２の、超楕円曲線を生成する。本発明は更に上で説明したような方法を利用する暗号装置を提供するが、この装置は、送信者と受信者との間で公衆網を通じて情報を安全に交換するために、メッセージを暗号化及び復号するために用いるのに有効である。このような暗号装置を用いることで、交換されるべきメッセージ及び資料を、送信者及び受信者に対する認証手続において高速かつ簡単に暗号化することが可能となる。
2006513444.tif 000002
【特許請求の範囲】
【請求項１】
あるＣＭ体Ｋを選択するステップと、
Ｋ内の最大位数による複素乗法を有する単純主偏極アーベル多様体の全ての同型類の代表系を決定するステップと、
前記代表系と関連する周期行列を決定するステップと、
テータ零を決定するステップと、
ある有限体Ｆｑ上の前記ＣＭ体に対する類多項式を決定するステップと、
前記有限体Ｆｑ上のある超楕円曲線を決定するステップと、
前記超楕円曲線の因子類群の群位数ｎを指定するステップと、
を含む暗号法目的に適する超楕円曲線を決定する方法。
【請求項２】
前記超楕円曲線は種数２である請求項１記載の方法。
【請求項３】
イグサ不変量が前記テータ零から決定される請求項１記載の方法。
【請求項４】
前記イグサ不変量は前記類多項式を決定するために用いられる請求項３記載の方法。
【請求項５】
メストル不変量が前記テータ零から決定される請求項１記載の方法。
【請求項６】
前記メストル不変量はＦｑ上の超楕円曲線を生成するために用いられる請求項５記載の方法。
【請求項７】
複数の適切なＣＭ体Ｋと関連する類多項式とがアクセス可能な形式にて格納され、前記超楕円曲線を決定するためにメモリ内に保持されているこれら複数からあるＣＭ体が選択される請求項１乃至６のいずれかに記載の方法。
【請求項８】
前記周期行列はジーゲル既約形式にて用いられる請求項１乃至７のいずれかに記載の方法。
【請求項９】
たった６個のテータ零が決定される請求項１乃至８のいずれかに記載の方法。
【請求項１０】
前記代表系を決定するために、前記ＣＭ体Ｋの実数部分体の基本単位が前記ＣＭ体の単位のノルムであるか調べるためのテストがなされる請求項１乃至９のいずれかに記載の方法。
【請求項１１】
前記代表系を決定するために、イデアル類の集合が決定される請求項１乃至１０のいずれかに記載の方法。
【請求項１２】
互いに逆数のイデアル類の複数の対が識別され、イグサ不変量が各対に対してたった１度だけ前記テータ零から決定される請求項１１記載の方法。
【請求項１３】
ｑは素数ｐである請求項１乃至１２のいずれかに記載の方法。
【請求項１４】
前記素数ｐは、各類多項式がｈｋ個より多くの線形因子を有さないように選択され、ここでｈｋは前記ＣＭ体の類数を表す請求項１３記載の方法。
【請求項１５】
前記ＣＭ体は、前記超楕円曲線の前記因子類群の前記群位数ｎがまさに素数となるように選択される請求項１乃至１４のいずれかに記載の方法。
【請求項１６】
ｑはある素数ｐの冪である請求項１乃至１５のいずれかに記載の方法。
【請求項１７】
暗号方法であって、データを暗号化するためのキーは、請求項１乃至１６のいずれかに記載の方法によって生成されたある超楕円曲線のＦｑ−有理数の群から決定される特徴とする方法。
【請求項１８】
請求項１乃至１７のいずれかに記載の方法を用いる暗号装置。
【請求項１９】
請求項１８記載の、メッセージを暗号化するための暗号装置を備える、メッセージを送信するための送信機。
【請求項２０】
請求項１８に記載の、メッセージを復号するための暗号装置を備える、メッセージを受信するための受信機。
【発明の詳細な説明】
【技術分野】
【０００１】
多くの場合において、送信者と受信者との間の公衆網を通じての情報を安全な交換は、交換されるべきメッセージ及び資料が暗号化されることを要求し、従って、これら送信者と受信者とに対する認証手続を必要としている。
【背景技術】
【０００２】
とりわけ、頻繁に遭遇される暗号方法は、“公開キー”方法としても知られる、“非対称”暗号化と呼ばれるものである。この方法は、メッセージの受信者が、あるキーを、公衆網を通じて送信者に、原理的には、第三者がアクセスできるようなやり方にて伝送することを許す。このキーが“公開キー”である。送信者は、次に、そのメッセージをこのキーを用いて暗号化する。この公開キー方法の威力は、この方法にて暗号化されたメッセージは、この公開キーのみの知識では再び復号することはできないという事実にある。その公開キーの生成者、つまり、その受信者のみが、その暗号化されたメッセージを、その公開キーにて復号することができる。このタイプの非対称暗号化には複数の変形タイプが存在する。非対称方法の最も広く普及された例は、ＲＳＡ方法であることは疑いない。
【０００３】
公開キー方法のある下位グループは、ある非常に大きな自然数、或いは別の大きな自然数の整数モジュロ（integer modulo）、すなわち、公開キーを指数化するステップを含む。この方法のグループの機密性は、このやり方にてこの機密指数を得るために、離散的対数を計算することは、実際的には不可能であることに基づく。この離散的対数問題に基づく暗号化及び認証の方法の例としては、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ暗号、Ｅｌ−Ｇａｍａｌ暗号、ＤＳＳシグニチャ及びＳｃｈｎｏｒの方法等の名称にて知られている方法がある。
【０００４】
この離散的対数が基づいている有限アーベル群は、様々なやり方にて選択することができる。一つの可能な選択は、ある有限体Ｆｑ上に定義されたある超楕円曲線の零（０）次の因子類群のＦｑ−有理要素の群である。この群に対して、超楕円曲線のＪａｃｏｂｉ多様体のＦｑ−有理点群（Fq-rational point group）とも呼ばれ、この群の要素のあるコンパクトな表現（compact representation）と効率的な加法アルゴリズム（efficient adding algorithm）とが存在する。この表現とこの群の使用の更なる詳細については、例えば、N.Koblitz "Algebraic Aspects of Cryptology", Springer Verlag, 1998において議論されている。
【０００５】
しかし、この選択の１つの問題は、適切な超楕円曲線の決定である。離散的対数が実際問題として解くことができないことを保証するためには、この曲線の因子類群は、非常に大きな素因子を含むべきであるが、これはこの対数問題を解くためのアルゴリズムの実行時間はこの素因子の平方根に依存するためである。今日のコンピュータシステムの性能を基礎に取ると、この素因子は少なくとも２１６０ビット長であるべきである。しかし、システムが効率的であることを保証するためには、システムのパラメータ、例えば、これらキーは、長すぎるべきではない。
【０００６】
これら条件を満たす超楕円曲線は、その零次因子類群が素数或いはほとんど素数群の位数である曲線である。この種の曲線を決定するためには、原理的には、有限体Ｆｐからこの曲線の係数（coefficients）をランダムに選択することが可能である。この結果としての曲線が特異でないときは、この因子類群の要素の数を決定することができる。しかし、現在に至るまで、大きな特性値（種数２の曲線に対してはｐ＞２８０）を有する体上のランダムに選択された超楕円曲線に対しては、上記数、つまり、その因子類群の位数を見つけることは不可能であった。加えて、複数の超楕円曲線のほんの一部のみが素数或いはほとんど素数位数の因子類群を有し、このため、もしそのようなアルゴリズムが存在したとしても、それでも、上で定義された意味において安全な曲線を決定できる前に、多数の曲線をテストしなければならないという問題が存在する。これらテストは、選択過程の速度を減ずる。
【発明の開示】
【０００７】
従って、本発明の目的は、安全な超楕円曲線を高速にて決定するための方法を定義することにある。更に、本発明の目的は、このような安全な超楕円曲線の高速決定を遂行するための暗号装置を提供することにある。
【０００８】
本発明のこれら意図に対して、この目的は、適切な超楕円曲線を虚数乗法の方法を用いて構成することで達成される。この発明の方法は、暗号用途のために、大きな標数を有する有限体上の適切な種数２の超楕円曲線を生成する。
【０００９】
２に等しくない標数を有する体Ｆｑ（或いはＦｐ）上の種数ｇの超楕円曲線は
ｙ２＝ｆ（ｘ）
なる形式の特異でない曲線として定義することができ、ここでｆ（ｘ）は、次数２ｇ＋１の正規化多項式を表す。
【００１０】
以下ではＣＭ法と呼ばれる、この虚数乗法の方法は、これ自体は知られており、例えば、既にＡｔｋｉｎによって楕円曲線を構成するために用いられている。ＣＭ理論のこの知られている用途の詳細については、A.O.L Atkin, F. Morain, Elliptic curves and primality proving, Math. Comp. 61:29-68,1993を参照されたい。この知られているＣＭ法は、ある与えられた虚数二次位数（imaginary quadratic order）Ｏ及び素数ｐに対してその自己準同型環がＯに対して同型であるＦｐ上の楕円曲線Ｅを決定することを可能にする。このＣＭ法及び従ってこれが必要とする計算作業の複雑さは、このケースにおいては、類数（class number）ｈ（Ｏ）と位数Ｏの判別式によって決定される。A.-M. Spallek [IEM,1994, preprint no.18]及び本発明者であるA. Weng[IEM,2002,preprint np.11]による（博士学位）論文においては、このＣＭ法の適用が、種数２、類数１の超楕円曲線（Spallek）、種数２、高々１０までの超楕円曲線、及び種数３及びそれ以上の超楕円曲線の特別なケース（Weng）、の構成に拡大されている。
【００１１】
特に、本発明による方法においては、単純主偏極アーベル多様体（simple principally polarized Abelian varieties）の全ての同形類（isomorphism classes）に対するある代表系（representant system）が決定される。このケースにおいては、これら同形類の計算（counting）は、その基本単位（fundamental unit）がこのＣＭ体Ｋ内の１単位の相対ノルム（relative norm）であるかチェックする必要がないために、簡素化される。
【００１２】
また、これら周期行列を等価のジーゲル（Ｓｉｅｇｅｌ）既約行列に変換し、これによってテータ零（theta nulls）の高速収束を図ることもできる。
【００１３】
もう一つの好ましい実施例においては、複素数の体Ｃ上のこの超楕円曲線は計算された１０個のテータ零の内の６個から決定される。
【００１４】
また、本発明による方法の１つの好ましい変形例においては、複数の、とりわけ（好ましくは）、１００以上の、更には、１０００以上の、可能なＣＭ体が決定され、これらＣＭ体に属する類多項式が計算され、これら２つが、この安全な超楕円曲線を決定するための方法の使用の前に、データ集合として格納される。
【００１５】
本発明による方法の一つの変形においては、可能なＣＭ体の範囲はテストによって削減される。これによって、その群位数に対して正確な素数（exact prime number）が得られることを確保することができる。
【００１６】
本発明によるこの方法においては、有限体Ｆｐが基づいている素数ｐは、Ｆｐ上のＣＭ体Ｋの最小多項式が４つの異なる線形因子に分解されるように選択される。
【００１７】
もう一つの変形においては、曲線が基づいている有限体Ｆｑは素数ではない。
【００１８】
上述のような方法を用いる暗号装置は、送信者と受信者との間で公衆網を通じて情報を安全に交換するために、メッセージを暗号化及び復号するために用いるのに有効である。このような暗号装置を用いることで、交換のためのメッセージ及び資料を、送信者及び受信者に対する認証手続において、高速かつ簡単に暗号化することができる。
【００１９】
本発明のこれら及びその他の態様は、実施例を参照することで明らかであるが、以下ではこられについて詳細に説明する。
【発明を実施するための最良の形態】
【００２０】
以下においては、本発明による方法のステップが詳細に説明される。この方法は２つのサブステップを含む。第一のサブステップは、ＣＭ体Ｋと、体Ｆｐを定義するのに適する素数ｐと、適当な群位数ｎの決定に関する。
【００２１】
適切なＣＭ体Ｋが、最初に、類数ｈｋｏ＝１を有する全実数体（totally real number field）Ｋｏの全虚数二次拡大（total imaginary quadratic expansion）によって決定される。この種のＣＭ体は、例えば、集合Ｋ＝Ｑ（ｉ（ａ＋ｂｄ）１／２）１／２）によって与えられ、ここでａ，ｂ及びｄは整数である。
【００２２】
素数ｐは以下の３つの条件が満たされるように選択される。
１．  Ｏｋ内にｗｗ＝ｐとなるような数ｗが存在し、ここで、ＯｋはＫの最大位数を表し、ｗはｗの共役複素元を表す（ここ及び以降において下線は下線を施された項目の共役複素元を示す）。
２．  ｎ１＝Π（１−ｗｉ）或いはｎ２＝Π（１＋ｗｉ）はほとんど素数（almost prime）であること。ここでこの積ΠはＫ内のｗの全ての共役ｗｉをカバーする。
３．  これら位数ｎｉ（ｉ＝１，２）の１つはｋｑなる形式のものであり、ここでｋは小さな数であり、ｑはＦｑ内のｐの位数が高いという条件を満たす素数を表す。
【００２３】
ｐの選択は、この場合は、Ｏｋから乱数ηを選択し、積ηηの共役複素元が素数であるかチェックすることで簡易化できる。もしそれが素数である場合は、ｎ１或いはｎ２が条件２を満たすかチェックされる。このηは、この場合は、その相対ノルムが整数の集合Ｚの要素となることが保証されるように選択されるべきである。
【００２４】
代わりに、乱数ｐは、Ｚから選択し、Ｚ［ｘ］内の最小多項式を絶対ノルム方程式Ｎ／ｋ／ｑ（ｗ）＝ｐ２の全ての解に対して決定することもできる。これら多項式から、既約であり、絶対値ｐ１／２の零点（zero points）を有するものが選択される。これら最小多項式が次に点ｘ＝１の所で解析される。これは可能な群位数ｎｉの集合Ｓを与える。この集合は高々４つの異なる数を有する。これら値ｎｉが次に上の条件１と２を満たすかテストされる。
【００２５】
続く第二のサブステップに対しては、既に第一のサブステップにおいて条件１から３を満たすＣＭ体Ｋ、素数ｐ及び群位数ｎは決定されているものと想定される。この第二のサブステップにおいては、位数ｎの因子類群を有する体Ｆｐ上の超楕円曲線が構成される。
【００２６】
これを行う際には、種数２の超楕円曲線の場合は、これら曲線のヤコビ多様体は、完全に、次元２の主偏極アーベル多様体となるという事実が利用される。また、知られている方法を用いて、Ｏｋによる虚数乗法を有する複素数の体Ｃの単純主偏極アーベル多様体の全ての同形類に対するある代表系を見つけることが可能である。また、原理的には、これら多様体の周期行列（period matrix）Ωを集合Ｈ２から決定できることが知られている。ここで、Ｈ２＝｛ＭはＧｌ２（Ｃ）から取られ、Ｍｔ＝Ｍｐ、Ｍの虚数部は正定値｝は、次元２のジーゲル上側半平面（Siegel upper half-plane）を表す。この行列は、こうして、対称であり、正定値虚数部（positively defined imaginary part）を有する。
【００２７】
例として以下を取る。
【数１】
2006513444.tif 000003
【００２８】
ηはｉ（３＋）１／２に等しいものとして取られる。Ｑ（６１／２）の基本単位（fundamental unit）ε０は、この場合は、正のノルムを有する。実数二次部分体（real quadratic subfield）Ｏｋｏに対して相対的完備イデアル類群（ideal class group）の代表系は
【数２】
2006513444.tif 000004
として表すことができる。
【００２９】
Ａ１とＡ２の一般表現から
Ａｉ＝αＯｋｏ＋βＯｋｏ
τｉ＝α／βが計算されるが、上の例を取ると、
【数３】
2006513444.tif 000005
となる。
【００３０】
複素数Ｃの体内のＫの埋め込み（embedment）σは
【数４】
2006513444.tif 000006
と、これに対する共役複素元としてのρによって与えられる。Ｏｋによる乗法を有する単純主偏極アーベル多様体の全ての同形類の代表系は、すると、以下のような組の集合によって与えられる。
【数５】
2006513444.tif 000007
【００３１】
ある組（ｓ１，ｓ２）に対する関連する周期行列は
【数６】
2006513444.tif 000008
である。
【００３２】
以下の手続によって、体Ｋ＝Ｑ（ｉ（ａ＋ｂｄ１／２）１／２がＣＭ体であり、ε０が基本単位であり、σが共役
【数７】
2006513444.tif 000009
を表し、ρが複素共役である場合は、この同形類の総数が得られる。代表Ａｉ＝αｉＯｋｏ＋βｉＯｋｏに対して、τｉ＝αｉ／βｉが得られ、ここでτｉの虚部は正である。類群として｛τ１，・・・，τｋ・・・，τｈｋ｝およびｋ≦ｈとすると、ｉ≦ｋの場合、τｉσの虚部は正となり、ｉ＞ｋの場合、τｉσの虚部は負となる。以下の規則は、Ｏｋにて虚数乗法可能な単純主偏極アーベル多様体の適当な集合Ｓを得ることを可能にする。
Ｋがガロア体であるときは、Ｓ：＝｛τｉ，τｉσ），１≦ｉ≦ｈ｝
Ｋが非正規で、かつ、Ｎ（ε０）＝１のときは、ｋ：＝ｈ／２、
【数８】
2006513444.tif 000010
が得られ、そして、Ｋは非正規であるが、Ｎ（ε０）＝−１のときは、得られる定義は以下の通りとなる。
【数９】
2006513444.tif 000011
【００３３】
上で決定された周期行列Ωｉ（ｉ＝１，…，４）の各行列に対して、次に、絶対不変量ｊｋ（ｉ）（ｋ＝１，２，３）が計算される。この目的に対しては、最初に、各行列Ωｉに対して偶数のテータ零（even theta-nulls）が計算され、このテータ零の助けを借りて、Ｃ上の曲線が決定され、その曲線のヤコビ多様体が周期行列Ωに対応する。この曲線の類多項式がこれら絶対不変量から計算される。
【００３４】
これら周期行列Ωｉの偶数テータ零は
【数１０】
2006513444.tif 000012
によって与えられる。ここで、δ，εは集合｛０，１｝ｇから取られ、δｔε＝０  ｍｏｄ  ２である。
【００３５】
種数２の曲線については、この関数はちょうど１０個のテータ零を与える。この近似の質は、その後計算される類多項式の近似が、Ｚ［１／ｎ］［Ｘ］内にある滑らかな数（smooth number）ｎが存在するのに十分となるように選択されるべきである。説明の例では、７０桁（seventy decimal places）で十分である。
【００３６】
テータ零の助けを借りてのこの式の収束は、この関数内に、Ｈ２からの行列Ωｉの代わりに、ジーゲル縮約行列（Siegel-reduced matrices）Ω’を代入することで改善することができる。Ｈ２からの行列Ω’＝Ｘ＋ｉＹは（ここで、Ｘ＝（ｘｋｌ）、下付き文字ｋ,ｌ＝｛１，２｝）は、
１．１／２≦ｘｋ１≦−１／２
２．Ｙはミンコフスキー縮約（Minkowski-reduced）
３．全ての
【数１１】
2006513444.tif 000013
に対して
【数１２】
2006513444.tif 000014
が真であればジーゲル縮約である。
【００３７】
これらテータ零を介して、Ｃ上の求められている曲線のモデルを決定することができる。ローゼンハイン（Ｒｏｓｅｎｈａｉｎ）モデル
ｙ２  ＝  ｘ（ｘ−１）Π（ｘ−λｉ）
はこの種のモデルであり、ここで下付き文字ｉは１から２ｇ−１まで亘る、つまり、種数２から３の曲線に対する。このローゼンハインモデルは、これらλｉ値をテータ零から計算することを可能にする。下の例では、以下のようになる。
【数１３】
2006513444.tif 000015
【００３８】
これら１０個の偶数テータ零から、いわゆる絶対イグサ（Ｉｇｕｓａ）不変量ｊ１，ｊ２，ｊ３も既知の関数として得られる。しかし、ローゼンハインモデルのこれらλｉ及びこれらイグサ不変量は、両方とも単に６個のテータ零から決定することもできる。
【数１４】
2006513444.tif 000016
【００３９】
モデルｆ（ｘ）＝ｘ(ｘ−１)(ｘ−λ１)(ｘ−λ３)(ｘ−λ５)のこれらλｉ‘は、
λ１＝α１２α２２(α３２α４２)−１
λ３＝α３２α２２(α３２α６２)−１
λ５＝α５２α１２(α４２α６２)−１
によって与えられ、そして（非絶対）イグサ不変量は
【数１５】
2006513444.tif 000017
によって定義され、ここで
【数１６】
2006513444.tif 000018
であり、ここで項（ｇｈ）ｋは
【数１７】
2006513444.tif 000019
なる形式の、次数ｎとｍの、２つの２部形式（binary forms）のオーバレイを表す。
【００４０】
次に、この絶対不変量をイグサ不変量から得ることができる。
【数１８】
2006513444.tif 000020
【００４１】
これらイグサ不変量の計算はイデアル類の群Ｉｋをイデアル類とそれらの逆イデアル類の対に分けることで更に高速化することができる。類数１の体Ｋ０の場合は、この逆イデアル類は共役複素イデアル類に等しいために、見つけられた共役複素イデアル類の各対に対して、たった１つの単純主偏極アーベル多様体を計算することのみが必要とされる。
【００４２】
もし、（τｌ，τｌΨ）がイデアルＡｉに属する主偏極アーベル多様体であり、ＣＭタイプ（Ｋ，Ψ）である場合は、（−τｌ，−τｌΨ）はＡｉに属する、同じＣＭタイプの主偏極アーベル多様体である。もし、加えて、ｊｉが（τｉ，τｉΨ）のイグサ不変量である場合は、（−τｉ，−τｉΨ）の対応するイグサ不変量はｊｉに等しい。こうして、共役複素イデアル類の逆類の各対に対して、たった１つのイグサ不変量を決定することのみが必要とされる。この結果として、このステップに対して要求される計算作業の量がほとんど半減される。
【００４３】
これら類多項式Ｈｋはイグサ不変量ｊｋ，ｋ＝１，・・・，３の関数として
【数１９】
2006513444.tif 000021
として表すことができ、ここで、ｉ＝１，・・・，４である。
【００４４】
これら多項式は、有理多項式Ｑ［ｘ］の総体（corpus）のメンバである。無限連分数の方法の適用とこれに続く乗法によって、Ｈｋ（Ｘ）は整数多項式Ｈｋ（Ｘ）＃に変換することができる。この例においては、
【数２０】
2006513444.tif 000022
は
【数２１】
2006513444.tif 000023
である。
【００４５】
もし、精度が十分に高く選択される場合は、これら係数（coefficients）の分母の最小公倍数は、この連分数アルゴリズム（continued fraction algorithm）にて見つけられる。本例においては、これは１１４となる。これによって整多項式
【数２２】
2006513444.tif 000024
が与えられる。
【００４６】
これらＱ［ｘ］上の形式Ｈｋ（Ｘ）の類多項式と整多項式Ｚ［ｘ］の体上の形式Ｈｋ（Ｘ）＃の類多項式は、選択されたＣＭ体Ｋのみに依存する。しかし、この超楕円曲線に対する基礎素体（basic prime number field）Ｆｐは、このＣＭ体Ｋが選択された後でもまだ変わり得る。このため、望ましくは、多数の、実際には数百或いは数千の、適当なＣＭ体及び関連する類多項式が事前に計算され、適当なやり方にて格納される。もし、このステップの後に、暗号を適用するために、ある超楕円曲線を生成することが必要となったときは、メモリ内に保持されたファイルからの、あるランダムに選択されたＣＭ体、或いは換言すればランダムに選択された類多項式を利用して、適当な素数ｐと群位数ｎが第一のサブステップにおいて挙げられた基準によって決定される。その後、以下のステップが、これら類多項式を再決定することを必要とされることなく、直ちにＦｐ上の超楕円曲線を決定するために遂行される。
【００４７】
ある暗号プロトコルを実現するためには、また、望ましくは、その動作は完全に素数（exactly prime）である群位数に制限される。
【００４８】
この目的に対しては、ＣＭ体の選択を制限すること、及び２を法とする最小多項式Ｋ／Ｑが２つの異なる係数を有するような、すなわち、既約なＣＭ体Ｋのみを用いることが提唱される。
【００４９】
このため、Ｆｐ上の超楕円曲線を計算するための以下のステップにおいては、このＣＭ体Ｋは既に選択されており、それら類多項式Ｈｋ（Ｘ）＃は上述のステップを遂行することで既に計算されているか或いは事前に計算されたファイルから取り出されているものと想定される。
【００５０】
次のステップはこの曲線を計算することである。この目的のためには、Ｈｋ（Ｘ）＃（ａｋ）＝０  ｍｏｄ  ｐを有する（Ｆｐ）３からの各３つ組（ａ１，ａ２，ａ３）に対して以下のステップが遂行される。
【００５１】
ｊｉ：＝ａ１，ｊ２：＝ａ２及びｊ３：＝ａ３とセットする。次に、メストル（Ｍｅｓｔｒｅ）不変量Ａｉｊ及びＨｉｊｋがｊｉから計算される。例えば、
【表１】
2006513444.tif 000025
において説明されているように、有限体に対する知られているメストル手続の下では、これらメストル不変量は
ΣＡｉｊｘｉｘｊ
なる二次形式と、
ΣＨｉｊｋｘｉｘｊｘｋ
なる三次形式の係数であり、ここで、この総和は下付き文字ｉ，ｊ，ｋの１から３まで亘っている。
【００５２】
この二次形式に対するパラメータを多項式ｆ１（ｔ），ｆ２（ｔ），ｆ３（ｔ）を取ることでセットし、これらを三次形式に
ΣＨｉｊｋｆｉ（ｔ）ｆｊ（ｔ）ｆｋ（ｔ）
に代入することで、Ｆｐ上の超楕円曲線のモデル
ｙ２＝ｆ（ｔ）  
が得られる。次に、この多項式ｆ（ｔ）の次数（通常は６）が、ｆ（ｔ）がＦｐ内に零点を有するときは、射影変換によって１から５だけ低減される。次に、この曲線の因子類群が位数ｎのそれであるか否かを、ランダム因子Ｄを選択し、積ｎＤを形成することでチェックする。
【００５３】
与えられた例の場合は、この結果としての曲線は
【数２３】
2006513444.tif 000026
となり、体Ｆｐ上に定義され、ここで
【数２４】
2006513444.tif 000027
は上述の値に等しい。このｎの値は素数の１５２倍である。
【００５４】
このメストルアルゴリズムは適当な素数ｐを選択することで高速化できる。これに対する前提条件は、ＣＭ体Ｋが非正規であることと、ｐは、Ｋ内で完全に分解できる整数Ｚの集合に属する素数であるが、これは、Ｆｐ内のＫの最小多項式が４つの異なる線形因子（linear factors）に分解できることと等価である。これら条件の下では、各類多項式に対するｐを法とする線形因子の数は、上述の式ｗｗ＝ｐが、その符号と共役複素元を除いて、集合Ｏｋからのたった１つの解ｗを有するならば、半減される。この線形因子の半減化はメストルアルゴリズムの適用を８の因数だけ高速化する。
【００５５】
この長所を活用できるようにするためには、上の第一のサブステップにおいて決定された素数ｐがＦｐ内のＫの最小多項式を４つの異なる線形因子に分解するかを調べるためのチェックがなされる。これは直接の計算によって行うことができる。しかし、上で説明したように、ｐは、既約であり絶対値ｐ（１／２）の所に零点を有するＺ［ｘ］内の最小多項式の点ｘ＝１の所での解析にて選択されものであり、これら見つけられた素数は既に予め分類されている。この後、これら素数は２つの異なる群位数のみを許す素数に制限することもできる。
【００５６】
ＣＭ体が巡回的であり、そのイデアル類群の巾指数が２より大きいときは、この意味において有益な素数は正に密（positive density）である。とりわけ、このような無限個の素数が存在する。
【００５７】
この暗号目的に適する超楕円曲線を生成するための説明の方法は、非素数有限体（non-prime finite fields）Ｆｑをカバーするように拡大することもできる。この場合は、数ｑ：＝ｐｆは素数ｐの冪として定義される。この指数ｆは自然数であり、拡大次数（degree of expansion）と呼ばれる。また、この曲線はＦｑの部分体（subfield）上では定義できないものと想定することもできる。
【００５８】
このＣＭ体Ｋがガロア体である場合は、ｐは
ｐ＝Ｋ／Ｋ０内のＡＡ
となるように選択されるべきである。
【００５９】
もし、ｆが
Ａｆ＝（ｗ）    （ｗはＯｋからの元）
が主イデアル（main ideal）である条件下で最小のものとして選択されるときは、Ｆｑ上の類多項式の平方根が存在する。Ｆｑ上の超楕円曲線はこれら平方根からメストルアルゴリズムを介して上で詳述されたように構成することができる。これら曲線の位数は
ｎ＝Π（１−ｗｉ）或いはΠ（１＋ｗｉ）
によって与えられ、ここで下付き文字ｉは１，・・・，４であり、ｗｉはｗの共役複素元を表す。
【００６０】
このＣＭ体が非ガロア体、かつ、非正規である場合は、この素数ｐは素イデアル（ｐ）が３つのイデアル
（ｐ）＝ｐ１ｐ２ｐ３
に分解されるように選択されるべきである。
【００６１】
この場合は、あるイデアルＡが存在し、このことは
Ａ＝ｐ１ｐ２２
であることを意味し、ｆは、ここでも
Ａｆ＝（ｗ）    （ｗはＯｋからの元）
なる条件下で、最小のものとして選択される。
【００６２】
これら条件の下では、この非素数有限体Ｆｑここでｑ＝ｐ２ｆ上の超楕円曲線は、上で詳述されたようにしてメストルアルゴリズムを介して構成することができる。この群位数はガロア体Ｋの場合と同様にして計算することができる。
【００６３】
一例として、ある曲線が、拡大次数ｆ＝２ｈｋ＝１０の体上で、類数ｈｋ＝５を有するＣＭ体Ｋから開始して構成される。素数としては、この体Ｋ上のそのイデアル（ｐ）が３つの素イデアルに分解される、ｐ＝９１１が用いられる。イデアルＡ＝ｐ１ｐ２２に対しては、ｆ＝５が最小指数である。この主イデアルは従ってＡｆである。
【００６４】
ｑ＝９１１１０である体Ｆｑ内の成分は次数９の多項式にて記述することができる。モジュロｐ既約類多項式（modulo p irreducible class polynomials）は
【数２５】
2006513444.tif 000028
である。
【００６５】
２つの可能な群位数
【数２６】
2006513444.tif 000029
が得られる。
【００６６】
これと関連する曲線ｙ２＝ｆ（ｘ）は
【数２７】
2006513444.tif 000030
となるが、ここで、上では
【数２８】
2006513444.tif 000031
なる簡略表記が用いられている。
【００６７】
群位数はｎ２＝４００ｒとなるが、ここでｒは５７桁を有する素数を表す。
【図面の簡単な説明】
【００６８】
【図１】本発明によるＣＭ体及び関連する類多項式を決定するための第一のサブステップを示す図である。
【図２】本発明による暗号目的に適する曲線を決定するための第二のサブステップを示す図である。
【図１】
2006513444.tif 000032
【図２】
2006513444.tif 000033
【国際調査報告】
2006513444.tif 000034