(57)【要約】【課題】本発明は楕円暗号、符号等の基本技術である体の逆元の計算を高速に行う方法に関するものである。【解決手段】本方法では、任意の基礎体とその任意次数の拡大体Ｍがあったとき、この次数の整数倍に１を足したものが素数のｑによるｑ分多項式により拡大した体Ｌを考え、この拡大体Ｌの中間体として体Ｍを考える。このようにすることでＭにおけるフロベニウス写像がＬにおけるフロベニウス写像から自然に得られる。このＬにおけるフロベニウス写像に必要な計算の量は大変小さい。また逆元を求めるにあたりある中間体上の要素のそれより小さい中間体に関する共役元全ての積とノルムを計算することを繰り返すことにより、Ｍにおける乗算の使用頻度を減らしている。このような操作により任意の拡大次数の拡大体を得ることができ、結果として逆元を高速に求めることができる。【選択図】      図２
2004233428.tif 000002
【特許請求の範囲】
【請求項１】
有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算装置であって、
外部からの入力データを受け付ける入力部と、前記入力データの数値から約数列を決定する約数列算出部と、前記約数列算出部から前記約数を逐次入力して共役元積とノルムとを計算し前記約数列算出部に返却する共役元積ノルム計算部と、前記約数列算出部から入力した共役元積とノルムとから逆元を計算する逆元計算部と、前記逆元計算部で計算した逆元を出力する出力部とを備え、
前記入力部は、基礎体Ｋを拡大して拡大体Ｍを求める任意の拡大次数ｎ（ｎは自然数）と、ｑ＝ｎ・ｊ＋１が素数となるようなｑ（ｊは小さい自然数）と、ｑ次の円分分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）が素体Ｚ／ｐＺ上で既約となるような素数ｐであって、その素数ｐを情報処理装置上の数値として表現した場合の有効ビット数が情報処理装置の処理するワード長以下でかつそれに近いビット数、ワード長の半分以下でかつそれに近いビット数，  およびワード長の２倍以下でかつそれに近いビット数のいずれかの条件をもつ素数ｐと、
素体Ｚ／ｐＺを拡大して基礎体Ｋを得るための既約多項式と、を入力し、
素数ｐと既約多項式をもとに基礎体Ｋを生成し、基礎体Ｋをｎによって拡大して拡大体Ｍ、基礎体Ｋをｑ次の円分多項式で拡大して拡大体Ｌを決定し、前記拡大体Ｍの元で逆元の演算を行う元Ａを入力し、
前記約数列算出部は、ｎの約数ｎ［１］、・・・ｎ［ｋ］  について、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるような約数列を選び、位数が基礎体Ｋのｎ［ｉ］乗であるＬの部分体をＮ［ｉ］  とし、ｎ［０］＝１、ｎ［ｋ＋１］＝ｎ、Ｎ［０］＝Ｋ、Ｎ［ｋ＋１］＝Ｍ、Ａ［ｋ＋１］＝Ａとした時、ｎの約数ｎ［ｉ］、ｎ［ｉ＋１］と、Ａ［ｉ］とをｉがｋから始まり１になるまで逐次前記共役元積ノルム算出部に提供し、結果として前記共役元積ノルム算出部から返却された共役元積Ａ［ｉ］  ＊を記憶し、
前記共役元積ノルム算出部は、約数ｎ［ｉ］  、ｎ［ｉ＋１］と、Ａ［ｉ］を用い、
Ｎ［ｉ−１］に関するＡ［ｉ］を除くＡ［ｉ］の共役元全ての積Ａ［ｉ］  ＊を、
Ａ［ｉ］＊＝Ａ［ｉ］＾｛ｐｎ［ｉ−１］＋ｐ２ｎ［ｉ−１］＋・・・＋ｐｎ［ｉ］−ｎ［ｉ−１］｝＝（・・・（（Ａ［ｉ］＾（ｐｎ［ｉ−１］）Ａ［ｉ］）＾（ｐｎ［ｉ−１］）Ａ［ｉ］）・・・）＾（ｐｎ［ｉ−１］）、と計算し、
ノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を、
ＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）＝Ａ［ｉ］Ａ［ｉ］＊、として計算し、このノルムを
新たにＡ［ｉ−１］とし共役元積Ａ［ｉ］＊とともに前記約数列算出部に返却し、
前記逆元算出部は、
前記約数列算出部の記憶する共役元積全てと、
前記約数列算出部が最後に呼び出した時の前記共役元積ノルム算出部が出力したノルムの逆元Ａ［０］−１と、の積を、
Ａ−１＝Ａ［ｋ＋１］＊Ａ［ｋ］＊・・・Ａ［１］＊Ａ［０］−１として計算し、
前記出力部は、前記逆元計算部の計算結果を出力する、
ことを特徴とする逆元演算装置。
【請求項２】
有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算方法であって、
ある素数ｑがあって１の原始ｑ乗根のみを根とする基礎体Ｋについて既約な多項式を定義多項式として用い、基礎体Ｋを拡大した拡大体Ｌを得る第１のステップと、
基礎体Ｋと拡大体Ｌとの間の、所与の拡大次数ｎで基礎体Ｋを拡大した拡大体Ｍを求める第２のステップと、
拡大体Ｍの元の逆元を拡大体Ｌにおけるフロベニウス写像を用いて求める第３のステップと、
を備え、
前記ｑは、拡大次数ｎの整数倍に１を足した素数であることを特徴とする逆元演算方法。
【請求項３】
有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算方法であって、
任意の基礎体Ｋとその任意拡大次数ｎによる拡大体Ｍがあったとき、前記拡大次数ｎの整数倍に１を足した素数ｑによって得られるｑ次円分多項式により基礎体Ｋを拡大した拡大体Ｌを求め、拡大体Ｍにおけるフロベニウス写像が拡大体Ｌにおけるフロベニウス写像から自然に得られることを利用して逆元を求めることを特徴とする逆元演算方法。
【請求項４】
請求項３において、拡大体Ｍの元Ａの逆元を求めるにあたり、拡大次数ｎの任意の約数列ｎ［１］、・・・ｎ［ｋ］  を、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるよう選び、
拡大体Ｍと基礎体Ｋとの間の位数が（＃Ｋ）ｎ［ｉ］（有限体Ｋの位数のｎ［ｉ］乗）のある部分体をＮ［ｉ］  としたとき、
Ｋ⊂Ｎ［１］⊂・・・⊂Ｎ［ｋ］⊂Ｍであって、
最初に拡大体Ｍの直下の部分体Ｎ［ｋ］に関するＡの全ての共役元の積とノルムをもとめ、これを基礎体Ｋに達するまで繰り返し計算することにより逆元を求めることを特徴とする逆元演算方法。
【請求項５】
有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算方法であって、
拡大体Ｍの拡大次数ｎと、
ｑ＝ｎ・ｊ＋１（ｊは小さな自然数）で得られる素数ｑと、
ｑ次円分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）が素体Ｚ／ｐＺ上で既約となるような素数ｐであって、その素数ｐを情報処理装置上の数値として表現した場合の有効ビット数が情報処理装置の処理するワード長以下で、かつそれに近いビット数、ワード長の半分以下でかつそれに近いビット数，  およびワード長の２倍以下でかつそれに近いビット数、のいずれかの条件をもつ素数ｐと、
素体Ｚ／ｐＺを拡大して基礎体Ｋを得るための既約多項式と、
拡大体中の逆元を求める元Ａを入力する第１のステップと、
拡大次数ｎの任意の約数ｎ［１］、・・・ｎ［ｋ］  について、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるような約数列を選ぶ第２のステップと、
拡大体Ｍと基礎体Ｋの間にあって位数が（＃Ｋ）ｎ［ｉ］である中間体列を求める第３のステップと、
中間体列の拡大体Ｍ直下の中間体に関する元Ａの共役元で自分自身以外のものを全てかけあわせた共役元積を求めこれを記憶する第４のステップと、
共役元積と元Ａを掛け合わせてＡのノルムを計算してこれをＡ’とする第５のステップと、
前記第５のステップのＡ’について前記中間体列でＭから１段下げてシフトした中間体について前記第４のステップと前記第５のステップのＡをＡ’で置き換えて実行し、同様にして前記ノルムが基礎体Ｋの元になるまでこれを有限回繰り返す第６のステップと、
基礎体についてのノルムの逆元を求め、前記第４のステップで記憶する全ての中間体列に関する共役元積との積を計算してこれをＡの逆元とする第７のステップと、
を備えることを特徴とする逆元演算方法。
【請求項６】
２７ビット以上３２ビット以下の素数を標数とし１の原始７乗根を含まない素体Ｐに１の原始７乗根を付加して拡大した６次拡大体Ｍの元の逆元を計算する逆元演算方法であって，
６次拡大体Ｍの元で逆元を求める元Ａが入力される第１のステップと、
素体Ｐの３次拡大体Ｎ［１］を求める第２のステップと、
元Ａの３次拡大体Ｎ［１］についての共役元全ての積を第一共役元積として計算する第３のステップと、
前記第一共役元積に元Ａをかけあわせた第一ノルムを計算する第４のステップと、
前記第一ノルムの前記素体についての共役元すべての積を第二共役元積として計算する第５のステップと、
前記第二共役元積に前記第一ノルムをかけあわせた第二ノルムを計算する第６のステップと、
前記第二ノルムの逆元を計算する第７のステップと、
前記第二ノルムの逆元と前記第二共役元積と前記第一共役元積とをかけあわせてＡの逆元Ａ−１を計算する第８のステップと、
Ａの逆元Ａ−１を出力する第９のステップと、
を備えることを特徴とする逆元演算方法。
【請求項７】
請求項６において、素体Ｐの元は情報処理装置において１ワードとして処理され、６次拡大体Ｍの元は６ワードとして処理されることを特徴とする逆元演算方法。
【請求項８】
有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算方法であって、
基礎体Ｋを拡大して拡大体Ｍを求める任意の拡大次数ｎ（ｎは自然数）と、
ｑ＝ｎ・ｊ＋１が素数となるようなｑ（ｊは小さい自然数）と、
ｑ次の円分分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）が素体Ｚ／ｐＺ上で既約となるような素数ｐであって、その素数ｐを情報処理装置上の数値として表現した場合の有効ビット数が情報処理装置の処理するワード長以下でかつそれに近いビット数、ワード長の半分以下でかつそれに近いビット数，  およびワード長の２倍以下でかつそれに近いビット数のいずれかの条件をもつ素数ｐと、
素体Ｚ／ｐＺを拡大して基礎体Ｋを得るための既約多項式と、
を入力する第１のステップと、
素体Ｚ／ｐＺ上の既約多項式を一つ選び、この既約多項式でＺ／ｐＺを拡大して得られる体を基礎体Ｋとし、既約多項式として一次式が選ばれた場合にはＫ＝Ｚ／ｐＺとするとともに、基礎体Ｋをｑ次の円分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）で拡大した体を拡大体Ｌとする時、拡大体Ｌの中間体Ｍとしてｊ＝１の場合はＭとしてＬ自身をとり、ｊ＞１の場合は、位数がｐｎのものをＭとし、逆元を計算する対象のＭの元Ａを入力する第２のステップと、
ｎの任意の約数ｎ［１］、・・・ｎ［ｋ］  について、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるような約数列を選び、位数がＫの位数のｎ［ｉ］乗であるＬの部分体をＮ［ｉ］とし、ｎ［０］＝１、Ｎ［０］＝Ｋ、Ｎ［ｋ＋１］＝Ｍ、Ａ［ｋ＋１］＝Ａとする第３のステップと、
Ｎ［ｉ］の要素Ａ［ｉ］  について、Ｎ［ｉ−１］に関する共役元全ての積Ａ［ｉ］  ＊を、
Ａ［ｉ］＊＝Ａ［ｉ］＾｛ｐｎ［ｉ−１］＋ｐ２ｎ［ｉ−１］＋・・・＋ｐｎ［ｉ］−ｎ［ｉ−１］｝＝（・・・（（Ａ［ｉ］＾（ｐｎ［ｉ−１］）Ａ［ｉ］）＾（ｐｎ［ｉ−１］）Ａ［ｉ］）・・・）＾（ｐｎ［ｉ−１］）と計算して記憶する第４のステップと、
ノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を、
ＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）＝Ａ［ｉ］Ａ［ｉ］＊と計算し、このノルムを新たにＡ［ｉ−１］とする第５のステップと、
ｉ＝ｋ＋１の拡大体Ｍの元Ａから１の基礎体Ｋまで順に、Ａ［ｉ］を入力し、
Ａ［ｉ］＊及びノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を得る第６のステップと、
ＮＮ［１］／Ｎ［０］（Ａ［１］）の逆元を求め、これをＡ［０］−１とする第７のステップと、
第４のステップで記憶したＡ［ｉ］＊と第７のステップのＡ［０］−１から
Ａ−１＝Ａ［ｋ＋１］＊Ａ［ｋ］＊・・・Ａ［１］＊Ａ［０］−１としてＡの逆元を得る第８のステップと、
を備えることを特徴とする逆元演算方法。
【請求項９】
有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算処理をコンピュータに実行させる逆元演算プログラムであって、
ある素数ｑがあって１の原始ｑ乗根のみを根とし基礎体Ｋについて既約な多項式を定義多項式として用いて基礎体Ｋを拡大した拡大体Ｌを得る機能と、基礎体Ｋと拡大体Ｌとの間の所与の数値ｎで基礎体Ｋを拡大した拡大体Ｍを求める機能と、
拡大体Ｍの元の逆元を拡大体Ｌにおけるフロベニウス写像を用いて求める機能と、
を備え、
ｑは、中間体の拡大次数ｎの整数倍に１を足した素数であることを特徴とする逆元演算プログラム。
【請求項１０】
有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算処理をコンピュータに実行させる逆元演算プログラムであって、
基礎体Ｋを拡大して拡大体Ｍを求める任意の拡大次数ｎ（ｎは自然数）と、
ｑ＝ｎ・ｊ＋１が素数となるようなｑ（ｊは小さい自然数）と、
ｑ次の円分分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）が素体Ｚ／ｐＺ上で既約となるような素数ｐであって、その素数ｐを情報処理装置上の数値として表現した場合の有効ビット数が情報処理装置の処理するワード長以下でかつそれに近いビット数、ワード長の半分以下でかつそれに近いビット数，  およびワード長の２倍以下でかつそれに近いビット数のいずれかの条件をもつ素数ｐと、
素体Ｚ／ｐＺを拡大して基礎体Ｋを得るための既約多項式と、
を入力する機能と、
素体Ｚ／ｐＺ上の既約多項式を一つ選び、この既約多項式でＺ／ｐＺを拡大して得られる体を基礎体Ｋとし、既約多項式として一次式が選ばれた場合にはＫ＝Ｚ／ｐＺとするとともに、基礎体Ｋをｑ次の円分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）で拡大した体を拡大体Ｌとする時、拡大体Ｌの中間体Ｍとしてｊ＝１の場合はＭとしてＬ自身をとり、ｊ＞１の場合は、位数がｐｎのものをＭとし、逆元を計算する対象のＭの元Ａを入力する機能と、
ｎの任意の約数ｎ［１］、・・・ｎ［ｋ］  について、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるような約数列を選び、位数が（＃Ｋ）ｎ［ｉ］であるＬの部分体をＮ［ｉ］  とし、ｎ［０］＝１、Ｎ［０］＝Ｋ、Ｎ［ｋ＋１］＝Ｍ、Ａ［ｋ＋１］＝Ａとする機能と、
Ｎ［ｉ］の要素Ａ［ｉ］  について、Ｎ［ｉ−１］に関する共役元全ての積Ａ［ｉ］  ＊を、
Ａ［ｉ］＊＝Ａ［ｉ］＾｛ｐｎ［ｉ−１］＋ｐ２ｎ［ｉ−１］＋・・・＋ｐｎ［ｉ］−ｎ［ｉ−１］｝＝（・・・（（Ａ［ｉ］＾（ｐｎ［ｉ−１］）Ａ［ｉ］）＾（ｐｎ［ｉ−１］）Ａ［ｉ］）・・・）＾（ｐｎ［ｉ−１］）と計算して記憶する機能と、
ノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を、
ＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）＝Ａ［ｉ］Ａ［ｉ］＊と計算し、このノルムを新たにＡ［ｉ−１］とする機能と、
ｉ＝ｋ＋１の拡大体Ｍの元Ａから１の基礎体Ｋまで順に、Ａ［ｉ］を入力し、
Ａ［ｉ］＊及びノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を得る機能と、
ＮＮ［１］／Ｎ［０］（Ａ［１］）の逆元を求め、これをＡ［０］−１とする機能と、
第４のステップで記憶したＡ［ｉ］＊と第７のステップのＡ［０］−１から
Ａ−１＝Ａ［ｋ＋１］＊Ａ［ｋ］＊・・・Ａ［１］＊Ａ［０］−１としてＡの逆元を得る機能と、
を備えることを特徴とする逆元演算プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，  有限体である基礎体とその有限次拡大体との中間体の元の逆元を求める方法に関し、特に前記拡大体が前記基礎体を、既約な多項式で、ある整数ｍがあって根として１の原始ｍ乗根およびそれのみを根とするものを定義多項式として用いる逆元演算装置、逆元演算方法、及び逆元演算プログラムに関する。
【０００２】
【従来の技術】
楕円曲線暗号や符号においては素体とは限らない有限体の元の逆元を求める演算が使われることがある。そして多くの場合この演算は、乗算加算等のその他の演算に比べて計算時間を多く必要とするため、この高速化による恩恵は大きい。
【０００３】
特許文献１には、この内容が記載されている。
楕円曲線暗号の例をあげる。ある有限体上定義された楕円曲線上の点の加算に必要な計算は、点をａｆｆｉｎｅ座標であらわした場合に定義体上の乗算３個と逆元演算１個である。定義体が素体の場合逆元演算に必要な計算量は乗算の１０倍以上必要で、点の加算に必要な計算に占める逆元演算の割合は大きい。それゆえ、逆元演算の高速化は重要な課題となっている。
【０００４】
定義体を素体でない有限体にすることで、定義体の逆元演算を効率化する方法が  幾つか知られている。そうした効率化方法として例えば、ＯＥＦによる方法、逐次拡大ＯＥＦ法，  円分拡大による方法などが知られている。
【０００５】
ＯＥＦによる方法とは，  非特許文献１に記載されている方法である．
逐次拡大ＯＥＦ法とは，  非特許文献２に記載されている方法である。
【０００６】
円分拡大による方法とは、非特許文献３に記載されている方法である。
【０００７】
まずＯＥＦによる方法を説明する。定義体の素体からの拡大次数をｍとすると、定義体の元は素体の元ｍ個の列と見做す事ができる。情報処理装置の処理するワード長をｕとする。ＯＥＦにおいては、定義体の位数ｐは２ｕ以下で，  しかも位数は２ｕに近い値でなければならない。さらに、定義体の定義多項式は、ある整数ｗで
Ｘｍ−ｗの形で  書けるものを用いる。整数ｗの絶対値が小さければ小さいほど演算は高速である。
【０００８】
ＯＥＦによる方法における乗算および逆元演算を説明する。例えば上記ワード長が３２（３２ビット情報処理装置）で、拡大次数ｍが７であったとする。
定義体の位数ｐのビット数は３２以下である。また、Ｚ／ｐＺの元は１ワードで書くことができる。定義体の元Ａを任意に取るとき、Ａは、Ｚ／ｐＺの元ａ０、ａ１、ａ２、ａ３、ａ４、ａ５、ａ６を用いて、
ａ０＋ａ１Ｘ＋ａ２Ｘ２＋ａ３Ｘ３＋ａ４Ｘ４＋ａ５Ｘ５＋ａ６Ｘ６と表現することができる。定義体のもう一つの元Ｂをｂ０＋ｂ１Ｘ＋ｂ２Ｘ２＋ｂ３Ｘ３＋ｂ４Ｘ４＋ｂ５Ｘ５＋ｂ６Ｘ６とした時に、二つの要素の積ＡＢを求めるにはまず、二つの要素の多項式としての積を求める。結果は１２次の多項式で、Ｚ／ｐＺの要素ｃ０、ｃ１、ｃ２、ｃ３、ｃ４、ｃ５、ｃ６、ｃ７、ｃ８、ｃ９、ｃ１０、ｃ１１、ｃ１２を用いて、ｃ０＋ｃ１Ｘ＋ｃ２Ｘ２＋ｃ３Ｘ３＋ｃ４Ｘ４＋ｃ５Ｘ５＋ｃ６Ｘ６＋ｃ７Ｘ７＋ｃ９Ｘ８＋ｃ９Ｘ９＋ｃ１０Ｘ１０＋ｃ１１Ｘ１１＋ｃ１２Ｘ１２とあらわせる。
【０００９】
これを既約多項式Ｘ７−ｗを用いて、６次の多項式に落す。すなわち、７以上のｎに関して操作「ｃｎＸｎ→ｗｃｎＸｎ−７」を繰り返し、６次の多項式を得る。得られた６次式が拡大体上での二つの元Ａ、Ｂの積ＡＢである。
【００１０】
次に、逆元演算の方法を記述する。＾
まず、Ａ−１＝（Ａ（ｐ＾（ｍ−１）＋ｐ＾（ｍ−２）＋、、、＋ｐ＋１））−１Ａ（ｐ＾（ｍ−１）＋ｐ＾（ｍ−２）＋、、、＋Ｐ）であることが知られている．  最初にＡ（ｐ＾（ｍ−１）＋ｐ＾（ｍ−２）＋、、、＋Ｐ）を求める。
【００１１】
ＯＥＦにおいてはフロベニウス写像Ａ→Ａｐは簡単に計算できるので、この計算は高速に行うことができる。
【００１２】
具体的には、
Ａ（ｐ＾（ｍ−１）＋ｐ＾（ｍ−２）＋、、、＋Ｐ）＝（．．．（（ＡｐＡ）ｐＡ）．．．）ｐである事を用いて、フロベニウス写像とＡとの積を取る演算とを交互に用いることで値を計算する。次にこれにＡを乗じてＡ（ｐ＾（ｍ−１）＋ｐ＾（ｍ−２）＋、、、＋ｐ＋１）を求める。この値は素体の元なので、基礎体上での逆元を計算すれば良い。
【００１３】
ＯＥＦを用いることの第一の利点は、多項式の積を求める上述の計算が、情報処理装置の処理するワード長に収まる数どうしの積と和とで可能なため、多倍長演算が不要となり、ソフトウェア実装の場合高速になる事である。
【００１４】
第二の利点は、１２次の多項式を６次に落す際に、各Ｚ／ｐＺにｗという小さい値を乗じるだけで済む事である。これが拡大体と同程度の位数を持つ素体である場合は、同じ操作に対応する除算に必要な計算コストが非常に大きい。
【００１５】
第３の利点は、逆元の計算が容易なことである。素体上での逆元演算は、体が大きいとコストが非常に大きくなるが、ＯＥＦの場合拡大体の逆元を計算する時に必要な逆元演算は、小さな素体上での逆元演算だけである為、コストが少なくてすむ。
【００１６】
次に逐次拡大ＯＥＦによる方法を説明する。逐次拡大ＯＥＦによる方法は、ＯＥＦによる方法と同様の拡大を繰り返し適用して拡大した体を用いる。例として、２回拡大する場合を記述する。
【００１７】
まず有限体Ｋをひとつとり、その拡大体Ｍをとる。拡大体Ｍをさらに拡大したものを拡大体Ｌと呼ぶことにする。ＭのＫからの拡大次数をｎ’とし、ＬのＭからの拡大次数をｎとする。Ｌの元Ａを任意に取る。逐次拡大ＯＥＦで元Ａの逆元を求める方法を説明する。
【００１８】
ＯＥＦの場合と同様に
Ａ−１＝（Ａ（ｐ＾（ｎ−１）＋ｐ＾（ｎ−２）＋、、、＋ｐ＋１））−１Ａ（ｐ＾（ｎ−１）＋ｐ＾（ｎ−２）＋、、、＋Ｐ）である事を利用する。
ここで、Ｂ＝Ａ（ｐ＾（ｎ−１）＋ｐ＾（ｎ−２）＋、、、＋ｐ＋１）とするとＢはＭの要素である。
するとまた、
Ｂ−１＝（Ｂ（ｐ＾（ｎ’−１）＋ｐ＾（ｎ’−２）＋、、、＋ｐ＋１））−１Ｂ（ｐ＾（ｎ’−１）＋ｐ＾（ｎ’−２）＋、、、＋ｐ）がなり立つ。
【００１９】
ここでＣ＝Ｂ（ｐ＾（ｎ’−１）＋ｐ＾（ｎ’−２）＋、、、＋ｐ＋１）とおくと、Ｃは基礎体Ｋの要素である。よってＡ−１＝Ａ（ｐ＾（ｎ−１）＋ｐ＾（ｎ−２）＋、、、＋ｐ）Ｂ（ｐ＾（ｎ’−１）＋ｐ＾（ｎ’−２）＋、、、＋ｐ）Ｃ−１である。
【００２０】
この等式を用いてＡ−１を求める。拡大の回数が２より大きい場合は、同様の手法を各拡大体に対して順次繰り返せば良い．
逐次拡大ＯＥＦ  による方法を用いることの利点を上記例で説明する．
等式Ａ−１＝Ａ（ｐ＾（ｎ−１）＋ｐ＾（ｎ−２）＋、、、＋ｐ）Ｂ（ｐ＾（ｎ’−１）＋ｐ＾（ｎ’−２）＋、、、＋ｐ）Ｃ−１を用いて、式Ａ−１を求める場合、右辺の計算において、Ａを乗じる演算は、体Ｌ上の演算であるが、Ｂを乗じる演算は体Ｍ上の演算である。体Ｍは体Ｌより小さいので、後者の演算はより効率的に行える。ＯＥＦによる方法におけるｍと、本方法におけるｎ，ｎ’の間に、ｍ＝ｎｎ’の関係があるとする。これは、暗号にこれらの体を用いた時に、暗号に同程度の強度を持たせるためには適切な仮定である。
【００２１】
ＯＥＦで用いられる拡大体をＬ’とする。逆元演算のために必要な演算は、ＯＥＦの場合体Ｌ’上の乗算がｍ個と素体上の逆元演算、逐次拡大ＯＥＦの場合体Ｌ上の乗算はｎ個、体Ｍ上の乗算がｎ’個と基礎体上の逆元演算である．  体Ｌ上の乗算と体Ｌ’上の乗算にかかるコストはほぼ同じであるので、全体として逐次拡大ＯＥＦの方が演算コストが低い。但し、逐次拡大ＯＥＦは体の拡大次数がｎｎ’と書けるため、拡大次数は合成数である必要がある。
【００２２】
最後に円分拡大を用いる方法を説明する。有限体Ｋに対し、Ｋ上の多項式で、１の原始ｍ乗根およびそれのみを根とするものを、Ｋ上の第ｍ円分多項式と呼ぶことにする。Ｋが１の原始ｍ乗根を含まないことがＫ上のｍ次の円分多項式が既約であるための必用十分条件である。円分拡大を用いる方法では、ＯＥＦとほぼ同等の効果に加えて、フロベニウス写像がより高速であることが期待できる。但し、選択できる拡大体は、拡大次数が素数より１小さいものに限られている。
【００２３】
【特許文献１】
特開２０００−２１４７６８（４−４、図１）
【非特許文献１】
ダニエル（Ｄａｎｉｅｌ  Ｖ．）、ベイリー（Ｂａｉｌｅｙ）、パー（Ｃｈｒｉｓｔｏｆ  Ｐａａｒ）による文献「オプティマル  イクステンション  フィールド  フォー  ファスト  アリスメティック  イン  パブリックキー  アルゴリズムズ。クリプト９８、シュプリンガー  レクチャーノート  イン  コンピューター  サイエン  ス、１９９６年（Ｏｐｔｉｍａｌ  Ｅｘｔｅｎｓｉｏｎ  Ｆｉｅｌｄｓ  ｆｏｒ  Ｆａｓｔ  Ａｒｉｔｈｍｅｔｉｃ  ｉｎ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ａｌｇｏｒｉｔｈｍｓ，  ＣＲＹＰＴＯ’９８．  Ｓｐｒｉｎｇｅｒ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｓ，  １９９６．）」
【非特許文献２】
小林鉄太郎  青木和麻呂、星野文学による文献「逐次拡大ＯＥＦ，  ＳＣＩＳ２０００−Ｂ０２」
【非特許文献３】
柳澤重  毅  松尾和人  趙  晋輝  辻井重男による文献「楕円暗号のハードウェア実装，  ＳＣＩＳ’９８−１０．１．Ｃ．」
【００２４】
【発明が解決しようとする課題】
２００３年現在、多くのコンピューターが３２ビットＣＰＵを使っている。
【００２５】
その為、楕円曲線暗号を高速にソフトウエア実装するためには、その演算の単位が３２ビット以下で、その値が２３２に近いものであることが望ましい。また同現在，  楕円曲線暗号の安全定数のビット数の標準は１６０ビットである。これは、用いる体の位数が２１６０−１以上であることを要求している。もし、３２ビット程度の素体を選んだ場合、その拡大体の位数が上記値であるためには、拡大次数は５または６である必要がある。拡大次数が５であるためには基礎体のビット数は丁度３２（＝１６０／５）である必要がある。拡大次数が６であるならば、基礎体のビット数は２７（＞１６０／６）ビット以上であれば良い。
【００２６】
従来の技術では、フロベニウス写像を高速化するためには、体の拡大は円分多項式で行うことが好ましく、乗算を少しでも小さな体で行うためには逐次拡大が好ましいことが結論される。ところが、拡大次数として５を選んだ場合、５は素数であるので逐次拡大とはなり得ず、５＋１は素数でもないので円分多項式による拡大も行えない。また、拡大次数として６を選んだ場合、６＝２ｘ３であるので逐次拡大とすることはできるが、３＋１が合成数なので４次の拡大は円分多項式による拡大とはできない。
【００２７】
本発明は、いかなる拡大次数の拡大体でも円分多項式を用いる拡大を応用して、拡大体のフロベニウス写像を高速に演算することを可能にし、またその拡大次数が合成数の場合、逐次拡大の長所もあわせ持たせることを可能にする逆元演算装置、逆元演算方法、及び逆元演算プログラムを提供するものである。
【００２８】
【課題を解決するための手段】
本発明の第１の逆元演算装置は、有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算装置であって、
外部からの入力データを受け付ける入力部と、前記入力データの数値から約数列を決定する約数列算出部と、前記約数列算出部から前記約数を逐次入力して共役元積とノルムとを計算し前記約数列算出部に返却する共役元積ノルム計算部と、前記約数列算出部から入力した共役元積とノルムとから逆元を計算する逆元計算部と、前記逆元計算部で計算した逆元を出力する出力部とを備え、
前記入力部は、前記基礎体Ｋを拡大して前記拡大体Ｍを求める任意の拡大次数ｎ（ｎは自然数）と、ｑ＝ｎ・ｊ＋１が素数となるようなｑ（ｊは小さい自然数）と、ｑ次の円分分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）が素体Ｚ／ｐＺ上で既約となるような素数ｐであって、その素数ｐを情報処理装置上の数値として表現した場合の有効ビット数が情報処理装置の処理するワード長以下でかつそれに近いビット数、ワード長の半分以下でかつそれに近いビット数，  およびワード長の２倍以下でかつそれに近いビット数のいずれかの条件をもつ素数ｐと、
素体Ｚ／ｐＺを拡大して基礎体Ｋを得るための既約多項式と、を入力し、
素数ｐと既約多項式をもとに基礎体Ｋを生成し、基礎体Ｋをｎによって拡大して拡大体Ｍ、基礎体Ｋをｑ次の円分多項式で拡大して拡大体Ｌを決定し、前記拡大体Ｍの元で逆元の演算を行う元Ａを入力し、
前記約数列算出部は、ｎの約数ｎ［１］、・・・ｎ［ｋ］  について、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるような約数列を選び、位数が基礎体Ｋのｎ［ｉ］乗であるＬの部分体をＮ［ｉ］  とし、ｎ［０］＝１、ｎ［ｋ＋１］＝ｎ、Ｎ［０］＝Ｋ、Ｎ［ｋ＋１］＝Ｍ、Ａ［ｋ＋１］＝Ａとした時、ｎの約数ｎ［ｉ］、ｎ［ｉ＋１］と、Ａ［ｉ］とをｉがｋから始まり１になるまで逐次前記共役元積ノルム算出部に提供し、結果として前記共役元積ノルム算出部から返却された共役元積Ａ［ｉ］  ＊を記憶し、
前記共役元積ノルム算出部は、約数ｎ［ｉ］  、ｎ［ｉ＋１］と、Ａ［ｉ］を用い、
Ｎ［ｉ−１］に関するＡ［ｉ］を除くＡ［ｉ］の共役元全ての積Ａ［ｉ］  ＊を、
Ａ［ｉ］＊＝Ａ［ｉ］＾｛ｐｎ［ｉ−１］＋ｐ２ｎ［ｉ−１］＋・・・＋ｐｎ［ｉ］−ｎ［ｉ−１］｝＝（・・・（（Ａ［ｉ］＾（ｐｎ［ｉ−１］）Ａ［ｉ］）＾（ｐｎ［ｉ−１］）Ａ［ｉ］）・・・）＾（ｐｎ［ｉ−１］）、と計算し、
ノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を、
ＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）＝Ａ［ｉ］Ａ［ｉ］＊、として計算し、このノルムを
新たにＡ［ｉ−１］とし共役元積Ａ［ｉ］＊とともに前記約数列算出部に返却し、
前記逆元算出部は、前記約数列算出部の記憶する共役元積全てと、
前記約数列算出部が最後に呼び出した時の前記共役元積ノルム算出部が出力したノルムの逆元Ａ［０］−１との積を、
Ａ−１＝Ａ［ｋ＋１］＊Ａ［ｋ］＊・・・Ａ［１］＊Ａ［０］−１として計算し、
前記出力部は、前記逆元計算部の計算結果を出力する、
ことを備える。
【００２９】
本発明の第１の逆元演算方法は、有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算方法であって、
ある素数ｑがあって１の原始ｑ乗根のみを根とする前記基礎体Ｋについて既約な多項式を定義多項式として用いて前記基礎体Ｋを拡大した拡大体Ｌを得る第１のステップと、
前記基礎体Ｋと前記拡大体Ｌとの間の所与の拡大次数ｎで前記基礎体Ｋを拡大した拡大体Ｍを求める第２のステップと、
前記拡大体Ｍの元の逆元を前記拡大体Ｌにおけるフロベニウス写像を用いて求める第３のステップと、
を備え、
前記ｑは、前記中間体の拡大次数ｎの整数倍に１を足した素数であることを備える。
【００３０】
本発明の第２の逆元演算方法は、有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算方法であって、任意の基礎体とその任意拡大次数ｎの拡大体Ｍがあったとき、前記拡大次数ｎの整数倍に１を足した素数ｑによって得られるｑ次円分多項式により前記基礎体を拡大した拡大体Ｌを求め、前記拡大体Ｍにおけるフロベニウス写像が拡大体Ｌにおけるフロベニウス写像から自然に得られることを利用して逆元を求めることを備える。
【００３１】
本発明の第３の逆元演算方法は、第２の発明において、前記拡大体Ｍの元Ａの逆元を求めるにあたり、前記拡大体Ｍと前記基礎体Ｋとの間で前記拡大次数ｎの任意の約数ｎ［１］、・・・ｎ［ｋ］  を、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるよう選び、
位数が（＃Ｋ）ｎ［ｉ］である部分体をＮ［ｉ］  としたとき、
Ｋ＝Ｎ［０］⊂Ｎ［１］⊂・・・Ｎ［ｋ］⊂Ｎ［ｋ＋１］＝Ｍであって、
最初にＭの直下の部分体Ｎ［ｋ］に関するＡの全ての共役元の積とノルムをもとめ、これを基礎体Ｋに達するまで繰り返し計算することにより逆元を求めることを備える。
【００３２】
本発明の第４の逆元演算方法は、有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算方法であって、
前記拡大体Ｍの拡大次数ｎと、
ｑ＝ｎ・ｊ＋１（ｊは小さな自然数）で得られる素数ｑと、
ｑ次円分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）が素体Ｚ／ｐＺ上で既約となるような素数ｐであって、その素数ｐを情報処理装置上の数値として表現した場合の有効ビット数が情報処理装置の処理するワード長以下で、かつそれに近いビット数、ワード長の半分以下でかつそれに近いビット数，  およびワード長の２倍以下でかつそれに近いビット数、のいずれかの条件をもつ素数ｐと、
素体Ｚ／ｐＺを拡大して前記基礎体Ｋを得るための既約多項式と、
前記拡大体中の逆元を求める元Ａを入力する第１のステップと、
前記拡大次数ｎの任意の約数ｎ［１］、・・・ｎ［ｋ］  について、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるような約数列を選ぶ第２のステップと、
前記拡大体Ｍと前記基礎体Ｋの間にあって位数が（＃Ｋ）ｎ［ｉ］である中間体列を求める第３のステップと、
前記中間体列の前記拡大体Ｍ直下の中間体に関する元Ａの共役元で自分自身以外のものを全てかけあわせた共役元積を求めこれを記憶する第４のステップと、
前記共役元積と元Ａを掛け合わせてＡのノルムを計算してこれをＡ’とする第５のステップと、
前記第５のステップのＡ’について前記中間体列でＭから１段下げてシフトした中間体について前記第４のステップと第５のステップを実行し、同様にして前記ノルムが前記基礎体Ｋの元になるまでこれを有限回繰り返す第６のステップと、
基礎体についてのノルムの逆元を求め、前記第４のステップで記憶する全ての中間体列に関する共役元積との積を計算してこれをＡの逆元とする第７のステップと、
を備える。
【００３３】
本発明の第５の逆元演算方法は、２７ビット以上３２ビット以下の素数を標数とし１の原始７乗根を含まない素体に１の原始７乗根を付加して拡大した６次拡大体の元の逆元を計算する逆元演算方法であって，
前記６次拡大体の元で逆元を求める元が入力される第１のステップと、
前記素体の３次拡大体Ｎ［１］を求める第２のステップと、
元Ａの前記３次拡大体Ｎ［１］についての共役元全ての積を第一共役元積として計算する第３のステップと、
前記第一共役元積に元Ａをかけあわせた第一ノルムを計算する第４のステップと、
前記第一ノルムの前記素体についての共役元すべての積を第二共役元積として計算する第５のステップと、
前記第二共役元積に前記第一ノルムをかけあわせた第二ノルムを計算する第６のステップと、
第二ノルムの逆元を計算する第７のステップと、
第二ノルムの逆元と第二共役元積と第一共役元積とをかけあわせてＡの逆元を計算する第８のステップと、
Ａの逆元を出力する第９のステップと、
を備える。
【００３４】
本発明の第６の逆元演算方法は、第５の発明において、前記素体の元は情報処理装置において１ワードとして処理され、前記６次拡大体の元は６ワードとして処理されることを備える。
【００３５】
本発明の第７の逆元演算方法は、有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算方法であって、
前記基礎体Ｋを拡大して前記拡大体Ｍを求める任意の拡大次数ｎ（ｎは自然数）と、
ｑ＝ｎ・ｊ＋１が素数となるようなｑ（ｊは小さい自然数）と、
ｑ次の円分分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）が素体Ｚ／ｐＺ上で既約となるような素数ｐであって、その素数ｐを情報処理装置上の数値として表現した場合の有効ビット数が情報処理装置の処理するワード長以下でかつそれに近いビット数、ワード長の半分以下でかつそれに近いビット数，  およびワード長の２倍以下でかつそれに近いビット数のいずれかの条件をもつ素数ｐと、
素体Ｚ／ｐＺを拡大して基礎体Ｋを得るための既約多項式と、
を入力する第１のステップと、
素体Ｚ／ｐＺ上の既約多項式を一つ選び、この既約多項式でＺ／ｐＺを拡大して得られる体を前記基礎体Ｋとし、既約多項式として一次式が選ばれた場合にはＫ＝Ｚ／ｐＺとするとともに、基礎体Ｋをｑ次の円分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）で拡大した体を拡大体Ｌとする時、拡大体Ｌの中間体Ｍとして
ｊ＝１の場合はＭとしてＬ自身をとり、ｊ＞１の場合は、位数がｐｎのものをＭとし、逆元を計算する対象のＭの元Ａを入力する第２のステップと、
ｎの任意の約数ｎ［１］、・・・ｎ［ｋ］  について、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるような約数列を選び、位数が（＃Ｋ）ｎ［ｉ］であるＬの部分体をＮ［ｉ］  とし、ｎ［０］＝１、Ｎ［０］＝Ｋ、Ｎ［ｋ＋１］＝Ｍ、Ａ［ｋ＋１］＝Ａとする第３のステップと、
Ｎ［ｉ］の要素Ａ［ｉ］  について、Ｎ［ｉ−１］に関する共役元全ての積Ａ［ｉ］  ＊を、
Ａ［ｉ］＊＝Ａ［ｉ］＾｛ｐｎ［ｉ−１］＋ｐ２ｎ［ｉ−１］＋・・・＋ｐｎ［ｉ］−ｎ［ｉ−１］｝＝（・・・（（Ａ［ｉ］＾（ｐｎ［ｉ−１］）Ａ［ｉ］）＾（ｐｎ［ｉ−１］）Ａ［ｉ］）・・・）＾（ｐｎ［ｉ−１］）と計算して記憶する第４のステップと、
ノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を、
ＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）＝Ａ［ｉ］Ａ［ｉ］＊と計算し、このノルムを新たにＡ［ｉ−１］とする第５のステップと、
ｉ＝ｋ＋１の拡大体Ｍの元Ａから１の基礎体Ｋまで順に、Ａ［ｉ］を入力し、
Ａ［ｉ］＊及びノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を得る第６のステップと、
ＮＮ［１］／Ｎ［０］（Ａ［１］）の逆元を求め、これをＡ［０］−１とする第７のステップと、
第４のステップで記憶したＡ［ｉ］＊と第７のステップのＡ［０］−１から
Ａ−１＝Ａ［ｋ＋１］＊Ａ［ｋ］＊・・・Ａ［１］＊Ａ［０］−１としてＡの逆元を得る第８のステップと、
を備える。
【００３６】
本発明の第１の逆元演算プログラムは、有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算処理をコンピュータに実行させる逆元演算プログラムであって、
ある素数ｑがあって１の原始ｑ乗根のみを根とし前記基礎体Ｋについて既約な多項式を定義多項式として用いて前記基礎体Ｋを拡大した拡大体Ｌを得る機能と、前記基礎体Ｋと前記拡大体Ｌとの間の所与の数値ｎで前記基礎体Ｋを拡大した拡大体Ｍを求める機能と、
前記拡大体Ｍの元の逆元を前記拡大体Ｌにおけるフロベニウス写像を用いて求める機能と、
を備え、
前記ｑは、前記中間体の拡大次数ｎの整数倍に１を足した素数であることを備える。
【００３７】
本発明の第２の逆元演算プログラムは、有限体の基礎体Ｋを拡大した拡大体Ｍの元に対する逆元を求める逆元演算処理をコンピュータに実行させる逆元演算プログラムであって、
前記基礎体Ｋを拡大して前記拡大体Ｍを求める任意の拡大次数ｎ（ｎは自然数）と、
ｑ＝ｎ・ｊ＋１が素数となるようなｑ（ｊは小さい自然数）と、
ｑ次の円分分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）が素体Ｚ／ｐＺ上で既約となるような素数ｐであって、その素数ｐを情報処理装置上の数値として表現した場合の有効ビット数が情報処理装置の処理するワード長以下でかつそれに近いビット数、ワード長の半分以下でかつそれに近いビット数，  およびワード長の２倍以下でかつそれに近いビット数のいずれかの条件をもつ素数ｐと、
素体Ｚ／ｐＺを拡大して基礎体Ｋを得るための既約多項式と、
を入力する機能と、
素体Ｚ／ｐＺ上の既約多項式を一つ選び、この既約多項式でＺ／ｐＺを拡大して得られる体を前記基礎体Ｋとし、既約多項式として一次式が選ばれた場合にはＫ＝Ｚ／ｐＺとするとともに、基礎体Ｋをｑ次の円分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）で拡大した体を拡大体Ｌとする時、拡大体Ｌの中間体Ｍとして
ｊ＝１の場合はＭとしてＬ自身をとり、ｊ＞１の場合は、位数がｐｎのものをＭとし、逆元を計算する対象のＭの元Ａを入力する機能と、
ｎの任意の約数ｎ［１］、・・・ｎ［ｋ］  について、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるような約数列を選び、位数が（＃Ｋ）ｎ［ｉ］であるＬの部分体をＮ［ｉ］  とし、ｎ［０］＝１、Ｎ［０］＝Ｋ、Ｎ［ｋ＋１］＝Ｍ、Ａ［ｋ＋１］＝Ａとする機能と、
Ｎ［ｉ］の要素Ａ［ｉ］  について、Ｎ［ｉ−１］に関する共役元全ての積Ａ［ｉ］  ＊を、
Ａ［ｉ］＊＝Ａ［ｉ］＾｛ｐｎ［ｉ−１］＋ｐ２ｎ［ｉ−１］＋・・・＋ｐｎ［ｉ］−ｎ［ｉ−１］｝＝（・・・（（Ａ［ｉ］＾（ｐｎ［ｉ−１］）Ａ［ｉ］）＾（ｐｎ［ｉ−１］）Ａ［ｉ］）・・・）＾（ｐｎ［ｉ−１］）と計算して記憶する機能と、
ノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を、
ＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）＝Ａ［ｉ］Ａ［ｉ］＊と計算し、このノルムを新たにＡ［ｉ−１］とする機能と、
ｉ＝ｋ＋１の拡大体Ｍの元Ａから１の基礎体Ｋまで順に、Ａ［ｉ］を入力し、
Ａ［ｉ］＊及びノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を得る機能と、
ＮＮ［１］／Ｎ［０］（Ａ［１］）の逆元を求め、これをＡ［０］−１とする機能と、
第４のステップで記憶したＡ［ｉ］＊と第７のステップのＡ［０］−１から
Ａ−１＝Ａ［ｋ＋１］＊Ａ［ｋ］＊・・・Ａ［１］＊Ａ［０］−１としてＡの逆元を得る機能と、
を備える。
【００３８】
【発明の実施の形態】
本発明の実施の形態の構成を図１を参照して説明する。
【００３９】
本発明の実施の形態の構成は、共通鍵暗号等で使用する暗号鍵を生成する情報処理装置である暗号鍵生成装置１と、暗号鍵生成装置１と同じ構成をもつ暗号鍵生成装置２と、暗号鍵生成装置１と暗号鍵生成装置２とを接続するインターネットを含むネットワーク３と、から構成される。
【００４０】
さらに、暗号鍵生成装置１と暗号鍵生成装置２とは、キーボード等の入力手段１０と、暗号鍵生成のため楕円曲線の演算を行う暗号鍵演算装置１１と、ディスプレイやプリンタを含む出力手段１２と、暗号鍵の生成を行うソフトウェアプログラムを格納する磁気ディスク装置等の二次記憶装置１３と、から構成されている。
【００４１】
さらに、暗号鍵演算装置１１は、６４ビットアーキテクチャ、３２ビットアーキテクチャ等で設計されたＣＰＵ１１０と、予め固定された数値データ等の不揮発性データを記憶するＲＯＭ１１１と、二次記憶装置１３からロードした演算処理のプログラムを記憶するＲＡＭ１１２と、二次記憶装置１３との入出力を制御するＩＯポート１１３と、から構成されている。
【００４２】
次に、本発明の実施の形態の動作時におけるソフトウェアの構成について図２をもとに説明すると、外部からの入力データを入力手段１１によって受け付ける入力部４１と、前記入力データの数値から約数列を決定する約数列算出部４２と、前記約数列算出部から前記約数を逐次入力して共役元積とノルムとを計算し前記約数算出部４２に返却する共役元積ノルム計算部４３と、前記約数列算出部４２から入力した共役元積とノルムとから逆元を計算する逆元計算部４４と、前記逆元計算部４４で計算した逆元を出力手段１２等に出力する出力部４５とを備えている。
【００４３】
尚、本実施の形態は、共通鍵暗号処理における逆元の演算を例として説明するが、本発明は、これに限られるものでないことは明瞭である。
【００４４】
次に、本発明の実施の形態の動作について図３と図４のフローチャートを元に説明する。
【００４５】
暗号鍵生成装置１，２は、ネットワーク３を介して情報を交換して暗号鍵生成装置１，２の間で共有する共通暗号鍵の生成を行う。暗号鍵生成装置１、２の管理者は、暗号鍵演算装置１１のもつアーキテクチャに従って処理されるワード長以下でかつそれに近い素数ｐの持つビット数｜ｐ｜及びｐによる素体Ｚ／ｐＺによる基礎体Ｋに対する任意の拡大次数ｎ等を入力手段１０から入力する。これらの入力から楕円曲線を定義する体を決定する。
［体の選び方］
まずワード長倍数ζを１、１／２、または２とし、そこからζを選択する。ワード長倍数ζが１か１／２か２かに応じて、情報処理装置の処理するワード長以下でかつそれに近い素数ｐのビット数、ワード長の半分以下でかつそれに近い素数ｐのビット数，  およびワード長の２倍以下でかつそれに近い素数ｐのビット数｜ｐ｜のいずれかが入力手段１０から与えられるとする。
【００４６】
さらに任意の拡大次数ｎが与えられたとする（ステップ１０１）。尚、一旦入力された数値は、ＲＯＭ１１１に記憶し、以降はＲＯＭ１１１に記憶した数値を取り込むようにしてもよい。
【００４７】
ｊを、ｑ＝ｎ・ｊ＋１が素数となるような整数とする（ステップ１０２）。
（なおｊは小さい方がより好ましい。）
ｑ分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）が素体Ｚ／ｐＺ上で既約となるような素数ｐでかつｐのビット数が与えられたビット数に一致するようなｐを選ぶ。  さらに、素体Ｚ／ｐＺ上の既約多項式を一つ選び、この既約多項式でＺ／ｐＺを拡大して得られる体を基礎体として固定する（ステップ１０３）。以後この基礎体をＫと書く。  なお既約多項式として一次式が選ばれた場合にはＫ＝Ｚ／ｐＺとする。基礎体Ｋをｑ分多項式で拡大した体をＬとする。
【００４８】
ここで、ｑ分多項式はｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１となる。ｊ＝１の場合はＭとしてＬ自身をとる。ｊ＞１の場合は、Ｌの中間体で位数がｐｎのものをＭとする（ステップ１０４）。尚、ｑ分多項式の数値ｑ及び既約多項式も入力手段１０から入力されるものとする。
【００４９】
以上説明した本発明の逆元演算に関する所与の条件を整理すると、
（１）任意の拡大次数ｎ（ｎは自然数）
（２）ｑ＝ｎ・ｊ＋１が素数となるようなｑ
（３）ｑ分多項式（ｘｑ−１＋ｘｑ−２＋・・・＋ｘ＋１）が素体Ｚ／ｐＺ上で既約となるような素数ｐであって、その素数ｐを情報処理装置上の数値として表現した場合の有効ビット数が情報処理装置の処理するワード長以下でかつそれに近いビット数、ワード長の半分以下でかつそれに近いビット数，  およびワード長の２倍以下でかつそれに近いビット数のいずれかの条件をもつ素数ｐ
（４）素体Ｚ／ｐＺを拡大して基礎体Ｋを得るための既約多項式
となる。
【００５０】
以上の前提のもとに暗号鍵の生成処理に必要な処理プログラムが、暗号鍵演算装置１１の図示しないオペレーティングシステムによって二次記憶装置１３から読み出され、ＲＡＭ１１２に配置されて実行が開始される。この暗号鍵の生成における楕円曲線の演算にあたり、ある数値について上記体の逆元の計算が必要となった場合、暗号鍵の生成を行う本体から逆元を求める対象となる数値を引数として本発明に関する逆元演算処理の呼び出しが行われ、逆元が演算の結果として生成されると、呼び出し元にこの逆元が返却されるようになっている。
［逆元演算方法］
［準備（１）（体Ｋの２つの元の積の計算）］
Ｋの要素（ａ１、ａ２、、、、ａｑ−１）  及び（ｂ１、ｂ２、、、ｂｑ−１）を用いてあらわされる体Ｌの要素Ａ＝ａ１ｘ＋ａ２ｘ２＋・・・＋ａｑ−１ｘｑ−１、及びＢ＝ｂ１ｘ＋ｂ２ｘ２＋・・・ｂｑ−１ｘｑ−１の積は、多項式ＡＢの積を求めた後、ｑ分多項式による同値関係を用いて、一意にｃ１ｘ＋ｃ２ｘ２＋・・・ｃｑ−１ｘｑ−１とあらわすことができる。但し、（ｃ１、ｃ２、、、、ｃｑ−１）はＺ／ｐＺの要素である。
［準備（２）（体Ｌ上の演算）］
体Ｌの任意の元ｗは、ｑ−１個のＫの元ａ１、ａ２、、、、ａｑ−１を用いて、
ｗ＝ａ１ｘ＋ａ２ｘ２＋・・・＋ａｑ−１ｘｑ−１とあらわすことができる。
【００５１】
以下、ａ１ｘ＋ａ２ｘ２＋・・・＋ａｑ−１ｘｑ−１を略して（ａ１、ａ２、、、、ａｑ−１）とも書くことにする。
【００５２】
この要素のフロベニウス写像φによるφ（ｗ）は、
φ（ｗ）＝（ａ’１、ａ’２、、、、ａ’ｑ−１）と表すことができる。
但し、ａ’ｉｐ ｍｏｄ ｑ＝ａｉ
［準備（３）（体Ｍ上の演算）］
体Ｍは体Ｌに埋め込まれているため、体Ｍの要素に対するフロベニウス写像は、体Ｌの要素に対するフロベニウス写像と同様に計算できる。
【００５３】
また、同様に体Ｍの要素の積も計算できる。
【００５４】
この時、体Ｍは体Ｌより位数が小さいので、ｑ−１個のＺ／ｐＺの要素（ａ１、ａ２、、、、ａｑ−１）の中には、高々ｎ個しか異なる値を含まない。これを利用すると、体Ｍの要素間の積は体Ｌのそれより簡単に計算できる。
［逆元演算］
前記［体の選び方］に記述した様に選ばれた体Ｌ，Ｍ，Ｋ，Ｚ／ｐＺ及びｎ、ｑがあるとする。そして、逆元演算対象として体Ｍの要素Ａが入力されたとする（ステップ２０１）。
【００５５】
ｎの任意の約数ｎ［１］、・・・ｎ［ｋ］  を、ｎ［ｉ］  がｎ［ｉ＋１］を割りきるよう複数選ぶ（ステップ２０２）。
【００５６】
位数が（＃Ｋ）ｎ［ｉ］（Ｋの位数のｎ［ｉ］乗）で、拡大体Ｌの部分体をＮ［ｉ］  と呼ぶことにする（ステップ２０３）。
【００５７】
また、ｎ［０］＝１、Ｎ［０］＝Ｋ、Ｎ［ｋ＋１］＝Ｍ、Ａ［ｋ＋１］＝Ａとする。
【００５８】
Ｎ［ｉ］の要素Ａ［ｉ］  が逐次入力されたとき、
Ｎ［ｉ−１］に関するＡ［ｉ］を除くＡ［ｉ］の共役元全ての積Ａ［ｉ］  ＊  及びノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）を、
Ａ［ｉ］＊＝Ａ［ｉ］＾｛ｐｎ［ｉ−１］＋ｐ２ｎ［ｉ−１］＋・・・＋ｐｎ［ｉ］−ｎ［ｉ−１］｝＝（・・・（（Ａ［ｉ］＾（ｐｎ［ｉ−１］）Ａ［ｉ］）＾（ｐｎ［ｉ−１］）Ａ［ｉ］）・・・）＾（ｐｎ［ｉ−１］）、
ＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）＝Ａ［ｉ］Ａ［ｉ］＊、と計算する。
【００５９】
共役元積生成方法を利用して以下の処理をする。
【００６０】
ここでＫ＝Ｎ［０］⊂Ｎ［１］⊂・・・⊂Ｎ［ｋ＋１］＝Ｍである。
ｉ＝ｋ＋１から１まで順に（ステップ２０６）、共役元積生成方法に  Ａ［ｉ］を入力し、Ａ［ｉ］＊（ステップ２０４）及びノルムＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）（ステップ２０５）を得、ＮＮ［ｉ］／Ｎ［ｉ−１］（Ａ［ｉ］）をＡ［ｉ−１］とする。
ＮＮ［１］／Ｎ［０］（Ａ［１］）の逆元を求め（ステップ２０７）これをＡ［０］−１とする．  Ａ−１＝Ａ［ｋ＋１］＊Ａ［ｋ］＊・・・Ａ［１］＊Ａ［０］−１とする（ステップ２０８）。これがＡの逆元である（ステップ２０９）。
【００６１】
［実施例（１）］
情報処理装置の処理ワード長が３２ビットであるとし、ワード長倍数ζ１で、拡大次数ｎが８となる拡大体Ｍを選び、この体上での逆元演算を行う方法を図３と図４のフローチャートを参照しながら説明する。
【００６２】
ワード長の数値３２と拡大次数の数値８が入力される（ステップ１０１）。
８＊２＋１＝１７が素数なのでｑ＝１７とする（ステップ１０２）。
【００６３】
第１７円分多項式Φ１７＝１＋ｘ＋ｘ２＋・・・＋ｘ１６がＺ／ｐＺ上既約となる素数ｐで  かつｐのビット長が３２以下３２に近いｐを選ぶ（ステップ１０３）。ここでは例としてｐ＝２２７−３９とする。
【００６４】
次にＺ／ｐＺ上の既約多項式を一つ選ぶ。ここでは一次式が選ばれたとする。よって基礎体ＫはＺ／ｐＺ自身である。Ｋを１７分多項式で拡大した体をＬとする。
Ｌの中間体でその位数がｐ８であるものをＭとする（ステップ１０４）。
【００６５】
Ｍの要素Ａは８個のＫの要素（ａ１，ａ２，・・・、ａ８）を用いて、
Ａ＝ａ１ｘ＋ａ２ｘ２＋・・・＋ａ７ｘ７＋ａ８ｘ８＋ａ８ｘ９＋ａ７ｘ１０＋・・・＋ａ２ｘ１５＋ａ１ｘ１６とあらわすことができる。
Ｍの要素Ａが入力される（ステップ２０１）。
（１）ＭのＫに対する拡大次数は８である。８の約数として２，４を選ぶ（２は４を割りきる）（ステップ２０２）。以下、Ｌの中間体で位数がｐ２であるものをＮ［１］，  位数がｐ４であるものをＮ［２］  とする（ステップ２０３）。
（２）ＡのＮ［２］に関する共役元全ての積Ａ＊を、
Ａ＊＝Ａ＾｛ｐ４｝  として計算する（ステップ２０４）。
【００６６】
これはフロベニウス写像を４回作用させたもので
φ４：Ａ→Ａ＾｛ｐ４｝は成分でかくと、
φ４：ａ１ｘ＋ａ２ｘ２＋ａ３ｘ３＋ａ４ｘ４＋ａ５ｘ５＋ａ６ｘ６＋ａ７ｘ７＋ａ８ｘ８＋ａ８ｘ９＋ａ７ｘ１０＋ａ６ｘ１１＋ａ５ｘ１２＋ａ４ｘ１３＋ａ３ｘ１４＋ａ２ｘ１５＋ａ１ｘ１６
→  ａ４ｘ＋ａ８ｘ２＋ａ５ｘ３＋ａ１ｘ４＋ａ３ｘ５＋ａ７ｘ６＋ａ６ｘ７＋ａ２ｘ８＋ａ２ｘ９＋ａ６ｘ１０＋ａ７ｘ１１＋ａ３ｘ１２＋ａ１ｘ１３＋ａ５ｘ１４＋ａ８ｘ１５＋ａ４ｘ１６
である。
（Ａを拡大体Ｌの要素と見ることで、フロベニウス写像が、単なるＫの要素の入れ替えとなっている。）
（３）ＡのＮ［２］に関するノルムＡ［２］を、
Ａ［２］＝Ａ・Ａ＊  ｍｏｄ  Φ１７として計算する（ステップ２０５）。
【００６７】
Ａ［２］の要素は４個のＫの要素（ｃ１、ｃ２、ｃ３、ｃ４）を用いて、
Ａ［２］＝ｃ１ｘ＋ｃ２ｘ２＋ｃ３ｘ３＋ｃ１ｘ４＋ｃ３ｘ５＋ｃ４ｘ６＋ｃ４ｘ７＋ｃ２ｘ８＋ｃ２ｘ９＋ｃ４ｘ１０＋ｃ４ｘ１１＋ｃ３ｘ１２＋ｃ１ｘ１３＋ｃ３ｘ１４＋ｃ２ｘ１５＋ｃ１ｘ１６
とあらわすことができる。
（４）Ｎ［２］に関する共役元、ノルムを計算したが、このＮ［２］は基礎体Ｋの元ではないので、再び共役元の積を求めるステップに行く（ステップ２０６）。
（５）Ａ［２］のＮ［１］に関する共役元全ての積Ａ［２］＊を、
Ａ［２］＊＝Ａ［２］＾｛ｐ２｝と計算する（ステップ２０４）。
【００６８】
これはフロベニウス写像を２回作用させたもので
Ａ［２］＾｛ｐ２｝＝φ２（Ａ［２］）を、成分でかくと、
φ２（ｃ１ｘ＋ｃ２ｘ２＋ｃ３ｘ３＋ｃ１ｘ４＋ｃ３ｘ５＋ｃ４ｘ６＋ｃ４ｘ７＋ｃ２ｘ８＋ｃ２ｘ９＋ｃ４ｘ１０＋ｃ４ｘ１１＋ｃ３ｘ１２＋ｃ１ｘ１３＋ｃ３ｘ１４＋ｃ２ｘ１５＋ｃ１ｘ１６）
＝ｃ２ｘ＋ｃ１ｘ２＋ｃ４ｘ３＋ｃ２ｘ４＋ｃ４ｘ５＋ｃ３ｘ６＋ｃ３ｘ７＋ｃ１ｘ８＋ｃ１ｘ９＋ｃ３ｘ１０＋ｃ３ｘ１１＋ｃ４ｘ１２＋ｃ２ｘ１３＋ｃ４ｘ１４＋ｃ１ｘ１５＋ｃ２ｘ１６
である。
（６）Ａ［２］のＮ［１］に関するノルムＡ［１］を、
Ａ［１］＝Ａ［２］・Ａ［２］＊  ｍｏｄ  Φ１７により計算する（ステップ２０５）。
Ａ［１］の要素は２個のＫの要素（ｄ１、ｄ２）を用いて、
Ａ［１］＝ｄ１ｘ＋ｄ１ｘ２＋ｄ２ｘ３＋ｄ１ｘ４＋ｄ２ｘ５＋ｄ２ｘ６＋ｄ２ｘ７＋ｄ１ｘ８＋ｄ１ｘ９＋ｄ２ｘ１０＋ｄ２ｘ１１＋ｄ２ｘ１２＋ｄ１ｘ１３＋ｄ２ｘ１４＋ｄ１ｘ１５＋ｄ１ｘ１６
とあらわすことができる。
（７）Ｎ［１］に関する共役元、ノルムを計算したが、このＮ［１］は基礎体Ｋの元ではないので、再び共役元の積を求めるステップに行く（ステップ２０６）。
（８）Ａ［１］のＫに関する共役元全ての積Ａ［１］＊を、
Ａ［１］＊＝Ａ［１］＾｛ｐ｝  と計算する（ステップ２０４）。
これはフロベニウス写像を１回作用させたもので、
φ（Ａ［１］）＝Ａ［１］＾｛ｐ｝は、成分でかくと、
φ（ｄ１ｘ＋ｄ１ｘ２＋ｄ２ｘ３＋ｄ１ｘ４＋ｄ２ｘ５＋ｄ２ｘ６＋ｄ２ｘ７＋ｄ１ｘ８＋ｄ１ｘ９＋ｄ２ｘ１０＋ｄ２ｘ１１＋ｄ２ｘ１２＋ｄ１ｘ１３＋ｄ２ｘ１４＋ｄ１ｘ１５＋ｄ１ｘ１６）
＝ｄ２ｘ＋ｄ２ｘ２＋ｄ１ｘ３＋ｄ２ｘ４＋ｄ１ｘ５＋ｄ１ｘ６＋ｄ１ｘ７＋ｄ２ｘ８＋ｄ２ｘ９＋ｄ１ｘ１０＋ｄ１ｘ１１＋ｄ１ｘ１２＋ｄ２ｘ１３＋ｄ１ｘ１４＋ｄ２ｘ１５＋ｄ２ｘ１６
である。
（９）Ａ［１］のＫに関するノルムＡ［０］を、
Ａ［０］＝Ａ［１］・Ａ［１］＊  ｍｏｄ  Φ１７を計算する（ステップ２０５）。
【００６９】
Ａ［０］の要素は１個のＫの要素（ｅ１）を用いて、
Ａ［０］＝ｅ１ｘ＋ｅ１ｘ２＋ｅ１ｘ３＋ｅ１ｘ４＋ｅ１ｘ５＋ｅ１ｘ６＋ｅ１ｘ７＋ｅ１ｘ８＋ｅ１ｘ９＋ｅ１ｘ１０＋ｅ１ｘ１１＋ｅ１ｘ１２＋ｅ１ｘ１３＋ｅ１ｘ１４＋ｅ１ｘ１５＋ｅ１ｘ１６
とあらわすことができる。
（１０）Ｋに関する共役元、ノルムを計算し終えたが、このＫは基礎体なので次の（ステップ２０７）に行く。
（１１）ｅ１の逆元  ｅ１−１を求める（ステップ２０７）。
（１２）Ａの逆元Ａ−１を、
Ａ−１＝ｅ１−１Ａ［１］＊Ａ［２］＊Ａ＊と計算する（ステップ２０８）。
最後にＡ−１を出力手段１２によって出力して終了する（ステップ２０９）。
【００７０】
［実施例（２）］
情報処理装置の処理ワード長が３２ビットであるとし、ワード長倍数ζが１で、拡大次数が６となる拡大体Ｍを選び、この体上での逆元演算を行う方法を図３と図４のフローチャートを参照しながら説明する。
ワード長（３２）と拡大次数（６）が入力される（ステップ１０１）。
６ｘ１＋１＝７が素数なので、ｑ＝７とする（ステップ１０２）。
【００７１】
７分多項式Φ７＝１＋ｘ＋ｘ２＋ｘ３＋ｘ４＋ｘ５＋ｘ６がＺ／ｐＺ上既約となる素数ｐで  かつｐのビット長が３２以下３２に近いｐを選ぶ（ステップ１０３）。
【００７２】
ここでは例としてｐ＝２２７−１１５とする。Ｚ／ｐＺ上の既約多項式を一つ選ぶ。ここでは既約多項式として一次式が選ばれたとする。よって基礎体ＫはＺ／ｐＺ自身である。
【００７３】
Ｋを７分多項式で拡大した体をＬとする。Ｌ自体をＭとする（ステップ１０４）。Ｍの要素Ａを選択すると、Ａは６個のＫの要素  （ａ１、ａ２、ａ３、ａ４、ａ５、ａ６）を用いて、
Ａ＝ａ１ｘ＋ａ２ｘ２＋ａ３ｘ３＋ａ４ｘ４＋ａ５ｘ５＋ａ６ｘ６とあらわすことができる。
Ｍの要素  Ａが入力される（ステップ２０１）。
（１）ＭのＫに対する拡大次数は６である。６の約数として３を選ぶ。以下、Ｌの中間体で位数がｐ３であるものをＮ［１］とする（ステップ２０３）。
（２）ＡのＮ［１］に関する共役元全ての積Ａ＊を、
Ａ＊＝Ａ＾｛ｐ３｝  として計算する（ステップ２０４）。
これはフロベニウス写像を３回作用させたもので
φ３（Ａ）＝Ａ＾｛ｐ３｝を成分でかくと、
φ３（ａ１ｘ＋ａ２ｘ２＋ａ３ｘ３＋ａ４ｘ４＋ａ５ｘ５＋ａ６ｘ６）＝ａ６ｘ＋ａ５ｘ２＋ａ４ｘ３＋ａ３ｘ４＋ａ２ｘ５＋ａ１ｘ６である。
（３）ＡのＮ［１］に関するノルムＡ［１］を、
Ａ［１］＝Ａ・Ａ＊  ｍｏｄ  Φ７を計算する（ステップ２０５）。
Ａ［１］  の要素は３個のＫの要素（ｃ１、ｃ２、ｃ３）を用いて、
Ａ［１］＝ｃ１ｘ＋ｃ２ｘ２＋ｃ３ｘ３＋ｃ３ｘ４＋ｃ２ｘ５＋ｃ１ｘ６
とあらわすことができる。
（４）Ｎ［１］に関する共役元、ノルムを計算したが、このＮ［１］  は基礎体Ｋではないので、再び共役元の積を求めるステップに行く（ステップ２０６）。
（５）Ａ［１］のＫに関する共役元全ての積Ａ［１］＊を、
Ａ［１］＊＝Ａ［１］＾｛ｐ＋ｐ２｝＝（Ａ［１］＾ｐＡ）＾ｐとして計算する（ステップ２０４）。
これはフロベニウス写像と積の演算により可能である。
ここで  φ（Ａ［１］）＝Ａ［１］＾｛ｐ｝は、成分でかくと、
φ（  ｃ１ｘ＋ｃ２ｘ２＋ｃ３ｘ３＋ｃ３ｘ４＋ｃ２ｘ５＋ｃ１ｘ６）＝ｃ３ｘ＋ｃ１ｘ２＋ｃ２ｘ３＋ｃ２ｘ４＋ｃ１ｘ５＋ｃ３ｘ６である。
（６）Ａ［１］のＫに関するノルムＡ［０］を、
Ａ［０］＝Ａ［１］・Ａ［１］＊  ｍｏｄ  Φ７として計算する（ステップ２０５）。
【００７４】
Ａ［０］の要素は１個のＫの要素（ｅ１）を用いて、
Ａ［０］＝ｅ１ｘ＋ｅ１ｘ２＋ｅ１ｘ３＋ｅ１ｘ４＋ｅ１ｘ５＋ｅ１ｘ６
とあらわすことができる。
（７）Ｋに関する共役元、ノルムを計算したが、このＫは基礎体なので次の（ステップ２０７）に行く。
（８）ｅ１の逆元ｅ１−１を求める（ステップ２０７）。
（９）Ａの逆元Ａ−１を、
Ａ−１＝ｅ１−１Ａ［１］＊Ａ＊として計算する（ステップ２０８）。
最後にＡ−１を出力手段１２によって出力して終了する（ステップ２０９）。
【００７５】
【発明の効果】
任意の基礎体とその任意次の拡大体に対し逆元演算が従来の技術に比べて同等かより高速に行える。
【００７６】
第１に、本発明におけるフロベニウス写像はいずれも基礎体上の要素の入れ替えにすぎないため、計算のコストは著しく低い。このような特徴を持つためには、拡大体を素数ｑによるｑ分多項式による拡大で生成するか、ｑ円分多項式で逐次拡大する必要があった。
【００７７】
このため利用できる拡大体の拡大次数が限られていたが、本発明の場合はこの制限をうけない。また、本発明におけるフロベニウス写像の計算コストはＯＥＦによる方法のそれよりも低い。
【００７８】
第２に本発明における積の計算コストはＯＥＦのそれと比較しても低い。これは、Ｍの元をＬへ埋め込まれていると見ると、ｑより次数の高い項はΦｑによりより低い項と同一視できるからである。ＯＥＦの場合この高次の項は、その係数に小さい係数を乗じた低次の項と同一視できるため、乗算の計算コストが発生する。
【００７９】
第３に、本発明は逐次、より小さい中間体に関する共役元の逆元演算に帰着している。このことは、積の計算をより小さい体で行うことを可能にしている。例えば、実施例（１）ではＡのＫに関する全ての共役元の積をＭ上のフロベニウス写像と乗算を用いて求めるより、これを実施例のようにＡ＊Ａ［１］＊Ａ［２］＊として求める方が効率的である。なぜならＡ［１］＊等をより小さな中間体の積を使うことにより求めることができるからである。尚、これは逐次拡大の持つ利点と同じである。
【図面の簡単な説明】
【図１】本発明の実施の形態の構成を説明するブロック図である。
【図２】本発明の実施の形態のソフトウェア構成を説明するブロック図である。
【図３】本発明の実施例１及び実施例２の拡大体を決定する方法のフローーチャートである。
【図４】本発明の実施例１及び実施例２の逆元を求める方法のフローーチャートである。
【符号の説明】
１    暗号鍵生成装置
１０    入力手段
１１    暗号鍵演算装置
１１０    ＣＰＵ
１１１    ＲＯＭ
１１２    ＲＡＭ
１１３    ＩＯポート
１２    出力手段
１３    二次記憶装置
２    暗号鍵生成装置
３    ネットワーク
４１    入力部
４２    約数列算出部
４３    共役元積ノルム計算部
４４    逆元計算部
４５    出力部
【図１】
2004233428.tif 000003
【図２】
2004233428.tif 000004
【図３】
2004233428.tif 000005
【図４】
2004233428.tif 000006