(57)【特許請求の範囲】
【請求項１】
文の暗号化に用いるパラメータを計算機により超楕円曲線暗号パラメータ生成アルゴリズムに基いて生成する暗号パラメータ生成方法において、
入力手段により得られた超楕円曲線を構成する井草不変量と分母因子閾値とに基いて、複素数体計算手段が、上記井草不変量の１次基本対称式の値を計算して、該値を記憶手段に記憶するステップと、
計算手段が、上記記憶された１次基本対称式の値を上記分母因子閾値以下の分母因子である複数の有理数に変換した分母素因数群とし、該分母素因数群を記憶手段に記憶するステップと、
計算手段が、上記記憶されている有理数の分母素因数群に基いて、井草不変量の１次基本対称式の値をそれら複数の有理数の積で表した連分数展開で近似して複数の類多項式を得て、該複数の類多項式を構成する出現頻度の多い有理数を係数の候補として得て該得た係数の候補を記憶手段に記憶するステップと、
計算手段が、上記記憶されている係数の候補の中から、類多項式の係数多項式としての可約性を満たすことを判定条件として、類多項式係数を決定するステップ、とを備えたことを特徴とする超楕円曲線暗号パラメータ生成方法。
【請求項２】
計算手段が、超楕円曲線の実２次体の総虚２次拡大体上において、所定の判別式を計算するステップ、を備え、
上記判別式を計算するステップにおいて、所定の条件が満足される場合には、計算手段が、井草不変量の上記１次基本対称式を、２つの、構成する有理数の個数が半分の１次基本対称式群で表現して、該構成する有理数の個数が半分の１次基本対称式群に対して、有理数への変換を得るようにしたことを特徴とする請求項１記載の超楕円曲線暗号パラメータ生成方法。
【請求項３】
文の暗号化に用いるパラメータを計算機により超楕円曲線暗号パラメータ生成アルゴリズムに基いて生成する暗号パラメータ生成装置において、
入力手段により得られた超楕円曲線を構成する井草不変量と分母因子閾値とに基いて、上記井草不変量の１次基本対称式の値を計算して、該値を記憶手段に出力する複素数体計算手段と、
上記記憶された１次基本対称式の値を上記分母因子閾値以下の分母因子である複数の有理数に変換して分母素因数群とし、該得た分母素因数群を記憶手段に出力し、
上記記憶されている有理数の分母素因数群に基いて、井草不変量の１次基本対称式の値をそれら複数の有理数の積で表した連分数展開で近似して複数の類多項式を得て、該複数の類多項式を構成する出現頻度の多い有理数を係数の候補として得て該得た係数の候補を記憶手段に出力し、
上記記憶されている係数の候補の中から、類多項式の係数多項式としての可約性を満たすことを判定条件として、類多項式係数を決定する計算手段と、
上記井草不変量の上記計算された１次基本対称式の値を一時記憶し、
上記有理数に変換された分母素因数群を一時記憶し、
上記係数の候補を一時記憶する記憶手段と、
を備えたことを特徴とする超楕円曲線暗号パラメータ生成装置。
【発明の詳細な説明】
【０００１】
本発明は、楕円曲線暗号等、幾つかの暗号体系のうちで、超楕円暗号設計の効率的な方法およびそれを用いた暗号設計ツールに関するものである。
【０００２】
【従来の技術】
従来の種数２の超楕円曲線設計方法について説明する。これは楕円曲線暗号設計とは全く別の体系であり、楕円曲線暗号体系での方法を超楕円曲線暗号に適用しても必ずしもうまく適用できない。即ち別の分野であり、以降超楕円曲線暗号設計に限定して述べる。
従来の種数２超楕円曲線設計方法は、Ａ．Ｗｅｎｇ、"Ｃｏｎｓｔｒｕｃｔｉｎｇ  ｈｙｐｅｒｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ  ｏｆ  ｇｅｎｕｓ  ２  ｓｕｉｔａｂｌｅ  ｆｏｒ  ｃｒｙｐｔｏｇｒａｐｈｙ"、  Ｅｓｓｅｎ  Ｕｎｉｖｅｒｓｉｔｙ、Ｉｎｓｔｉｔｕｔｅ  ｆｏｒ  Ｅｘｐｅｒｉｍｅｎｔａｌ  Ｍａｔｈｅｍａｔｉｃｓ、ｐｒｅｐｒｉｎｔ  Ｎｏ．１２（２０００）  及び  Ａ−．Ｍ．Ｓｐａｌｌｅｋ、"Ｋｕｒｖｅｎ  ｖｏｍ  Ｇｅｓｃｈｌｅｃｈｔ  ２ｕｎｄ  ｉｈｒｅ  Ａｎｗｅｎｄｕｎｇ  ｉｎ  Ｐｕｂｌｉｃ−Ｋｅｙ−Ｋｒｙｐｔｏｓｙｓｔｅｍｅｎ"、  Ｅｓｓｅｎ  Ｕｎｉｖｅｒｓｉｔｙ、Ｉｎｓｔｉｔｕｔｅ  ｆｏｒ  Ｅｘｐｅｒｉｍｅｎｔａｌ  Ｍａｔｈｅｍａｔｉｃｓ、ｐｒｅｐｒｉｎｔ  Ｎｏ．１８（１９９４）、に記載されている。また、以下の数学的背景は、Ｇ．Ｓｈｉｍｕｒａ、"Ａｂｅｌｉａｎ  Ｖａｒｉｅｔｉｅｓ  ｗｉｔｈ  Ｃｏｍｐｌｅｘ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ａｎｄ  Ｍｏｄｕｌａｒ  Ｆｕｎｃｔｉｏｎｓ"、Ｐｒｉｎｃｅｔｏｎに記載されている。
【０００３】
まず本発明の技術的背景である公開鍵暗号、離散対数問題および超楕円暗号について簡単に説明する。
公開鍵暗号通信においては、利用者ごとに秘密鍵ｘと公開鍵ｙの組が用意され、秘密鍵ｘは、各利用者が秘密に保持しておく。公開鍵ｙは利用者自身以外の一般に公開する。利用者Ｂが利用者Ａに秘密にデータを送りたい時は、利用者Ｂは利用者Ａに対応する公開鍵ｙを用いてデータを暗号化する。この暗号文は、秘密鍵ｘを知る利用者Ａにしか復号できない。
離散対数問題とは代数群Ｇ（加法が定義されているものとする）の２つの要素ｇ1、ｇ2に対して、ｇ1＝ｍｇ2を満たすようなｍを求める問題である。代数群Ｇの要素の数が大きい場合、多くの離散対数問題を解くことは、計算量的に非常に困難になることが知られている。この事実を利用してｍを秘密鍵、ｇ1またはｇ2を公開鍵とする暗号を設計することができる。
有限体Ｆq上の種数２の超楕円曲線Ｃとは、ｙ2＝ｆ（ｘ）（ｆ（ｘ）はＦq係数の５次または、６次式）と表される方程式である。また、Ｃのヤコビ多様体の有理点集合には加法が定義されて、群となる。種数２においては、曲線のヤコビ多様体と主偏極アーベル多様体は一対一に対応し、また、次数２のジーゲル上半空間の点とも一対一に対応している。ここで、次数２のジーゲル上半空間とは、２ｘ２の複素対称行列で、虚数部が正定値になるもの全体のことである。
【０００４】
ここで特に、次数２の主偏極アーベル多様体を主偏極アーベル曲面という。また、実２次体の総虚２次拡大体を次数２のＣＭ体という。また、次数２のＣＭ体Ｋに対し、恒等写像ｉｄとその恒等写像でも複素共役でもない複素数体への埋め込みσとの対ΦをＣＭ体Ｋとあわせて、ＣＭタイプ（Ｋ，Φ）という。また、リフレックスＣＭタイプ（Ｋ*，Φ*）がＣＭタイプ（Ｋ，Φ）から一意的に決まる。
虚数乗法を持つ主偏極アーベル曲面の準同型環は、次数２のＣＭ体Ｋのオーダーと同型になる。Ｋのオーダーとは、Ｋの部分環で、Ｋの有理数体上の生成系を含む、階数がＫの有理数体上の次数と一致する整数係数自由加群となるものである。特にＫの整数環は、Ｋのオーダーである。主偏極アーベル曲面の原点の接空間での準同型環の表現は、２つの１次表現の直和に同値になり、ＣＭタイプ（Ｋ，Φ）が決まる。
Ｋの整数環を準同型環にもつＣＭタイプ（Ｋ，Φ￣）の主偏極アーベル曲面に対応するジーゲル上半空間の点Ωiは、Ｋのイデアル類群の部分群Ｗ’とＫの単数群の部分群の商群の直積集合の要素と一対一に対応している。ＣＭタイプ（Ｋ，Φ）の主偏極アーベル曲面に対応するジーゲル上半空間の点ΩiもＫのイデアル類群とＫの単数群の構造から同じように同定することが可能であり、Ｋが有理数体上ガロア拡大でない場合には、Ｋの整数環を準同型環にもつ主偏極アーベル曲面全体の集合は、ＣＭタイプ（Ｋ，Φ）をもつものとＣＭタイプ（Ｋ，Φ￣）をもつものの和集合となる。
本明細書、ならびに要約書においては、上記和集合の各元が定める井草不変量が満たすモニック有理数係数または、その有理数係数既約因子多項式のことを類多項式と呼ぶことにする。
【０００５】
次数２のジーゲル上半空間の点から主偏極アーベル多様体を与える対応は、テータ関数によって与えられる。また、主偏極アーベル多様体から曲線を与える対応は、Ｍｅｓｔｒｅの方法などによって与えられる。図８は、従来の超楕円曲線の虚数乗法を用いた構成法のフローチャートである。図９は、図８内の類多項式を構成するステップＳ４０３での更に細かいフローチャートとなっている。
図８において、まず次数２のＣＭタイプ（Ｋ，Φ）が入力される。Ｓ４０１はジーゲル上半空間の点Ωi（ｉ＝１，…，ｍ）を計算するステップ、Ｓ４０２は井草氏が提案した量、いわゆる井草不変量ｊi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）を計算するステップ、Ｓ４０３は類多項式Ｈk（ｋ＝１，…，６）を構成するステップ、Ｓ４０４は超楕円曲線Ｃの係数を求めるステップであり、Ｓ４０５は大きい素数ｐを選ぶステップ、Ｓ４０６は素数ｐを割り切るヴェイユ数ωを計算するステップ、Ｓ４０７はヤコビ多様体のＦp有理点の位数ｎを計算するステップであり、Ｓ４０８において、ｎが概略して素数とみなせる概素数であれば、Ｓ４０４で計算された超楕円曲線と位数ｎが出力される。
【０００６】
次に動作を説明する。まず虚数乗法による種数２の超楕円曲線の構成方法を図８に基づいて説明する。
次数２のＣＭタイプ（Ｋ，Φ）がまず入力される。Ｓ４０４を除く各ステップにおける演算は全て複素数体内での演算となり、Ｓ４０４では、有限体Ｆp上の演算となる。
次に類多項式の構成方法を図９に基づいて説明する。井草不変量ｊi,k（ｉ
＝１，…，ｍ；ｋ＝１，…，６）がまず入力される。各ステップにおける演算は全て複素数体内での演算となる。
Ｓ５０１は、井草不変量ｊi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）の添え字ｉに関する基本対称式ｓ〜i,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）を計算するステップ、Ｓ５０２はｓi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）を計算するステップであり、Ｓ５０３で類多項式Ｈk（ｋ＝１，…，６）が計算されて出力される。
ここで、従来の演算方法によると、Ｓ５０２と、Ｓ５０３の類多項式Ｈk（ｋ＝１，…，６）を求めるステップに多大の処理を必要とし、従って時間がかかる。即ち実数を展開近似して有理数に変換を行い、Ｈk＝Σsi,kXm-i（Σはｉ＝０からｍまで）を求めると、エラーが発生したり、または、より次数を高めて有理数に変換するので処理量が増大する。
【０００７】
【発明が解決しようとする課題】
従来の虚数乗法を用いた種数２の超楕円曲線の構成方法は、以上のように構成されており、一般には複素数体内での計算精度を低くして適用すると、実数から有理数への変換を行う演算ステップ（Ｓ４０３、Ｓ５０２）において近似した有理数が得られず、エラー終了することになった。エラー終了を回避するには、計算精度を高くする必要があり、そのため計算時間、計算領域共に多くが必要であるという課題がある。
【０００８】
本発明の目的は、上記の課題を解決するためになされたもので、１次基本対称式の分母に現れる素因数群を見つけて、低い精度でも所定の有理数による類多項式を構成することができ、従って暗号生成の基となる暗号アルゴリズムを高速に得ることを目的とする。
【０００９】
【課題を解決するための手段】
この発明に係る計算機を用いて超楕円曲線暗号アルゴリズムを生成する方法において、超楕円曲線を構成する井草不変量１次基本対称式s〜1kの有理数への変換s1kの分母素因数群を得るステップと、変換した分母素因数群に着目して、井草不変量の基本対称式とそれら素因数群の積の連分数展開近似によって、出現頻度の多い、類多項式の有理数係数の候補を得るステップと、出現頻度が多い有理数係数候補中から、類多項式のK*0係数多項式としての可約性を判定条件として類多項式係数を決定するステップ、とを備えた。
【００１０】
この発明に係る超楕円曲線の次数２のＣＭ体上において、所定の判別式を計算するステップを設けて、判別式が計算ステップにおいて所定の条件を満足する場合には、井草不変量の基本対称式群を、２つの、個数が半分の基本式群で表現して、個数半分の基本対称式群に対して、有理数への変換を得るようにした。
【００１１】
この発明に係る超楕円曲線暗号アルゴリズムを生成する計算ユニットを用いた装置において、
超楕円曲線を構成する井草不変量の１次基本対称式s〜1kの有理数への変換s1kの分母素因数群を出力する計算手段と、s1kとその分母素因数群を記憶する記憶手段と、s1kの分母素因数群に着目して、井草不変量の基本対称式s〜i,kとそれら素因数群の積の連分数展開近似によって、出現頻度の多い、類多項式の有理数係数の候補を出力する計算手段と、出現頻度が多い有理数係数候補を記憶する記憶手段と、記憶された有理数係数候補中から、類多項式のK*0係数多項式としての可約性を判定条件として類多項式係数を決定する計算手段、とを備えた。
【００１２】
【発明の実施の形態】
実施の形態１.
本実施の形態における主旨は、超楕円曲線における類多項式の構成において、いわゆる井草不変量の基本対称式を連分数展開して近似した時に、1次基本対称式s〜1kの有理数への変換s1kの分母素因数群に着目し、かつその類多項式係数s1kの分母との共通因数を多くもった小素因数からなる分母を持った他の基本対称式の有理数近似を、見つけることである。これは、逆にこれまで正しく有理数展開できた類多項式の各係数の分母は、共通の小素因数の積になることが知られているからである。こうした共通小素因数を見つけることができれば、やみくもに類多項式を計算して近似が成立するかどうかを調べる必要がなくなる。以下、計算機を用いることが必須になるが、その計算機を用いた処理時間を短縮する方法を述べる。
【００１３】
本発明による類多項式の構成方法の一実施の形態を図１に基づいて説明する。
図１は本実施の形態による、井草不変量ｊi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）からそれらを根とする有理数係数の類多項式を計算する方法を示したフローチャートである。図において、まず井草不変量ｊi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）と分母推定を行う時に用いる分母因子（素因数）閾値Ｂが入力される。Ｓ１０１はｓ〜i,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）を計算するステップ、Ｓ１０２は分母因子がＢ以下になるｓi,kを一つ見つけるステップ、Ｓ１０３はＳ１０２でｓi,kを一つ見つけることができたかどうか判定するステップ、Ｓ１０４はｓi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）の候補のリストＬｓi,kを計算するステップ、Ｓ１０５はＨk（ｋ＝１，…，６）を計算するステップ、Ｓ１０６はＨkがＫ0*上可約かどうか判定するステップであり、可約と判断されると、Ｈkが出力される。このフローにおいて、従来の図９に示すフローと比較すると、本実施の形態における主旨であるＳ１０２と、対応して結果を確認するＳ１０４が、Ｓ５０２に代わっていることが判る。
【００１４】
次に動作を説明する。
まず、ＣＭ体Ｋを一つ選ぶ。それから、Ｋ*上共役になるＫの整数環を準同型環にもつ主偏極アーベル多様体に対応するジーゲル上半空間の点Ωi（ｉ＝１，…，ｍ）を計算する。Ωi（ｉ＝１，…，ｍ）のそれぞれに対し、テータ零値を用いて、井草不変量ｊi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）を計算する。このｊi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）と分母因子閾値Ｂを入力し、Ｓ１０４で素因数と見なせる候補をリストアップする。そしてその中からどの有理数近似にも共通に現れる数、即ち出現頻度が一番多いものを係数の候補とする。図２はこのようにして得られたHkの各次数について、次数の小さいものから順に並べて、得られた有理数係数の分母di,kの例を示す表である。この表は、
K=Q(√-(8+√3) )の時の、Hi(X)の分母を表している。即ち、絶対値の一番小さい(i, k)=(1, 4)の時の係数の分母d1,4に着目して、それを素因数（この場合、32194）に分解する。これは小素因数ばかりなので、素因数分解抽出プログラムを用いて計算機上で実行すれば、容易に得られる。
そしてＳ１０６で可約であれば、Ｓ１０７で類多項式Ｈk（ｋ＝１，…，６）を出力する。
図１の各ステップにおける計算は、全て複素数体上の演算ならびに代数体上の演算となる。この方法の演算は、素因数を見つければよく、結果的に実数から有理数への変換に必要とされる精度は、従来より低くてもよい。こうして高速に超楕円暗号アルゴリズムを得ることができる。
【００１５】
上記方法を適用した演算装置を図３に基づいて説明する。
図３は本実施の形態における有理数係数の類多項式を計算する演算装置を示した図である。図において、６０１は入力手段、６０２は記憶手段、６０３は複素数体計算手段、６０４は代数体計算手段、６０５と６０６と６０７と６０８と６０９と６１０は計算手段、６１１は出力手段、６１２は装置全体を制御する制御手段である。
【００１６】
その動作であるが、まず、ＣＭ体Ｋに対して、Ｋ*上共役になるＫの整数環を準同型環にもつ主偏極アーベル多様体に対応するジーゲル上半空間の点Ωi（ｉ＝１，…，ｍ）のそれぞれに対し、テータ零値を用いた、井草不変量ｊi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）と分母因子閾値Ｂが入力手段６０１に入力される。この装置では、類多項式Ｈk（ｋ＝１，…，６）が計算される。まず、計算手段６０５において、ｓ〜i,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）が計算される。各計算は、複素数体計算手段６０３を用いて計算される。計算されたｓi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）は記憶手段６０２に記憶される。
次に、計算手段６０６において、ｓ〜i,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）に順次連分数展開近似を適用して有理数への変換を行い、その分母因子がＢ以下になるものが一つ見つかったらそれをｓ〜i,kとし、また、その分母因子の集合をＳとする。各計算は、複素数体計算手段６０３を用いて計算される。計算されたｓ〜i,k及びＳは記憶手段６０２に記憶される。
次に、計算手段６０７において、ｓi,kが一つ見つかったかどうか判定する。もし、見つからなかったらエラーが出力手段６１１から出力される。
【００１７】
次に、計算手段６０８において、計算手段６０６において変換したもの以外のｓ〜i,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）にＳの元を素因子とする数を掛け合わせた実数に、連分数展開近似を用いた有理数への変換を行って、その分母因子がＢ以下になるものの中で出現頻度が一番多いものからリストアップしたリストＬｓi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）が計算される。各計算は、複素数体計算手段６０３を用いて計算される。計算されたＬｓi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）は記憶手段６０２に記憶される。
次に、計算手段６０９において、各Ｌｓi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）の先頭から順に要素を取り出して作った有理数配列ｓi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）を用い、ｓ0,k＝１、Ｘを変数として、類多項式の候補Ｈk＝Σｓi,kＸm-i（ｋ＝１，…，６）が計算される。各計算は、代数体計算手段６０４を用いて計算される。計算されたＨk（ｋ＝１，…，６）は記憶手段６０２に記憶される。
【００１８】
次に、計算手段６１０において、ＨkがリフレックスＣＭ体の部分実２次体Ｋ0*上可約かどうかｋが１から６まで順次判定される。もし、可約でなければ、そのｋについて、計算手段６０９に処理が引き渡される。
最後に、計算されたＨk（ｋ＝１，…，６）またはエラーの時はエラーが、出力手段６１１から出力される。
以上のように類多項式の係数の分母の素因子には小さい素数しかあらわれないことを利用して、上記の出現頻度の高い素因数を見つけて、その値によりＨk（ｋ＝１，…，６）を計算すれば、実数から有理数への変換に従来必要とされていた精度は結果的に従来より低くしても解を求めることが出来、従って高速に超楕円暗号アルゴリズムを得ることが出来る。
【００１９】
実施の形態２．
類多項式を例えば２つの類多項式で表現できるとすれば、類多項式の係数は、次数が小さくなるので更に低い必要精度で、見つけやすくなる。本実施の形態ではこのことに着目し、次数ｍの有理数係数類多項式が次数ｍ／２の有理数係数類多項式の積で得られると仮定して、ｍ／２の類多項式についてその有理数係数を求める。
本発明による類多項式の構成方法の一実施の形態を図４に基づいて説明する。図４は本実施の形態による従来の半分の次数の類多項式を計算する方法を示したフローチャートである。図において、まず井草不変量ｊi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）と分母推定を行う時に用いる分母因子閾値Ｂが入力される。Ｓ２０１はインデックスリストＬを作成するステップ、Ｓ２０２は半分次数の類多項式の根の組み合わせを探索するステップであり、図１のフローと比較すると、Ｓ２０１とＳ２０２のステップが特徴であることが判る。Ｓ２０３は探索が成功したかどうかを判定するステップ、Ｓ２０４はＳ２０３で成功したインデックスに従って、基本対称式ｓ１〜i,k（ｉ＝１，…，ｍ／２；ｋ＝１，…，６）、ｓ２〜i,k（ｉ＝１，…，ｍ／２；ｋ＝１，…，６）を計算し、連分数展開近似を用いて、ｓ１i,k（ｉ＝１，…，ｍ／２；ｋ＝１，…，６）、ｓ２i,k（ｉ＝１，…，ｍ／２；ｋ＝１，…，６）に変換するステップ、Ｓ２０５は類多項式Ｈ１k（ｋ＝１，…，６）、Ｈ２k（ｋ＝１，…，６）を計算するステップ、Ｓ２０６はＨ１k（ｋ＝１，…，６）、Ｈ２k（ｋ＝１，…，６）がＫ0*上可約かどうか判定するステップであり、可約と判断された類多項式に関しては、Ｈ１kまたはＨ２kが出力され、既約と判断された多項式に関しては、エラーと出力される。
【００２０】
次に動作を説明する。
まず、ＣＭ体Ｋを一つ選ぶ。それから、Ｋ*上共役になるＫの整数環を準同型環にもつ主偏極アーベル多様体に対応するジーゲル上半空間の点Ωi（ｉ＝１，…，ｍ）を計算する。Ωi（ｉ＝１，…，ｍ）のそれぞれに対し、テータ零値を用いて、井草不変量ｊi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）を計算する。このｊi,k（ｉ  ＝１，…，ｍ  ；  ｋ  ＝１，…，６）と分母因子閾値Ｂを入力し、類多項式Ｈ１k（ｋ＝１，…，６）、Ｈ２k（ｋ＝１，…，６）を計算する。図３の各ステップにおける計算は、全て複素数体上の演算ならびに代数体上の演算となる。この方法は、もし積を見つけることが出来れば、従来の類多項式の半分次数の類多項式で、有理数係数多項式への変換を可能にし、従ってより少ない演算で済ますことができ、高速に超楕円暗号アルゴリズムを得ることができる。
【００２１】
上記方法を適用した演算装置を図５に基づいて説明する。
図５は本実施の形態における従来の半分の次数の類多項式を計算する装置を示した図である。図において、７０１は入力手段、７０２は記憶手段、７０３は複素数体計算手段、７０４は代数体計算手段、７０５と７０６と７０７と７０８と７０９と７１０は計算手段、７１１は出力手段、７１２は装置全体を制御する制御手段である。
【００２２】
その動作であるが、まず、ＣＭ体Ｋ*に対して、Ｋ上共役になるＫの整数環を準同型環にもつ主偏極アーベル多様体に対応するジーゲル上半空間の点Ωi（ｉ＝１，…，ｍ）のそれぞれに対し、テータ零値を用いた、井草不変量ｊi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）と分母推定を行う時に用いる分母因子閾値Ｂが入力手段７０１に入力される。この装置では、類多項式Ｈk（ｋ＝１，…，６）の有理既約因子多項式Ｈ１k（ｋ＝１，…，６）、Ｈ２k（ｋ＝１，…，６）が計算される。まず、計算手段７０５において、Ωi（ｉ＝１，…，ｍ）を決めるために用いたイデアル類群Ｗ’の指数２の部分群に対応する井草不変量ｊi,kｍ／２個のインデックスの組のリストＬが計算される（その要素の個数をｌとする）。各計算は、代数体計算手段７０４を用いて計算される。計算されたＬは記憶手段７０２に記憶される。
【００２３】
次に、計算手段７０６において、Ｌの要素であるインデックスを順次取り出し、それに従って、井草不変量ｊi,4の和ｓ１〜1,4が計算され、その有理数への変換ｓ１1,4の分母因子が全てＢ以下になるまで繰り返される。各計算は、複素数体計算手段７０３を用いて計算される。計算されたｓ１1,4とインデックスは記憶手段７０２に記憶される。
次に、計算手段７０７において、分母因子が全てＢ以下のｓ１1,4が見つかったかどうか判定される。もし、見つからなかったら“エラー”が出力手段７１１から出力される。
次に、計算手段７０８において、計算手段７０６において求められたインデックスに従い、そのインデックスに入るｊi,kの基本対称式ｓ１〜i,k（ｉ＝１，…，ｍ／２；ｋ＝１，…，６）を計算して、連分数展開近似を用いて、ｓ１i,k（ｉ＝１，…，ｍ／２；ｋ＝１，…，６）に変換し、また同インデックスに従い、そのインデックスに入らないｊi,kの基本対称式ｓ２〜i,k（ｉ＝１，…，ｍ／２；ｋ＝１，…，６）を計算して、連分数展開近似を用いて、ｓ２〜i,k（ｉ＝１，…，ｍ／２；ｋ＝１，…，６）に変換される。各計算は、複素数体計算手段７０３を用いて計算される。計算されたｓ１i,k（ｉ＝１，…，ｍ／２；ｋ＝１，…，６）、ｓ２i,k（ｉ＝１，…，ｍ／２；ｋ＝１，…，６）は記憶手段７０２に記憶される。
【００２４】
次に、計算手段７０９において、ｓ0,k＝１、Ｘを変数として、類多項式のＨk（ｋ＝１，…，６）の有理既約因子多項式の候補Ｈ１k＝Σｓ１i,kＸm/2-i（ｋ＝１，…，６）（Σはｉ＝０からｍ／２まで）、Ｈ２k＝Σｓ２i,kＸm/2-i（ｋ＝１，…，６）（Σはｉ＝０からｍ／２まで）、が計算される。各計算は、代数体計算手段７０４を用いて計算される。計算されたＨ１k、Ｈ２k（ｋ＝１，…，６）は記憶手段７０２に記憶される。
次に、計算手段７１０において、Ｈ１k、Ｈ２k（ｋ＝１，…，６）がリフレックスＣＭ体の部分実２次体Ｋ0*上可約かどうかｋが１から６まで順次判定される。各計算は、代数体計算手段７０４を用いて計算される。
最後に、各ｋに対してＨ１k（ｋ＝１，…，６）またはエラーの時は“エラー”が、出力手段６１１から出力され、各ｋに対してＨ２k（ｋ＝１，…，６）またはエラーの時は“エラー”が、出力手段６１１から出力される。
以上のように類多項式Ｈkがかなりの頻度で、有理数係数の半分次数既約因子多項式の積に分解できることを利用してＨ１k、Ｈ２k（ｋ＝１，…，６）を計算すれば、実数から有理数への変換に従来必要とされていた精度を、従来より低くしても解を求めることができ、従って高速に超楕円暗号アルゴリズムが得られる。
【００２５】
上記では、類多項式を２つの低次数の類多項式の積で表現できる、と仮定して説明を行った。以下、この仮定が正しいかどうかを容易に判定する方法について説明する。
【００２６】
図６は本実施の形態における判定法、つまり従来の半分次数の類多項式を得るＣＭ体Ｋを探索して可能と判定する方法を示したフローチャートである。図において、まずＣＭ体Ｋが入力される。Ｓ３０１はＫのリフレックスＣＭ体の部分実２次体Ｋ0*を計算するステップ、Ｓ３０２はＫ0*の判別式ｄ0*を計算するステップ、Ｓ３０３はｄ0*が奇数かどうか判定するステップで、奇数と判定されれば、“Ｋは超楕円暗号構成に適したＣＭ体である”と出力され、そうでなければ、“Ｋは超楕円暗号構成に適したＣＭ体でない”と出力される。
【００２７】
次に動作を説明する。
まず、ＣＭ体Ｋを一つ選ぶ。これはＫの有理数体上の定義多項式を与えることによってなされる。そして、Ｋ0*の定義多項式が計算され、Ｋ0*の判別式が計算され、その偶奇性によって、Ｋが超楕円暗号構成に適したＣＭ体かどうか判定される。
図４の各ステップにおける計算は、全て代数体整数環上の演算となる。この方法を実際に類多項式構成の前計算として行い、超楕円暗号構成に適したＣＭ体Ｋに対してのみ、実施の形態１及び実施の形態２における類多項式構成法を適用する。
【００２８】
上記方法を適用した演算装置を図７に基づいて説明する。
図７は本実施の形態における、従来の半分次数の類多項式を計算できるＣＭ体Ｋを探索し、判定する装置を示した図である。図において、８０１は入力手段、８０２は記憶手段、８０３は代数体計算手段、８０４と８０５と８０６は計算手段、８０７は出力手段、８０８は装置全体を制御する制御手段である。
【００２９】
その動作であるが、まず、ＣＭ体Ｋが入力手段８０１に入力される。これはＫの有理数体上の定義多項式を与えることによってなされる。この装置ではＫが超楕円暗号構成に適したＣＭ体かどうかが判定される。まず、計算手段８０４において、リフレックスＣＭ体の部分実２次体Ｋ0*が計算される。各計算は、代数体計算手段８０３を用いて計算される。計算されたＫ0*は記憶手段８０２に記憶される。
次に、計算手段８０５において、Ｋ0*の判別式ｄ0*が計算される。各計算は、代数体計算手段８０３を用いて計算される。計算されたｄ0*は記憶手段８０２に記憶される。
次に、計算手段８０６において、ｄ0*が奇数かどうか判定される。
最後に、ｄ0*が奇数の場合は、“超楕円暗号構成に適している”を、偶数の場合は、“超楕円暗号構成に適していない”が出力手段８０７から出力される。
以上のように類多項式Ｈkが、有理数係数の半分次数既約因子多項式の積に分解するＣＭ体をあらかじめ選別できる。
【００３０】
【発明の効果】
以上のようにこの発明によれば、超楕円曲線を構成するために必要となる類多項式の分母の絶対値が最小となる係数に対して、その分母の小素因数群とその係数を得るステップと、その分母絶対値最小の係数を利用して他の有理数係数候補を得るステップと、出現頻度の多い有理数係数候補に基づいて類多項式を得るステップとを備えたので、演算量を少なくでき、少ない計算時間で暗号アルゴリズムを得られる効果がある。
【図面の簡単な説明】
【図１】  本発明の実施の形態１における超楕円曲線の類多項式を得るフロー図である。
【図２】  図１における有理数近似の分母を構成する素因数分解例を示す図である。
【図３】  実施の形態１における類多項式を計算する演算装置の構成図である。
【図４】  本発明の実施の形態２における超楕円曲線の類多項式を得るフロー図である。
【図５】  実施の形態２における類多項式を計算する演算装置の構成図である。
【図６】  実施の形態２における判別式を計算するフロー図である。
【図７】  実施の形態２における判別式を計算する演算装置の構成図である。
【図８】  従来の超楕円曲線の虚数乗法による類多項式を得るフロー図である。
【図９】  従来の類多項式を構成するステップの詳細を示したフロー図である。
【符号の説明】
Ｓ１０１  ｓi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）を計算するステップ、Ｓ１０２  分母因子がＢ以下になるｓi,kを一つ見つけるステップ、Ｓ１０３  Ｓ１０２でｓi,kを一つ見つけることができたかどうか判定するステップ、Ｓ１０４  ｓi,k（ｉ＝１，…，ｍ；ｋ＝１，…，６）の候補のリストＬｓi,kを計算するステップ、Ｓ１０５  Ｈk（ｋ＝１，…，６）を計算するステップ、Ｓ１０６  ＨkがＫ0*上可約かどうか判定するステップ、Ｓ２０１  ｍ／２個のインデックスの組のリストを作成するステップ、Ｓ２０２  有理数Ｓ１1,4に変換するステップ、Ｓ２０６  部分実２次体Ｋ0*上で可約かを調べるステップ、Ｓ３０３ｄ0*は奇数かを調べるステップ。
【図１】
0003892229.tif 000002
【図２】
0003892229.tif 000003
【図３】
0003892229.tif 000004
【図４】
0003892229.tif 000005
【図５】
0003892229.tif 000006
【図６】
0003892229.tif 000007
【図７】
0003892229.tif 000008
【図８】
0003892229.tif 000009
【図９】
0003892229.tif 000010