(57)【特許請求の範囲】
【請求項１】
有限体ＧＦ（ｑｍ）〔ｑは素数または素数の冪、ｍはｍ＞１の整数とする。〕上定義された代数曲線〔射影座標系で表現されるとする。〕上の点が成す有限可換群の元の群演算を、有限体ＧＦ（ｑｍ）上の除算に表れる除数および被除数を独立に演算するとし、除数を拡大座標〔上記射影座標系の座標のうちAffine座標系の座標を除く座標〕に関連付けることで、上記群演算における除数の逆元演算を回避して行う有限可換群演算方法であって、
有限可換群演算装置の擬似逆元演算手段が、有限体ＧＦ（ｑｍ）の元ｐに対して、Ｎ（ｐ）＝ｖ（ｐ）×ｐ〔但し、Ｎ（ｐ）は有限体ＧＦ（ｑｍ）の部分体の元とし、ｖ（ｐ）は有限体ＧＦ（ｑｍ）の元とする。〕を満たす擬似逆元ｖ（ｐ）を算出する擬似逆元演算ステップと、
有限可換群演算装置の補擬似逆元演算手段が、補擬似逆元Ｎ（ｐ）を算出する補擬似逆元演算ステップとを有し、
上記擬似逆元を上記被除数に含め、上記補擬似逆元を上記除数とする
有限可換群演算方法。
【請求項２】
射影座標系で表現された代数曲線上の点の拡大座標を有限体ＧＦ（ｑｍ）の部分体の元で与える
請求項１に記載の有限可換群演算方法。
【請求項３】
上記補擬似逆元Ｎ（ｐ）は、有限体ＧＦ（ｐｍ）上の元ｐのノルムである
請求項１または請求項２に記載の有限可換群演算方法。
【請求項４】
上記補擬似逆元Ｎ（ｐ）は式（ｃ１）で表され、
【数１】
0004621162.tif 000028
上記擬似逆元ｖ（ｐ）は式（ｃ２）で表される
【数２】
0004621162.tif 000029
請求項３に記載の有限可換群演算方法。
【請求項５】
上記補擬似逆元演算手段が、式（ｃ２）で表される擬似逆元ｖ（ｐ）の各項ｐθ〔但しθ＝ｑｉとする。〕をフロベニウス写像によって求める
請求項４に記載の有限可換群演算方法。
【請求項６】
式（ｃ２）で表される擬似逆元ｖ（ｐ）を式（ｃ３）と表現し、
【数３】
0004621162.tif 000030
上記補擬似逆元演算手段が、式（ｃ３）に表れるｐｕを加算連鎖によって求める
請求項５に記載の有限可換群演算方法。
【請求項７】
上記群演算は、加算演算および／または２倍演算である
請求項１から請求項６のいずれかに記載の有限可換群演算方法。
【請求項８】
有限体ＧＦ（ｑｍ）〔ｑは素数または素数の冪、ｍはｍ＞１の整数とする。〕上定義された代数曲線〔射影座標系で表現されるとする。〕上の点が成す有限可換群の元の群演算を、有限体ＧＦ（ｑｍ）上の除算に表れる除数および被除数を独立に演算するとし、除数を拡大座標〔上記射影座標系の座標のうちAffine座標系の座標を除く座標〕に関連付けることで、上記群演算における除数の逆元演算を回避して行う有限可換群演算装置であって、
有限体ＧＦ（ｑｍ）の元ｐに対して、Ｎ（ｐ）＝ｖ（ｐ）×ｐ〔但し、Ｎ（ｐ）は有限体ＧＦ（ｑｍ）の部分体の元とし、ｖ（ｐ）は有限体ＧＦ（ｑｍ）の元とする。〕を満たす擬似逆元ｖ（ｐ）を算出する擬似逆元演算手段と、
補擬似逆元Ｎ（ｐ）を算出する擬似逆元演算手段とを備え、
上記擬似逆元を上記被除数に含め、上記補擬似逆元を上記除数とする
有限可換群演算装置。
【請求項９】
コンピュータに請求項１から請求項７のいずれかに記載の有限可換群演算方法を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限可換群の元の群演算を行う技術に関する。
【背景技術】
【０００２】
有限体上定義された代数曲線（以下、特に断りが無い限り、単に代数曲線と云えば、有限体上定義された代数曲線を云うものとする。）を用いた公開鍵暗号やデジタル署名などでは、代数曲線上で定義された有限可換群の元の群演算が行われる。例えば、数論的問題を解くことに要する計算量を安全性の根拠とする暗号アルゴリズムを代数曲線上に構築する場合、このような数論的問題として離散対数問題がある。離散対数問題は、Ｇを有限可換群、α、βをＧの元、ＮをＧの位数とした場合、α＝ｎβを満たすｎ∈ＺＮを求める問題である。この例ではα＝ｎβ＝β＋β＋・・・＋β（βをｎ回加算するスカラー倍演算である。）なる演算が群演算で表現される。そして、この群演算は、代数曲線が定義される有限体の演算で構成される。
【０００３】
理解を容易にするため、具体的な一例を挙げて説明する。
有限体上定義された代数曲線の一例として有限体ＧＦ（ｑｍ）上定義された楕円曲線を選択する〔ｑは素数あるいは素数の冪、ｍはｍ＞１の整数とする。〕。この楕円曲線は種数１の超楕円曲線であり、有理点集合Ｅ（ＧＦ（ｑｍ））は有限可換群になる〔式（１）参照。但し、Affine座標系のワイエルシュトラス形式で、標数ｑ≠２且つｑ≠３且つ４ａ３＋２７ｂ２≠０とし、点Ｏは無限遠点とする。〕。
【数４】
0004621162.tif 000002
【０００４】
このとき楕円離散対数問題は、Ｐ∈Ｅ（ＧＦ（ｑｍ））、Ｑ∈Ｅ（ＧＦ（ｑｍ））、ｋ∈Ｚ／ｑｍＺに対して、Ｑ＝ｋＰ＝Ｐ＋Ｐ＋・・・＋Ｐ（Ｐをｋ回加算する楕円スカラー倍演算である。）を満たすｋを求める問題になる。
【０００５】
楕円スカラー倍演算は、一般に楕円曲線上の点の加算および２倍算から構成される。楕円曲線上の点の加算および２倍算は、それぞれ曲線が定義される有限体の四則演算から構成される。
【０００６】
点Ｒ１（ｘ１，ｙ１）、点Ｒ２（ｘ２，ｙ２）および点Ｒ３（ｘ３，ｙ３）を楕円曲線上の点とする。ｘ１＝ｘ２且つｙ１＝−ｙ２ならばＲ１＋Ｒ２＝Ｏ（無限遠点）とするが、そうでない場合には、Ｒ１＋Ｒ２＝Ｒ３とする。このとき式（２）が成立する。Ｐ≠Ｑの場合が楕円加算公式、Ｐ＝Ｑの場合が楕円２倍算公式である。
【数５】
0004621162.tif 000003
【０００７】
Affine座標系における楕円加算公式のアルゴリズム（演算手順）の一例およびその演算コストを図１に示す。入力：（ｘ１，ｙ１）∈ＧＦ（ｑｍ）２，（ｘ2，ｙ2）∈ＧＦ（ｑｍ）２、出力：（ｘ３，ｙ３）∈ＧＦ（ｑｍ）２として、図左側に実際の演算内容を示している。また、Ｉを有限体上逆元の演算コスト、Ｍを有限体上乗算の演算コスト、Ｓを有限体上自乗の演算コストとして、図右側に演算内容に対応した演算コストの見積もりを示している。なお、有限体上加算または減算または１／２倍算の演算コストは、有限体上逆元の演算コスト、乗算の演算コスト、自乗の演算コストに比して十分に小さいため無視できるので、図に表記していないことに留意すること。また、演算コストの見積もりでは、演算内容に用いる値がそれ以前の演算内容で計算されている場合には、当該値を改めて計算しなおす必要が無いことに留意しなければならない。図１で示した例で説明すると、最初の演算ステップでΛを計算し、２番目および３番目の演算ステップでΛを用いた計算をしているが、最初の演算ステップで計算したΛをメモリなどの記憶手段に格納しておき、２番目および３番目の演算ステップでΛを記憶手段から読み込むことでΛの再計算を避けることができる。
【０００８】
同様に、Affine座標系における楕円２倍算公式のアルゴリズム（演算手順）の一例およびその演算コストを図２に示す。但し、入力：（ｘ１，ｙ１）∈ＧＦ（ｑｍ）２、出力：（ｘ３，ｙ３）∈ＧＦ（ｑｍ）２である。演算コストの記号は既述のとおりである。
【０００９】
図１および図２から明らかなように、上記楕円加算を１回実行するのに有限体上の逆元１回、乗算２回、自乗１回の演算が必要であり、上記楕円２倍算を１回実行するのに有限体上の逆元１回、乗算２回、自乗２回の演算が必要である。
【００１０】
有限体上の逆元の演算は、一般には有限体上の乗算に比して実装が複雑で、速度も遅いという問題がある。そこで、楕円曲線上の点を（ｘ，ｙ）という２つの有限体の元ではなく３つ以上の有限体の元によって表現する事によって逆元演算を回避する方法が様々に考案されている。つまり、Affine座標系で表現された楕円曲線を射影座標系で表現された楕円曲線に変換するのである。
【００１１】
例えば射影座標系の一つであるJacobian座標系は、有限体の３つの元による表現手法であり、Affine座標（ｘ，ｙ）はＺ≠０なる同じ有限体上の任意のＺによってJacobian座標（ｘＺ２，ｙＺ３，Ｚ）に変換できる。逆にＺ≠０なるJacobian座標（Ｘ，Ｙ，Ｚ）が与えられたとき（Ｘ／Ｚ２，Ｙ／Ｚ３）によっていつでも対応するAffine座標を求めることが出来る（非特許文献１参照。）。
【００１２】
Jacobian座標系における楕円加算公式のアルゴリズム（演算手順）の一例およびその演算コストを図３に示す。但し、入力：（Ｘ１，Ｙ１，Ｚ１）∈ＧＦ（ｑｍ）３，（Ｘ２，Ｙ２，Ｚ２）∈ＧＦ（ｑｍ）３、出力：（Ｘ３，Ｙ３，Ｚ３）∈ＧＦ（ｑｍ）３である。演算コストの記号は既述のとおりである。
同様に、Jacobian座標系における楕円２倍算公式のアルゴリズム（演算手順）の一例およびその演算コストを図４に示す。但し、入力：（Ｘ１，Ｙ１，Ｚ１）∈ＧＦ（ｑｍ）３、出力：（Ｘ３，Ｙ３，Ｚ３）∈ＧＦ（ｑｍ）３である。演算コストの記号は既述のとおりである。
【００１３】
Jacobian座標系では、一般の楕円加算を１回実行するのに有限体上の乗算１２回、自乗４回の演算が必要であり、Ｚ２＝１の場合では楕円加算を１回実行するのに有限体上の乗算８回、自乗３回の演算が必要である。また、一般の楕円２倍算を１回実行するのに有限体上の乗算４回、自乗６回の演算が必要であり、ａ＝−３の場合では楕円２倍算を１回実行するのに有限体上の乗算４回、自乗４回の演算が必要である。
【００１４】
上記の楕円加算の例で説明すれば、Affine座標系ではΛの算出に逆元演算を要していた〔Λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）＝（ｙ２−ｙ１）×（ｘ２−ｘ１）−１である。〕。仮に、Affine座標系でのΛの分子を被除数Λｎ＝ｙ２−ｙ１とし、Affine座標系でのΛの分母を除数Λｄ＝ｘ２−ｘ１とし、それぞれ独立に演算するとしても、Affine座標系では除数Λｄの逆元の演算を避けることができない〔Λ＝Λｎ×Λｄ−１である。〕。
【００１５】
これに対してJacobian座標系では、Affine座標系でのΛを座標変換したものの分子相当Ｙ′２−Ｙ′１を被除数Λｎとし、Affine座標系でのΛを座標変換したものの分母相当Ｘ′２−Ｘ′１を除数Λｄとし、それぞれ独立に演算するとし、除数Λｄを拡大座標〔射影座標系の座標のうちAffine座標系の座標を除く座標であるとする。Jacobian座標系では第３座標Ｚに相当する。〕に関連付けることで、除数Λｄの逆元演算を回避している。なお、Affine座標系でのΛをJacobian座標系へ変換したΛJacobianは、適当な関数ｆをもってΛJacobian＝（Ｙ′２−Ｙ′１）／（Ｘ′２−Ｘ′１）×ｆ（Ｚ１，Ｚ２）と表されるので、Ｙ′２−Ｙ′１を「分子相当」、Ｘ′２−Ｘ′１を「分母相当」と呼んでいる。
このことは上記の楕円２倍算の例でも同様であり、また、Jacobian座標系だけでなくProjective座標系やChudnovsky座標系などの射影座標系でも同様である〔但し、常にΛｎ＝Ｙ′２−Ｙ′１、Λｄ＝Ｘ′２−Ｘ′１という趣旨ではない。〕。
【００１６】
上記の各例から分かるように、Jacobian座標系では、Affine座標系の場合に比して逆元演算を回避できるものの、乗算や自乗の演算コストが増加する。
【非特許文献１】H. Cohen, A. Miyaji ,and T. Ono,“Efficient elliptic curve exponentiation using mixed coordinates”， Advances in Cryptology-Proceedings of ASIACRYPT ’98, Lecture Notes  in Computer Science,Springer-Verlag,1514(1998),51-65.
【発明の開示】
【発明が解決しようとする課題】
【００１７】
有限体上定義された楕円曲線の楕円加算および楕円２倍算で例示説明したが、一般的には、有限体上定義された代数曲線上の点が成す有限可換群の元の群演算では、Affine座標系において有限体上の逆元演算が不可避である。これに対して、代数曲線を射影座標系に変換することで群演算に表れる有限体上の逆元演算を回避することができる。
しかし、このような回避方法では、有限体上の逆元演算を回避することはできても乗算や自乗の演算コストが大きくなるという問題があった。
【００１８】
そこで本発明は、上記の問題点に鑑み、有限体上定義された代数曲線上の点が成す有限可換群の元の群演算（有限可換群演算）であって、逆元演算を回避しつつ演算や自乗の演算コストを低減した有限可換群演算方法、装置、プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
上記課題を解決するために、本発明は、次のような構成とする。即ち、有限体ＧＦ（ｑｍ）〔但し、ｑは素数または素数の冪、ｍはｍ＞１の整数とする。〕の元ｐに対して、Ｎ（ｐ）＝ｖ（ｐ）×ｐ〔但し、Ｎ（ｐ）は有限体ＧＦ（ｑｍ）の部分体の元とし、ｖ（ｐ）は有限体ＧＦ（ｑｍ）の元とする。〕を満たす擬似逆元ｖ（ｐ）を算出する擬似逆元演算手段と、補擬似逆元Ｎ（ｐ）を算出する補擬似逆元演算手段とを備える。そして、有限体ＧＦ（ｑｍ）上定義された代数曲線〔射影座標系で表現されるとする。〕上の点が成す有限可換群の元の群演算を、有限体ＧＦ（ｑｍ）上の除算に表れる除数および被除数を独立に演算するとし、除数を拡大座標〔上記射影座標系の座標のうちAffine座標系の座標を除く座標であるとする。〕に関連付けることで、上記群演算における除数の逆元演算を回避して行う有限可換群演算であって、擬似逆元演算手段が擬似逆元を算出し、補擬似逆元演算手段が補擬似逆元を算出して、擬似逆元を被除数に含め、補擬似逆元を除数する。
このように、有限体ＧＦ（ｑｍ）の元である擬似逆元ｖ（ｐ）および有限体ＧＦ（ｑｍ）の部分体の元である補擬似逆元Ｎ（ｐ）を算出して、擬似逆元を被除数に含め、補擬似逆元を除数とするのである。
【００２０】
また、射影座標系で表現された代数曲線上の点の拡大座標を有限体ＧＦ（ｑｍ）の部分体の元で与えるとしてもよい。
これは補擬似逆元Ｎ（ｐ）の属する体によって拡大座標の元を与えることができることを意味し、有限体ＧＦ（ｑｍ）の部分体上での演算を可能とする。つまり、部分体上の演算コストで演算することができる。
【００２１】
また、補擬似逆元Ｎ（ｐ）は、有限体ＧＦ（ｐｍ）上の元ｐのノルムであるとしてもよい。そして、ノルムとして補擬似逆元Ｎ（ｐ）を式（ｒ１）で表し、擬似逆元ｖ（ｐ）を式（ｒ２）で表すとしてもよい。
有限体ＧＦ（ｐｍ）上の元ｐのノルムは、有限体ＧＦ（ｐｍ）の部分体の元を与えることができる。
【数６】
0004621162.tif 000004
【００２２】
式（ｒ２）で表される擬似逆元ｖ（ｐ）の各項ｐθ〔但しθ＝ｑｉとする。〕をフロベニウス写像によって求めるとしてもよく、式（ｒ２）で表される擬似逆元ｖ（ｐ）を式（ｒ３）と表現し、式（ｒ３）に表れるｐｕを加算連鎖によって求めるとしてもよい。
【数７】
0004621162.tif 000005
【００２３】
群演算を加算演算および／または２倍演算とすると、例えばスカラー倍演算は加算演算および／または２倍演算で構成されるから、効率の良いスカラー倍演算の実現に寄与する。
【００２４】
また、本発明の有限可換群演算装置としてコンピュータを機能させる有限可換群演算プログラムによって、コンピュータを有限可換群演算装置として作動処理させることができる。
【発明の効果】
【００２５】
本発明によれば、有限体上定義された代数曲線上の点が成す有限可換群の元の群演算（有限可換群演算）において、有限体ＧＦ（ｑｍ）の元である擬似逆元ｖ（ｐ）および有限体ＧＦ（ｑｍ）の部分体の元である補擬似逆元Ｎ（ｐ）を算出して、擬似逆元ｖ（ｐ）を被除数に含め、補擬似逆元Ｎ（ｐ）を除数とする。有限体ＧＦ（ｑｍ）の部分体の元である補擬似逆元Ｎ（ｐ）の算出は、有限体ＧＦ（ｑｍ）上の乗算や自乗の演算コストよりも小さい。また、擬似逆元ｖ（ｐ）の算出は、有限体ＧＦ（ｑｍ）上の逆元の演算コストよりも小さく、さらに効率の良い演算方法も存在する。従って、逆元演算を回避しつつ演算や自乗の演算コストを低減した有限可換群演算が可能である。
【発明を実施するための最良の形態】
【００２６】
《理論》
部分体を持つ有限体には擬似逆元演算と呼ばれる演算を定義できる。
＜擬似逆元演算＞
擬似逆元演算とは、ｑを素数または素数の冪、ｍをｍ＞１の整数として、有限体ＧＦ（ｑｍ）上の元ｘに対してＮ（ｘ）＝ｘ×ｖ（ｘ）なる（ｖ（ｘ），Ｎ（ｘ））を出力する演算である。但し、ｖ（ｘ）は有限体ＧＦ（ｑｍ）の元とし、Ｎ（ｘ）は有限体ＧＦ（ｑｍ）の部分体ＧＦ（ξ）の元とする。
ここでは、ｖ（ｘ）を擬似逆元、Ｎ（ｘ）を補擬似逆元と呼ぶことにする。
【００２７】
擬似逆元ｖ（ｘ）および補擬似逆元Ｎ（ｘ）を用いると、ｘの逆元ｘ−１は、ｖ（ｘ）×Ｎ（ｘ）−１で与えられる。換言すれば、逆元ｘ−１は被除数ｖ（ｘ）を分子とし、除数Ｎ（ｘ）を分母とした除算として与えられる。
このことに着眼すると、Jacobian座標系における楕円加算の例で説明すれば、被除数Λｎをｖ（Ｘ′２−Ｘ′１）×（Ｙ′２−Ｙ′１）とし、除数λｄをＮ（Ｘ′２−Ｘ′１）とし、それぞれ独立に演算するとし、除数λｄ、つまり補擬似逆元Ｎ（Ｘ′２−Ｘ′１）を拡大座標に関連付けることで、除数λｄの逆元演算を回避できることになる〔ｘ＝Ｘ′２−Ｘ′１と考えればよい。〕。このことは、Jacobian座標系における楕円２倍算の場合は勿論、他の射影座標系や代数曲線などでも同様である。但し、常にΛｎ＝ｖ（Ｘ′２−Ｘ′１）×（Ｙ′２−Ｙ′１）、λｄ＝Ｎ（Ｘ′２−Ｘ′１）という趣旨ではない。例えば、Projective座標系の楕円２倍算の場合、λｄ＝Ｎ（２Ｙ１）×ｚ１で与えられる。ただ、この場合でも、λｄ＝Ｎ（２Ｙ１）、λ′ｄ＝λｄ×ｚ１で与える構成としてもよく、このようにしても全体の演算コストは変わらない。要は、被除数Λｎにｖ（Ｘ′２−Ｘ′１）を含め、除数λｄをＮ（Ｘ′２−Ｘ′１）として、それぞれ独立に演算を行うとし、さらに、補擬似逆元である除数λｄを拡大座標に関連付けることで、除数λｄの逆元演算を回避するのである。
【００２８】
このような擬似逆元演算を用いた逆元演算回避手法の場合、従来の逆元演算回避手法に比較して、擬似逆元ｖ（ｘ）および補擬似逆元Ｎ（ｘ）の演算コストが必要になる。擬似逆元演算には効率良く演算する方法が存在するので、その一例を説明する。
【００２９】
擬似逆元演算を効率良く演算する方法の一つに、例えばｑｎ乗写像（フロベニウス写像）を用いる方法がある。ここでは説明の便宜から、有限体ＧＦ（ｑｍ）の部分体ＧＦ（ξ）を有限体ＧＦ（ｑ）として説明する。
【００３０】
＜ｑｎ乗写像を用いた擬似逆元演算＞
ｘ∈ＧＦ（ｑｍ）なるｘに対して、式（３）で与えられるｚをnormと呼ぶ。norm ｚは必ずｚ∈ＧＦ（ｑ）となることが知られている。
【数８】
0004621162.tif 000006
【００３１】
式（３）から式（４）を得る。
【数９】
0004621162.tif 000007
【００３２】
式（４）をｚ＝ｘｙと看做せば、括弧部分がｙに相当する。つまりｙは式（５）で表される。このとき、ｚが補擬似逆元Ｎ（ｘ）に相当し、ｙが擬似逆元ｖ（ｘ）に相当すると考えることができる。
【数１０】
0004621162.tif 000008
【００３３】
＜norm＞
norm ｚは一般にｚ∈ＧＦ（ｑ）が保証されているので、ｚ＝ｘｙの演算コストはＧＦ（ｑｍ）上の乗算や自乗の演算コストに比べて十分小さい。
【００３４】
＜ｑｎ乗写像＞
通常、有限体ＧＦ（ｑｍ）上の元ｘを表現するのに、有限体ＧＦ（ｑ）上のｍ個の元ｘｉ（０≦ｉ＜ｍ）が用いられる。ｍ個のｘｉ∈ＧＦ（ｑ），（０≦ｉ＜ｍ）の組をＧＦ（ｑｍ）上の元に対応させる代表的な方法は、ｍ個のαｉ∈ＧＦ（ｑｍ），（０≦ｉ＜ｍ）の組を使って、式（６）に示す対応を取ることである。
【数１１】
0004621162.tif 000009
【００３５】
このときαｉ（０≦ｉ＜ｍ）は、ＧＦ（ｑ）ｍとＧＦ（ｑｍ）とで１対１対応が取れるような組合せでなくてはならない。このαｉ（０≦ｉ＜ｍ）を基底と呼ぶ。
【００３６】
ところで二項定理によれば、式（７）が成立する。
【数１２】
0004621162.tif 000010
【００３７】
式（７）の右辺の各項の係数（ｑ，ｉ）は二項係数と呼ばれる定数で、ｉ≠０かつｉ≠ｑの場合必ずｑの倍数となる。ａ，ｂ∈ＧＦ（ｑｍ）のときは、ｑの整数倍は０と同値であるから（ＧＦ（ｑｍ）の標数はｑである。）、式（８）が成立する。
【数１３】
0004621162.tif 000011
【００３８】
更にｃ∈ＧＦ（ｑ）なるｃに関してｃｑ＝ｃが成立する。一般にａｉ∈ＧＦ（ｑｍ），（０≦ｉ＜ｎ）、ｃｉ∈ＧＦ（ｑ），（０≦ｉ＜ｎ）とすると、式（９）が成立する。
【数１４】
0004621162.tif 000012
【００３９】
従って、αｉ∈ＧＦ（ｑｍ）、ｘｉ∈ＧＦ（ｑ）なるとき、式（６）で表されるｘのｑ乗であるｘｑは、式（１０）で与えられる。
【数１５】
0004621162.tif 000013
【００４０】
従って事前に式（１１）で与えられるｃij∈ＧＦ（ｑ）が計算してあれば、式（１０）は式（１２）に書き換えられるから、基底αｉを使ったｘｑの表現Σｊ＝０ｍ−１ｃijｘｉを求めることができる。
【数１６】
0004621162.tif 000014
【００４１】
即ち、ｘ∈ＧＦ（ｑｍ）を表現するベクトル（ｘｉ）に行列（ｃｉｊ）を掛けるだけで、ｘｑを表現するベクトルが得られる。この演算コストは、一般にはＧＦ（ｑｍ）上の乗算１回分の演算コストにほぼ等しい。また、行列（ｃij）ｎ，（ｎ＝２，３，…）を事前に求めておけば、行列（ｃij）ｎを掛けるだけでｘｗ〔但し、ｗ＝ｑｎとする。〕を表現するベクトルが得られる。あるいは、（ｃij）-1を事前に求めておけば、（ｃij）-1を掛けるだけでｘ１／ｑを表現するベクトルが得られる。従って、一般の整数ｎに対してｘｗの演算コストは、一般にＧＦ（ｑｍ）上の乗算１回分の演算コストに等しい。
【００４２】
また、基底αｉの代表的な選び方として式（１３）に示す２つの方法がある。但しβ、γは各々の方法でＧＦ（ｑ）ｍとＧＦ（ｑｍ）とで１対１対応が取れるようなＧＦ（ｑｍ）上の元とする。
【数１７】
0004621162.tif 000015
【００４３】
このような基底を選択する場合に演算コストをさらに低減できることがある。例えば正規基底による方法の場合、基底αｉのｑ乗は式（１４）に示す関係にあるから、行列（ｃij）は式（１５）で与えられる。
【数１８】
0004621162.tif 000016
【００４４】
即ち、入力のｍ個のｘｉ∈ＧＦ（ｑ），（０≦ｉ＜ｍ）の順番を並び換えて出力するだけでｘｑの演算が完了する。ｘｗの演算の場合も同様の並び換えのみで完了する。この並び換えの演算コストは、ＧＦ（ｑｍ）上の乗算や自乗の演算コストに対して無視できる。
【００４５】
多項式基底による方法の場合、一般にはｘｗの演算はＧＦ（ｑｍ）上の乗算の演算コストとほぼ等しいが、γとして特別なＧＦ（ｑｍ）上の元を選択することによって演算コストを低減できることがある。例えばγがω∈ＧＦ（ｑ）に対してγｍ−ω＝０なる関係を持つ場合、基底αｉのｑｎ乗は式（１６）に示す関係にある。但し、記号［ｉｑｎ／ｍ］は、ｉｑｎ／ｍ以下の最大整数を表す。
【数１９】
0004621162.tif 000017
【００４６】
即ち、入力のｍ個のｘｉ∈ＧＦ（ｑ），（０≦ｉ＜ｍ）の各々にω[Ｔ]〔但し、Ｔ＝ｉｑｎ／ｍとする。〕を掛けて順番を並び換えて出力するだけでｘｗの演算が完了する。この演算コストも、ＧＦ（ｑｍ）上の乗算や自乗の演算コストに対して無視できる。
【００４７】
＜加算連鎖＞
次に、式（５）で表されるｙを効率良く計算する方法の一例を説明する。
ｙは式（１７）に変形できる。
【数２０】
0004621162.tif 000018
【００４８】
ここで記号ｕを式（１８）で定義する。
【数２１】
0004621162.tif 000019
【００４９】
このとき式（１７）は式（１９）に書き換えられ、ｘｕは式（２０）のように計算することができる。
【数２２】
0004621162.tif 000020
【００５０】
式（２０）のような演算を行う際、既述のとおりｑｉ乗演算はＧＦ（ｑｍ）上の乗算に比べ高速に演算可能であるから、演算の律速段階となるのはｍ−２回〔式（２０）の右辺の×の個数に相当する。〕実行されるＧＦ（ｑｍ）上の乗算である。
【００５１】
ところで、例えばｍ−１＝２ｎだったとすると、ｕは式（２１）のように分解して表すことができる。
【数２３】
0004621162.tif 000021
【００５２】
この場合、ｘｕを計算する方法として、例えば、式（２２）のような演算方法を用いると、ｎ回即ちlog２（ｍ−１）回のＧＦ（ｑｍ）上乗算でｘｕを計算できる。
【数２４】
0004621162.tif 000022
【００５３】
このような計算方法は、たとえｎが２の冪乗数でなかったとしても一般的に構成することが可能であり、一例として次のように構成することができる。
ｉ、ｊ、ｋを整数として整数（１＝）ｎ０，・・・，ｎｒ（＝ｍ−１）を式（２３）で与える。この整数列ｎ０，・・・，ｎｒをｍ−１の（最適）加算連鎖と呼ぶ。
【数２５】
0004621162.tif 000023
【００５４】
ｍ−１の（最適）加算連鎖を用いてｑ冪倍を含む（最適）加算連鎖を構成することができる。このｑ冪倍を含む（最適）加算連鎖は式（２４）で与えられる。このとき式（２５）が成立している。なお、式（２４）のｑの冪数ｎｋは式（２３）のｎｋに対応している。
【数２６】
0004621162.tif 000024
【００５５】
このｑ冪倍を含む（最適）加算連鎖を用いてｘｕの計算を次のように実行することができる。まずｍ−１の（最適）加算連鎖ｎ０，・・・，ｎｒを与える。この（最適）加算連鎖ｎｊ＝ｎｊ＋ｎｋ（ｊ，ｋ＜ｉ）におけるｉ、ｊ、ｋの対応に従って、ｉ＝０，・・・，ｒに対して式（２６）なる演算によってＡ０，・・・，Ａｎを求める。このとき式（２７）が成立する。
【数２７】
0004621162.tif 000025
【００５６】
ここで、式（２８）が成立するから、Ａｒが求めるｘｕとなる。
【数２８】
0004621162.tif 000026
【００５７】
ｍ−１の最短の加算連鎖の長さＬ（ｍ−１）は最悪でもＬ（ｍ−１）≦２log２（ｍ−１）に抑えることができる。即ち、Ａｒも最悪２log２（ｍ−１）回程度のＧＦ（ｑｍ）上の乗算で求めることができる。一般にｘｕを効率良く求めたいならば、効率の良いｍ−１の加算連鎖を与えれば良い。下記参考文献１には１以上１００以下の整数の加算回数に関する最適加算連鎖のＴｒｅｅ図が掲載されている。そのような加算連鎖を用いることによって、ｘｕの計算を最適化できる。
（参考文献１） Knuth著, "The Art of Computer Programming", VOLUME 2 Seminumerical Algorithms Third Edition, p.465, Addison Wesley, ISBN:O-201-89684-2
【００５８】
ここでは擬似逆元演算を効率良く演算する方法の一つとして、例えばｑｎ乗写像を用いる方法を示したが、この方法以外にもユークリッドの互除法を用いた方法などもある。
以上の説明から帰納されることとして、有限体ＧＦ（ｑｍ）の部分体の元である補擬似逆元ｚは、有限体ＧＦ（ｑｍ）上の乗算や自乗の演算コストに比して十分に小さい演算コストで計算可能であることが云える。また、擬似逆元ｙについても、有限体ＧＦ（ｑｍ）上の逆元の演算コストより小さく効率の良い演算コストで計算可能であることが云える。
【００５９】
さらに、有限体ＧＦ（ｑｍ）の部分体の元である補擬似逆元を除数λｄとし、除数λｄを拡大座標に関連付けることから、拡大座標を有限体ＧＦ（ｑｍ）の部分体の元で与えることができ、拡大座標を用いた計算について、その演算コストを低減することができる。
このことをJacobian座標系における楕円加算の例で説明すれば、Jacobian座標系の第３座標を有限体ＧＦ（ｑｍ）の部分体ＧＦ（ξ）の元ｚで与えることができるということである。例えば従来手法におけるＺ３←ΛｄＺ′３なる演算はｚ３←λｄｚ′３に変更される。この場合、従来手法の場合において有限体ＧＦ（ｑｍ）上乗算の演算コストであったのが、有限体ＧＦ（ｑｍ）の部分体ＧＦ（ξ）上乗算の演算コストに変更される。有限体ＧＦ（ｑｍ）の部分体ＧＦ（ξ）上乗算の演算コストは、有限体ＧＦ（ｑｍ）上乗算の演算コストに比較して十分に小さい。従って、従来手法に比して演算コストを低減できる。また、例えば従来手法におけるＸ"１←Ｘ′１Λｄ２なる演算はＸ"１←Ｘ′１λｄ２に変更される。この場合、従来手法の場合において有限体ＧＦ（ｑｍ）上の１回の乗算と１回の自乗の演算コストであったのが、有限体ＧＦ（ｑｍ）の部分体ＧＦ（ξ）の元と有限体ＧＦ（ｑｍ）の元との乗算１回および有限体ＧＦ（ｑｍ）の部分体ＧＦ（ξ）上の自乗１回の演算コストに変更されるので、演算コストを低減できることになる。
このように、拡大座標を有限体ＧＦ（ｑｍ）の部分体の元で与えることができることから拡大座標を用いる計算の演算コストも低減できる。
【００６０】
＜具体例＞
次に、具体例として、擬似逆元演算を用いたJacobian座標系における楕円加算のアルゴリズム（演算手順）の一例およびその演算コストを図５に示す。但し、入力：（Ｘ１，Ｙ１，ｚ１）∈ＧＦ（ｑｍ）２×ＧＦ（ξ），（Ｘ２，Ｙ２，ｚ２）∈ＧＦ（ｑｍ）２×ＧＦ（ξ）、出力：（Ｘ３，Ｙ３，ｚ３）∈ＧＦ（ｑｍ）２×ＧＦ（ξ）である。また、既述の演算コストの記号に加え、Ｖを擬似逆元ｖ（ｘ）の演算コストとする。なお、補擬似逆元Ｎ（ｘ）の演算コスト、ＧＦ（ｑｍ）×ＧＦ（ξ）乗算の演算コスト、ＧＦ（ξ）上乗算の演算コスト、ＧＦ（ξ）上自乗の演算コスト、ＧＦ（ξ）上加算の演算コストはＧＦ（ｑｍ）上乗算コストＭに比べて十分小さく無視できるため図に表記していないことに留意すること。
【００６１】
同様に、擬似逆元演算を用いたJacobian座標系における楕円２倍算公式のアルゴリズム（演算手順）の一例およびその演算コストを図６に示す。但し、入力：（Ｘ１，Ｙ１，ｚ１）∈ＧＦ（ｑｍ）２×ＧＦ（ξ）、出力：（Ｘ３，Ｙ３，ｚ３）∈ＧＦ（ｑｍ）２×ＧＦ（ξ）である。演算コストの記号は既述のとおりである。
【００６２】
擬似逆元ｖ（ｘ）は、例えば有限体ＧＦ（ｑｍ）の次数ｍがｍ＝５の場合、上記の（最適）加算連鎖の方法を用いることで、式（２９）のようにして擬似逆元ｖ（ｘ）および補擬似逆元Ｎ（ｘ）を得ることができるから、ｑｎ乗写像３回とＧＦ（ｑｍ）上乗算２回で実行することができる。
【数２９】
0004621162.tif 000027
【００６３】
既述のとおり、例えば補擬似逆元としてnormを用いた場合には、ｑｎ乗写像における基底を適切に選択しておくことでｑｎ乗写像の演算コストをＧＦ（ｑｍ）上乗算の演算コストに対して十分小さくすることができるから、ｍ＝５の場合、演算コストＶは凡そ演算コスト２Ｍ相当としてよい。
【００６４】
図５および図６に示す演算コストから、擬似逆元演算を用いたJacobian座標系における楕円加算を１回実行するのにＧＦ（ｑｍ）上の擬似逆元１回、乗算２回、自乗１回の演算が必要であり、擬似逆元演算を用いたJacobian座標系における楕円２倍算を１回実行するのにＧＦ（ｑｍ）上の擬似逆元１回、乗算２回、自乗２回が必要であることがわかる。
【００６５】
次数ｍ＝５の場合、擬似逆元１回がおよそ乗算２回相当であったことを考えると、擬似逆元演算を用いたJacobian座標系における楕円加算を１回実行するのにおよそＧＦ（ｑｍ）上の乗算４回、自乗１回が必要であり、擬似逆元演算を用いたJacobian座標系における楕円２倍算を１回実行するのにおよそＧＦ（ｑｍ）上の乗算４回、自乗２回が必要であることになる。
これは従来のJacobian座標系おける演算コストに比べて、楕円加算に関してＧＦ（ｑｍ）上の乗算８回、自乗３回分が節約され、楕円２倍算に関してＧＦ（ｑｍ）上の自乗４回分が節約されたことを意味する。
【００６６】
以上では、具体例として擬似逆元演算を用いたJacobian座標系の場合を説明したが、その他の具体例として、Projective座標系およびChudnovsky座標系の場合の楕円加算および楕円２倍算のアルゴリズム（演算手順）の一例およびその演算コストを示す。
図７にProjective座標系における楕円加算のアルゴリズム（演算手順）の一例およびその演算コスト、図８に擬似逆元演算を用いたProjective座標系における楕円加算のアルゴリズム（演算手順）の一例およびその演算コスト、図９にProjective座標系における楕円２倍算のアルゴリズム（演算手順）の一例およびその演算コスト、図１０に擬似逆元演算を用いたProjective座標系における楕円２倍算のアルゴリズム（演算手順）の一例およびその演算コストを示す。
また、図１１にChudnovsky座標系における楕円加算のアルゴリズム（演算手順）の一例およびその演算コスト、図１２に擬似逆元演算を用いたChudnovsky座標系における楕円加算のアルゴリズム（演算手順）の一例およびその演算コスト、図１３にChudnovsky座標系における楕円２倍算のアルゴリズム（演算手順）の一例およびその演算コスト、図１４に擬似逆元演算を用いたChudnovsky座標系における楕円２倍算のアルゴリズム（演算手順）の一例およびその演算コストを示す。
なお、各図で下線付の箇所は、その前に１度計算結果が現れていて改めて計算する必要のない値を表す。例えば（ａ）Ｙ←Ｘ２Ｘ、（ｂ）Ｚ←Ｘ２なる演算手順ではＹを求める時にＸ２を計算しているため、これを記憶手段に保存しておき、Ｚを求める際にはＸ２を改めて計算せずに保存していた値を使えばよい。
何れの場合においても、例えば次数ｍ＝５とした場合で明らかなとおり、従来手法に比較して、擬似逆元演算を用いた場合には乗算や自乗の演算コストが低減することがわかる。
【００６７】
《実施形態》
続いて、本発明の具体的な実施形態を説明するが、下記の点について留意しておかなくてはならない。即ち、以上の各座標系の例から明らかなように、具体的な実施形態は座標系によって変わりえる。また、楕円加算および楕円２倍算の例から明らかなように、群演算の種類によっても具体的な実施形態は変わりえる。もちろん、代数曲線の種類などによっても具体的な実施形態は変わりえる。さらに、群演算アルゴリズムも適宜に変更可能であるから、これに応じて具体的な実施形態は変わりえる。さらには、本発明をコンピュータで実施する場合、演算処理はＣＰＵで行われるのが通常であるから、ＣＰＵに実装されている命令セット（例えばＳＩＭＤ〔Single Instruction/Multiple Data〕型命令の有無）によっても具体的な実施形態は変わりえる。
【００６８】
従って、ここでは擬似逆元演算を用いた群演算の一例を具体的に示すという観点から、次の条件を設定して具体的な実施形態を説明することにする。
（条件）
１．有限体上定義された代数曲線を、有限体ＧＦ（ｑｍ）〔ｑは素数あるいは素数の冪、ｍはｍ＞１の整数とする。〕上定義された楕円曲線とする。
２．有限可換群は、上記楕円曲線の有理点集合Ｅ（ＧＦ（ｑｍ））とする。
３．群演算は、楕円２倍算とする。
４．楕円２倍算公式は、Affine座標系のワイエルシュトラス形式において、標数ｑ≠２且つｑ≠３且つ４ａ３＋２７ｂ２≠０とした場合のもの、つまり式（２）でＰ＝Ｑとした場合のものとする。
５．射影座標系は、Jacobian座標系とする。
要するに、図６に示したアルゴリズムを実行する実施形態とする。
【００６９】
実施形態で説明する有限可換群演算装置の細部においては、整数論における数値計算処理が必要となる場合があるが、整数論における数値計算処理自体は、公知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略する（この点の技術水準を示す整数論における数値計算処理が可能なソフトウェアとしては、例えばＰＡＲＩ／ＧＰ、ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては、例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成１８年４月１２日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては、例えばインターネット〈URL: http://www.math.tu-berlin.de/algebra/〉［平成１８年４月１２日検索］を参照のこと。）。
また、この点に関する文献として、参考文献２を挙げることができる。
（参考文献２）  H. Cohen, "A Course in Computational Algebraic Number Theory", GTM 138, Springer-Verlag, 1993.
【００７０】
実施形態について、図面を参照しながら説明する。
＜有限可換群演算装置＞
図１５に例示するように、有限可換群演算装置（１）は、キーボードなどが接続可能な入力部（１１）、液晶ディスプレイなどが接続可能な出力部（１２）、ＣＰＵ（Central Processing Unit;１４）〔キャッシュメモリやレジスタ（１９）などを備えていてもよい。〕、メモリであるＲＡＭ（Random Access Memory）（１５）、ＲＯＭ（Read Only Memory）（１６）やハードディスクである外部記憶装置（１７）、並びにこれらの入力部（１１）、出力部（１２）、ＣＰＵ（１４）、ＲＡＭ（１５）、ＲＯＭ（１６）、外部記憶装置（１７）間のデータのやり取りが可能なように接続するバス（１８）などを備えている。また必要に応じて、有限可換群演算装置（１）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００７１】
有限可換群演算装置（１）の外部記憶装置（１７）には、有限可換群演算のためのプログラムおよびこのプログラムの処理において必要となるデータなどが保存記憶されている。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭ（１５）やレジスタ（１９）などに適宜に保存記憶される。以下、演算結果やその格納領域のアドレスなどを記憶するＲＡＭ（１５）やレジスタ（１９）などの装置を単に「記憶部」と呼ぶことにする。
【００７２】
外部記憶装置（１７）には、擬似逆元を算出するためのプログラム、補擬似逆元を算出するためのプログラム、有限体上乗算の演算結果を算出するためのプログラム、有限体上自乗の演算結果を算出するためのプログラム、有限体上加算あるいは減算あるいは１／２倍算の演算結果を算出するためのプログラムが保存記憶されている。その他、これらのプログラムに基づく処理を制御するための制御プログラムも適宜に保存しておく。また、外部記憶装置（１７）には、有限可換群の元Ｐの座標値（Ｘ１，Ｙ１，ｚ１）および楕円曲線の係数ａが保存記憶されているとする。
【００７３】
有限可換群演算装置（１）では、外部記憶装置（１７）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じて記憶部（２０）に読み込まれて、ＣＰＵ（１４）で解釈実行・処理される。この結果、ＣＰＵ（１４）が所定の機能（擬似逆元演算部、補擬似逆元演算部、乗算演算部、自乗演算部、加算減算半倍算演算部、制御部）を実現することで有限可換群演算が実現される。
【００７４】
＜実施形態の有限可換群演算処理＞
次に、図１６〜図１８を参照して、有限可換群演算装置（１）における有限可換群演算処理の流れを叙述的に説明する。なお、外部記憶装置（１７）に保存された有限可換群の元Ｐの座標値（Ｘ１，Ｙ１，ｚ１）および係数ａは、制御部（１９０）の制御によって、予め記憶部（２０）に読み込まれて保存されているとする。以後、「記憶部から○○を読み込む」旨の説明をした場合は、「記憶部において○○が格納されている所定の格納領域から○○を読み込む」ことを意味するとする。
制御部（１９０）は、下記のアルゴリズムの処理を実行する制御を行う。
【００７５】
［図６の１番目の演算ステップ］
Λｎ←ｖ（２Ｙ１）・（３Ｘ１２＋ａｚ１４）の演算を行う。この演算は、Λｎ←ｖ（Ｙ１＋Ｙ１）・｛（Ｘ１２＋Ｘ１２＋Ｘ１２）＋ａ・（ｚ１２・ｚ１２）｝なる演算と同じである〔但し、記号・は乗算を表す。以下同様。〕。ここでは、２Ｙ１を２・Ｙ１なる乗算で求めるのではなくＹ１＋Ｙ１なる加算で求め、３Ｘ１２を３・Ｘ１２なる乗算で求めるのではなくＸ１２＋Ｘ１２＋Ｘ１２なる加算で求め、ｚ１４をｚ１・ｚ１・ｚ１・ｚ１なる乗算で求めるのではなくｚ１２・ｚ１２あるいは（ｚ１２）２なる演算で求めるなど、演算コストを低減する工夫が行われていることに留意しなければならない〔図６の２番目以降の演算ステップについても同様である。〕。
【００７６】
まず、自乗演算部（１４１）は、記憶部（２０）からＸ１を読み込んでＸ１・Ｘ１なる演算を行ない〔１Ｓの演算コスト〕、この演算結果Ｘ１２を記憶部（２０）の所定領域に格納する（ステップＳ１）。なお、図１７右側には、各ステップの段階で記憶部（２０）に格納されている値を示すことにする。但し、常に各ステップで得られた値を格納しなければならない趣旨ではなく、後の演算に用いる必要がない値は適宜の段階で記憶部（２０）の格納領域から解放することができる。
【００７７】
また、自乗演算部（１４１）は、記憶部（２０）からｚ１を読み込んでｚ１・ｚ１なる演算を行ない〔部分体上自乗の演算コスト〕、この演算結果ｚ１２を記憶部（２０）の所定領域に格納する（ステップＳ２）。
【００７８】
次に、加算減算半倍算演算部（１４２）は、記憶部（２０）からＹ１を読み込んでＹ１＋Ｙ１なる演算を行ない〔加算の演算コスト〕、この演算結果２Ｙ１を記憶部（２０）の所定領域に格納する（ステップＳ３）。
【００７９】
また、加算減算半倍算演算部（１４２）は、記憶部（２０）からＸ１２を読み込んでＸ１２＋Ｘ１２なる演算を行ない〔加算の演算コスト〕、この演算結果２Ｘ１２を記憶部（２０）の所定領域に格納する（ステップＳ４）。
【００８０】
さらに、加算減算半倍算演算部（１４２）は、記憶部（２０）から２Ｘ１２を読み込んで２Ｘ１２＋Ｘ１２なる演算を行ない〔加算の演算コスト〕、この演算結果３Ｘ１２を記憶部（２０）の所定領域に格納する（ステップＳ５）。
【００８１】
次いで、自乗演算部（１４１）は、記憶部（２０）からｚ１２を読み込んでｚ１２・ｚ１２なる演算を行ない〔部分体上自乗の演算コスト〕、この演算結果ｚ１４を記憶部（２０）の所定領域に格納する（ステップＳ６）。
【００８２】
さらに、自乗演算部（１４１）は、記憶部（２０）から係数ａおよびｚ１４を読み込んでａ・ｚ１４なる演算を行ない〔部分体上乗算の演算コスト〕、この演算結果ａｚ１４を記憶部（２０）の所定領域に格納する（ステップＳ７）。
【００８３】
続いて、加算減算半倍算演算部（１４２）は、記憶部（２０）から３Ｘ１２およびａｚ１４を読み込んで３Ｘ１２＋ａｚ１４なる演算を行ない〔加算の演算コスト〕、この演算結果３Ｘ１２＋ａｚ１４を記憶部（２０）の所定領域に格納する（ステップＳ８）。
【００８４】
次に、擬似逆元演算部（１４３）は、記憶部（２０）から２Ｙ１を読み込んで擬似逆元ｖ（２Ｙ１）を算出し〔１Ｖの演算コスト〕、この結果ｖ（２Ｙ１）を記憶部（２０）の所定領域に格納する（ステップＳ９）。なお、擬似逆元ｖ（２Ｙ１）の算出は既述のとおりである。例えば拡大体の次数ｍ＝５の場合であれば、式（２９）に示したアルゴリズムで演算できる〔但し、式（２９）のｘを２Ｙ１に置換して理解すること。〕。
【００８５】
続いて、乗算演算部（１４４）は、記憶部（２０）からｖ（２Ｙ１）および３Ｘ１２＋ａｚ１４を読み込んでｖ（２Ｙ１）・（３Ｘ１２＋ａｚ１４）なる演算を行ない〔１Ｍの演算コスト〕、この演算結果ｖ（２Ｙ１）・（３Ｘ１２＋ａｚ１４）を記憶部（２０）の所定領域に格納する（ステップＳ１０）。ここで得られた演算結果ｖ（２Ｙ１）・（３Ｘ１２＋ａｚ１４）がΛｎに相当することとなる。
【００８６】
［図６の２番目の演算ステップ］
λｄ←Ｎ（２Ｙ１）の演算を行う。この演算は、λｄ←Ｎ（Ｙ１＋Ｙ１）なる演算と同じである。ここで留意しなければならないことは、演算Ｙ１＋Ｙ１をする必要がないということである。何故なら、上記ステップＳ３で演算結果２Ｙ１を得ているからである。そこで、図６の２番目の演算ステップでは、次の演算を行えばよいことになる。
【００８７】
即ち、補擬似逆元演算部（１４５）は、記憶部（２０）から２Ｙ１を読み込んで補擬似逆元Ｎ（２Ｙ１）を算出し〔補擬似逆元の演算コスト〕、この結果Ｎ（２Ｙ１）を記憶部（２０）の所定領域に格納する（ステップＳ１１）。なお、補擬似逆元Ｎ（２Ｙ１）の算出は既述のとおりである。例えば拡大体の次数ｍ＝５の場合であれば、式（２９）に示したアルゴリズムで演算できる〔但し、式（２９）のｘを２Ｙ１に置換して理解すること。〕。ここで得られた演算結果Ｎ（２Ｙ１）がλｄに相当することとなる。
【００８８】
［図６の３番目以降の演算ステップ］
図６の３番目以降の演算ステップも、上記で説明した演算処理と同様にすればよい。つまり、３番目の演算ステップでは、ｚ３←λｄ・ｚ１なる演算を行う。４番目の演算ステップでは、Ｘ"１←Ｘ１・λｄ２およびＹ"１←Ｙ１・λｄ３＝Ｙ１・λｄ２・λｄなる演算を行う（λｄ２は再計算する必要が無い。）。５番目の演算ステップでは、Ｘ３←Λｎ２−（Ｘ"１＋Ｘ"１）なる演算を行う。６番目の演算ステップでは、Ｙ３←Λｎ・（Ｘ"１−Ｘ３）−Ｙ"１なる演算を行う。これらの演算は何れも、自乗演算部（１４１）、加算減算半倍算演算部（１４２）、乗算演算部（１４４）によって実現される。各演算部の処理は、図６の１番目および２番目の演算ステップで説明したのと同様である（図１７のステップＳ１１以降は省略している。）。
【００８９】
次に、上記（条件）のうち条件３．を「群演算は、楕円加算とする。」に変更した場合の有限可換群演算処理について説明する。つまり、図５に示したアルゴリズムを実行する実施形態である。
図５の各演算ステップも、上記実施形態で説明した演算処理と同様にすればよい。
１番目の演算ステップでは、ｚ′３←ｚ１・ｚ２なる演算を行う。
２番目の演算ステップでは、Ｘ′１←Ｘ１・ｚ２２およびＹ′１←Ｙ１・ｚ２３＝Ｙ１・ｚ２２・ｚ２なる演算を行う（ｚ２２は再計算する必要が無い。）。
３番目の演算ステップでは、Ｘ′２←Ｘ２・ｚ１２およびＹ′２←Ｙ２・ｚ１３＝Ｙ２・ｚ１２・ｚ１なる演算を行う（ｚ１２は再計算する必要が無い。）。
４番目の演算ステップでは、Λｎ←ｖ（Ｘ′２−Ｘ′１）・（Ｙ′２−Ｙ′１）なる演算を行う。この演算は、ｖ（Ｘ′２−Ｘ′１）およびＹ′２−Ｙ′１をそれぞれ求めて乗算する。
５番目の演算ステップでは、λｄ←Ｎ（Ｘ′２−Ｘ′１）なる演算を行う。
６番目の演算ステップでは、ｚ３←λｄ・ｚ′３なる演算を行う。
７番目の演算ステップでは、Ｘ"１←Ｘ′１・λｄ２およびＹ"１←Ｙ′１・λｄ３＝Ｙ′１・λｄ２・λｄなる演算を行う（λｄ２は再計算する必要が無い。）。
８番目の演算ステップでは、Ｘ"２←Ｘ′２・λｄ２なる演算を行う（λｄ２は再計算する必要が無い。）。
９番目の演算ステップでは、Ｘ３←Λｎ２−（Ｘ"１＋Ｘ"１）なる演算を行う。
１０番目の演算ステップでは、Ｙ３←Λｎ・（Ｘ"１−Ｘ３）−Ｙ"なる演算を行う。
【００９０】
これらの演算は何れも、楕円２倍算を例とした実施形態で説明したのと同様に、自乗演算部（１４１）、加算減算半倍算演算部（１４２）、擬似逆元演算部（１４３）、乗算演算部（１４４）、補擬似逆元演算部（１４５）によって実現される。また、楕円加算を例としたこの実施形態での各演算部の処理も、楕円２倍算を例とした実施形態で説明したのと同様である。
図１９に、擬似逆元演算を用いたJacobian座標系における楕円加算の有限可換群演算処理の処理フロー（全体）を示す。
【００９１】
以上の実施形態の他、本発明である有限可換群演算装置・方法は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記有限可換群演算装置・方法において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００９２】
また、上記有限可換群演算装置における処理機能をコンピュータによって実現する場合、有限可換群演算装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記有限可換群演算装置における処理機能がコンピュータ上で実現される。
【００９３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００９４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００９６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、有限可換群演算装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００９７】
本発明は、有限体上定義された代数曲線暗号の演算などに有用である。
【図面の簡単な説明】
【００９８】
【図１】Affine座標における楕円加算のアルゴリズムの一例と演算コストを示した図。
【図２】Affine座標における楕円２倍算のアルゴリズムの一例と演算コストを示した図。
【図３】Jacobian座標における楕円加算のアルゴリズムの一例と演算コストを示した図。
【図４】Jacobian座標における楕円２倍算のアルゴリズムの一例と演算コストを示した図。
【図５】擬似逆元演算を用いたJacobian座標における楕円加算のアルゴリズムの一例と演算コストを示した図。
【図６】擬似逆元演算を用いたJacobian座標における楕円２倍算のアルゴリズムの一例と演算コストを示した図。
【図７】Projective座標における楕円加算のアルゴリズムの一例と演算コストを示した図。
【図８】擬似逆元演算を用いたProjective座標における楕円加算のアルゴリズムの一例と演算コストを示した図。
【図９】Projective座標における楕円２倍算のアルゴリズムの一例と演算コストを示した図。
【図１０】擬似逆元演算を用いたProjective座標における楕円２倍算のアルゴリズムの一例と演算コストを示した図。
【図１１】Chudnovsky座標における楕円加算のアルゴリズムの一例と演算コストを示した図。
【図１２】擬似逆元演算を用いたChudnovsky座標における楕円加算のアルゴリズムの一例と演算コストを示した図。
【図１３】Chudnovsky座標における楕円２倍算のアルゴリズムの一例と演算コストを示した図。
【図１４】擬似逆元演算を用いたChudnovsky座標における楕円２倍算のアルゴリズムの一例と演算コストを示した図。
【図１５】有限可換群演算装置のハードウェア構成例を示す図。
【図１６】有限可換群演算装置の機能構成例を示す図。
【図１７】有限可換群演算処理（擬似逆元演算を用いたJacobian座標系における楕円２倍算の例）の処理フロー（一部）および保存記憶されている演算結果を示す図。
【図１８】有限可換群演算処理（擬似逆元演算を用いたJacobian座標系における楕円２倍算の例）の処理フロー（全体）を示す図。
【図１９】有限可換群演算処理（擬似逆元演算を用いたJacobian座標系における楕円加算の例）の処理フロー（全体）を示す図。
【符号の説明】
【００９９】
１    有限可換群演算装置
１４１    自乗演算部
１４２    加算減算半倍算演算部
１４３    擬似逆元演算部
１４４    乗算演算部
１４５    補擬似逆元演算部
１９０    制御部
【図１】
0004621162.tif 000031
【図２】
0004621162.tif 000032
【図３】
0004621162.tif 000033
【図４】
0004621162.tif 000034
【図５】
0004621162.tif 000035
【図６】
0004621162.tif 000036
【図７】
0004621162.tif 000037
【図８】
0004621162.tif 000038
【図９】
0004621162.tif 000039
【図１０】
0004621162.tif 000040
【図１１】
0004621162.tif 000041
【図１２】
0004621162.tif 000042
【図１３】
0004621162.tif 000043
【図１４】
0004621162.tif 000044
【図１５】
0004621162.tif 000045
【図１６】
0004621162.tif 000046
【図１７】
0004621162.tif 000047
【図１８】
0004621162.tif 000048
【図１９】
0004621162.tif 000049