(57)【要約】【課題】一般的なＣＰＵを使用してリダクション演算を行う場合に、処理ステップを低減して高速化できる既約多項式によるリダクション演算方法の実現。【解決手段】ＣＰＵ21を使用してソフトウエア制御により有限体の剰余演算を行う有限体演算方法であって、既約多項式によるリダクション演算を行う時に、既約多項式の次数、中間項の次数および既約多項式の次数から中間項の次数を減じた値の少なくとも１つが、ＣＰＵの演算処理のワード幅の倍数である既約多項式を使用する。【選択図】図５
2008197625.tif 000002
【特許請求の範囲】
【請求項１】
ＣＰＵを使用してソフトウエア制御により有限体の剰余演算を行う有限体演算方法であって、
既約多項式によるリダクション演算を行う時に、既約多項式の次数、中間項の次数および既約多項式の次数から中間項の次数を減じた値の少なくとも１つが、前記ＣＰＵの演算処理のワード幅の倍数である既約多項式を使用することを特徴とする有限体演算方法。
【請求項２】
リダクション演算の対象である有限体上の対象多項式の各項の係数を表すビットデータのそれぞれを、連続したビットデータとして記憶し、前記ＣＰＵの演算処理のワード幅に対応するビット数のデータを並列に処理する請求項１に記載の有限体演算方法。
【請求項３】
前記有限体は標数が３の有限体で、前記既約多項式の項数は３項以上であり、
リダクション演算の対象である有限体上の対象多項式の各項の係数を２ビットのデータで表し、各項の上位ビットと下位ビットをそれぞれ連続したビットデータとして記憶する請求項１または２に記載の有限体演算方法。
【請求項４】
前記既約多項式は３項式であり、中間項の次数が前記ＣＰＵの演算処理のワード幅の倍数であり、リダクション演算の対象である有限体上の対象多項式の各項の係数を表すビットデータのそれぞれを、連続したビットデータとして記憶し、前記ＣＰＵの演算処理のワード幅に対応するビット数のデータを並列に処理し、
前記対象多項式の前記既約多項式の次数以上のリダクション対象部分を、上位ビットから順に前記ワード幅単位で、前記既約多項式の次数に対応する項を前記ワード幅内の最小ビットに対応するようにシフトさせるシフト量だけシフトし、シフトしたワード幅単位のデータを、次数が前記既約多項式の第１項と中間項及び定数項との関係にある前記対象多項式の対応する項に加減算する請求項１に記載の有限体演算方法。
【請求項５】
ＣＰＵを備え、ソフトウエア制御により有限体の剰余演算を行う有限体演算装置であって、
既約多項式の次数、中間項の次数および既約多項式の次数から中間項の次数を減じた値の少なくとも１つが、前記ＣＰＵの演算処理のワード幅の倍数である既約多項式を使用してリダクション演算を行うリダクション演算手段を備えることを特徴とする有限体演算装置。
【請求項６】
前記リダクション演算手段は、リダクション演算の対象である有限体上の対象多項式の各項の係数を表すビットデータのそれぞれを、連続したビットデータとして記憶する係数記憶手段を備え、前記ＣＰＵの演算処理のワード幅に対応するビット数のデータを並列に処理する請求項５に記載の有限体演算装置。
【請求項７】
前記有限体は標数が３の有限体で、前記既約多項式の項数は３項以上であり、
前記リダクション演算手段は、リダクション演算の対象である有限体上の対象多項式の各項の係数を２ビットのデータで表し、各項の上位ビットと下位ビットをそれぞれ連続したビットデータとして記憶する係数記憶手段を備える請求項５に記載の有限体演算装置。
【請求項８】
前記既約多項式は３項式であり、中間項の次数が前記ＣＰＵの演算処理のワード幅の倍数であり、
前記リダクション演算手段は、
リダクション演算の対象である有限体上の対象多項式の各項の係数を表すビットデータのそれぞれを、連続したビットデータとして記憶する係数記憶手段を備え、
前記ＣＰＵの演算処理のワード幅に対応するビット数のデータを並列に処理し、
前記対象多項式の前記既約多項式の次数以上のリダクション対象部分を、上位ビットから順に前記ワード幅単位で、前記既約多項式の次数に対応する項を前記ワード幅内の最小ビットに対応するようにシフトさせるシフト量だけシフトし、シフトしたワード幅単位のデータを、次数が前記既約多項式の第１項と中間項及び定数項との関係にある前記対象多項式の対応する項に加減算する請求項５に記載の有限体演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限体（ガロア体）ＧＦ（ｑ）の演算方法に関し、特に既約多項式による剰余演算のリダクション演算の演算方法に関する。
【背景技術】
【０００２】
デジタルオーディオ機器などのエラー訂正方式、公開キー暗号方式などの技術分野で有限体（ガロア体）の演算が広く行われている。有限体の演算において、楕円曲線上の点のペアリングが持つ双線形性を応用して、効率的な暗号システムが実現できることが知られている。ペアリングにはWeilペアリングとTateペアリングがあり、Tateペアリングの方が計算量が少ないため暗号分野ではTateペアリングないしその改良版が用いられる。それでもTateペアリングは計算量が大きいため、現在まで種々の高速化手法が提案されている。
【０００３】
Tateペアリングを高速化した代表的なアルゴリズムとしてDuursma-Leeアルゴリズム・ηTペアリングが研究されている。これらの演算では標数３の有限体ＧＦ（３m）上の乗算が大部分を占める。従って高速化のためにはＧＦ（３m）上の乗算を効率化することが重要になる。以下、標数３の有限体ＧＦ（３m）における例を説明するが、本発明の演算方法及び演算装置は標数３の有限体ＧＦ（３m）に限定されるものではない。
【０００４】
非特許文献１は、Tateペアリング演算の高速化について記載しており、楕円曲線暗号におけるペアリングの高速計算で、有限体ＧＦ（３m）の乗算を必要とすること、及びペアリングを用いることでＩＤベース暗号等の新しい暗号システムが可能になること、を記載している。
【０００５】
非特許文献１に記載されるように、ペアリングの計算には、計算量の多い標数３の有限体ＧＦ（３m）の乗算が多数回必要である。ＧＦ（３m）の乗算は、次の２段階で計算される。
【０００６】
（１）ＧＦ（３）の元を係数に持つｍ−１次以下の２個の多項式の積を計算する。この計算結果は、ＧＦ（３）の元を係数とする２ｍ−２次以下の多項式になる。
【０００７】
（２）（１）で得られる積の多項式ｆ（ｘ）に対して、ＧＦ（３）の元を係数とするｍ次既約多項式ｐ（ｘ）による剰余ｇ（ｘ）＝ｆ（ｘ）ｍｏｄｐ（ｘ）を計算する。この値はＧＦ（３）の元を係数とするｍ−１次以下の多項式であり、これがＧＦ（３m）の乗算の結果になる。上記のｆ（ｘ）ｍｏｄｐ（ｘ）の演算では、多項式ｆ（ｘ）のｍ次以上の項に対するリダクション演算が行われる。
【０００８】
リダクションの対象であるＧＦ（３）上のｎ次の多項式をｆ（ｘ）、ＧＦ（３）上のｍ次既約多項式をｐ（ｘ）とする。ここで、ｎ≧ｍとする（ｎ＜ｍの場合はｇ（ｘ）＝ｆ（ｘ））。リダクション演算は、ｐ（ｘ）による剰余演算によりｆ（ｘ）をｍ−１次以下の多項式ｇ（ｘ）に変換する演算である。以下、リダクション演算について説明する。
【０００９】
ｆ（ｘ）及びｐ（ｘ）は、次のように表すことができる。（一般にｐ（ｘ）のｍ次の高の係数は１）
f(x)=cnxn+cn-1xn-1+...+c1x+c0      （１）
p(x)=xm+dm-1xm-1+...+d1x+d0      （２）
Ｐ（ｘ）＝０の関係式から次の式が得られる。
【００１０】
xm=-dm-1xm-1+...-d1x-d0      （３）
この式を用いて、ｆ（ｘ）のｍ次以上の各項を置き換える。具体的には、まず式（３）のｘmがｆ（ｘ）の一番上の項と等しくなるように、両側にcnxn-mを乗じると次の式が得られる。
【００１１】
cnxn=-cndm-1xn-1+...-cnd1xn-m+1-cnd0xn-m      （４）
そして、ｆ（ｘ）の第１項を（４）の右側の式で置き換えると、次の式が得られる。
【００１２】
f(x)=(cn-1-cndm-1)xn-1+(cn-2-cndm-2)xn-2...+(cn-m+1-cnd1)xn-m+1
+(cn-m-cnd0)xn-m+cn-m-1xn-m-1+c1x+c0      （５）
この式（５）は、ｎ−１次の多項式であり、ｆ（ｘ）の次数が１つだけ小さいｎ−１次の多項式になる。
【００１３】
次に、ｎ−１次の多項式である式（５）について、上記と同様に第１項を置き換える処理を行い、ｎ−２次の多項式にする。以下、同じ処理を、ｍ−１次の多項式が得られるまで繰り返す。得られた結果が、ｍｏｄ演算の結果ｇ（ｘ）になる。
【００１４】
ＧＦ（３）上のｍ次既約多項式は、各ｍについて複数存在する場合が多い。アプリケーションの目的において、ｍのみ指定され、実際の演算で使用するｍ次既約多項式の選択に自由度がある場合に、効率的にリダクション演算が実行できるｍ次既約多項式を考える。なお、ここでは、固定されたｍ次既約多項式を対象とする専用のハードウエアを使用せずに、一般的なＣＰＵを用いたソフトウエア処理により演算を実行するものとする。
【００１５】
上記のリダクション演算の方法から、リダクション演算に用いる既約多項式の項数はできるだけ少ない方が効率的であるのは明らかである。ＧＦ（３）上の既約多項式のうち２項式はｘ2＋１のみであるため、３項式ｘm＋ａｘk＋ｂ（ｍ＞ｋ＞０；ａ，ｂ∈ＧＦ（３）；ａｂ≠０）が候補となる。
【００１６】
既約多項式を使用した剰余演算については、特許文献１などに記載されているので、これ以上の説明は省略する。
【００１７】
【非特許文献１】白勢・高木・岡本，「Ｔａｔｅペアリングの効率的なアルゴリズム」信学技報ISEC2006-12,0019-26，電子情報通信学会
【非特許文献２】境・大岸・笠原，「ペアリングに基づく暗号方式」暗号理論とそれを支える代数曲線理論，第１回ワークショップ(2000年8月30日−9月1日，中央大学市ヶ谷キャンパス）
【非特許文献３】G. Granger, D. Page & M. Stam, "Hardware and Software Normal Basis Arithmetic for Pairing Based Cryptography in Characteristic Three", IEEE Trans. on Computers, Vol.54, No.7, pp852.860, 2005
【特許文献１】特開２０００−１４８０１３
【発明の開示】
【発明が解決しようとする課題】
【００１８】
上記のように、ＧＦ（３m）の乗算におけるリダクション演算では、既約３項式ｘm＋ａｘk＋ｂが候補になる。ハードウエア実装を含む従来例では、それらのうち最小のｋを有するものがこれまでは用いられてきた。
【００１９】
ここでは、一般的なＣＰＵを使用してリダクション演算を行う場合に、処理ステップを低減して高速化することを目的とする。
【課題を解決するための手段】
【００２０】
上記目的を実現するため、この有限体演算方法および装置は、一般的なＣＰＵを使用して既約多項式でリダクション演算を行う場合に、既約多項式の次数、中間項の次数および既約多項式の次数から中間項の次数を減じた値の少なくとも１つが、ＣＰＵの演算処理のワード幅の倍数である既約多項式を使用する。これにより、リダクション演算におけるシフト処理の一部を省略できる。
例えば、中間項の次数がワード幅の倍数である場合を説明する。ワード幅がＷビットで、既約多項式が３項式のｘm＋ａｘk＋ｂで表され、中間項の次数がワード幅の倍数であるとする。すなわち、ｋ＝Ｗ×ｇ（ｇは１以上の整数）とする。ｍはＷより大きく、ペアリング演算であれば、通常は９０以上である。
【００２１】
上記のように、ＧＦ（３m）の乗算におけるリダクション演算では、既約３項式ｘm＋ａｘk＋ｂが候補であり、従来は最小のｋを有するものが多く、少なくともＣＰＵを使用してソフトウエア制御により演算を行う場合に、演算の効率化を目的として中間項の次数がＣＰＵのワード幅の倍数であるように意図したものはなかった。
【００２２】
ＣＰＵを使用してソフトウエア制御により既約多項式によるリダクション演算を行う時には、リダクション演算の対象である有限体上の対象多項式の各項の係数を表すビットデータのそれぞれを、連続したビットデータとして記憶し、前記ＣＰＵの演算処理のワード幅に対応するビット数のデータを並列に処理する。この際に、対象多項式の前記既約多項式の次数以上のリダクション対象部分を、上位ビットから順にワード幅単位で、既約多項式の次数に対応する項をワード幅内の最小ビットに対応するようにシフトさせるシフト量だけシフトし、シフトしたワード幅単位のデータを、次数が既約多項式の第１項と中間項及び定数項との関係にある対象多項式の対応する項に加減算することが行われる。この場合、本発明のように中間項の次数がＣＰＵのワード幅の倍数であれば、中間項及び定数項の加減算のためのワード幅内でのシフト量が同一であり、シフト処理が共通化できるので、その分処理量を低減できる。
【００２３】
シフト処理の低減は、上記の場合に限られず、既約多項式の次数がＣＰＵの演算処理のワード幅の倍数であれば、定数項の加減算処理で格納されている係数がワード幅単位でシフトするだけで使用できるので、定数項の加減算のためのワード幅内でのシフト処理は不要になる。また既約多項式の次数から中間項の次数を減じた値がＣＰＵの演算処理のワード幅の倍数であれば、中間項の加減算のためのワード幅内でのシフト処理は不要になり、処理量を低減できる。これは、既約多項式が４項以上である場合も同様であり、各項が次数がワード幅の倍数であれば上記と同様にワード幅内でのシフト処理が不要になり、中間項同士の次数の差がＣＰＵの演算処理のワード幅の倍数であればそれらの中間項の加減算のためのシフト量が同一であるのでワード幅内でのシフト処理が共通化できる。
【００２４】
後述する例では、Ｔａｔｅペアリングの高速化に適した標数が３の有限体で、既約多項式は３項式である例を説明するが、既約多項式の次数、中間項の次数および既約多項式の次数から中間項の次数を減じた値の少なくとも１つがＣＰＵのワード幅の倍数であるという本発明の特徴は、標数２などの標数３以外の有限体でも有効であり、また上記のように既約多項式が４項以上である場合も有効である。
【００２５】
標数が３の場合、リダクション演算の対象である有限体上の対象多項式の各項の係数は２ビットのデータで表せるが、各項の上位ビットと下位ビットをそれぞれ連続したビットデータとして記憶し、ＣＰＵの演算処理のワード幅に対応するビット数のデータを並列に処理する。
【発明の効果】
【００２６】
記載される実施例によれば、ＣＰＵを使用してソフトウエア制御により有限体の剰余演算で発生する既約多項式によるリダクション演算を行う時の処理量を低減して高速化が図れる。
【発明を実施するための最良の形態】
【００２７】
実施例の有限体演算装置は、図１に示すようなハードウエア構成の演算装置を使用して、ハードウエアにインストールするプログラムによるソフトウエア制御により実現され、有限体演算が実行される。
【００２８】
図１（Ａ）に示すように、実施例で使用するハードウエアは、ＣＰＵ２１と、ＲＯＭ２５と、ＲＡＭ２６と、Ｉ／Ｏ２７、これらを接続する外部バス２８と、を有する一般的なコンピュータである。ＣＰＵ２１は、内部に演算ユニット（ＡＬＵ）２２と、レジスタ群２３とそれらを接続する内部バス２４と、を有する。内部バス２４はワード幅（ビット幅）は１６ビットであり、ＣＰＵ２１は各種処理を１６ビットのワード幅で行う。なお、ここではワード幅が１６ビットのＣＰＵを使用するが、これに限定されるものではなく、広く使用される８ビット、３２ビット、６４ビットのワード幅のＣＰＵを使用してもよい。
【００２９】
図１（Ｂ）は、実施例の有限体演算装置の機能ブロック図である。図１（Ｂ）に示すように、有減退演算部(装置）３１は、リダクション演算部３２を有する。リダクション演算部３２は、対象多項式の各項の係数を連続したビットデータとして記憶し、レジスタ群２３により実現される計数記憶部３３を有する。
【００３０】
第１実施例は、３項式の既約多項式で、中間項の次数がＣＰＵ２１のワード幅の倍数、すなわち１６の倍数である場合である。
図２は、第１実施例におけるリダクション演算フローを示す図である。ここでは、演算対象の対象多項式ｆ（ｘ）（ｎ次）を既約３項式ｐ（ｘ）（ｍ次）で剰余演算する時のリダクション演算を行うものとし、ｆ（ｘ）は前述の式（１）で表され、ｐ（ｘ）は次の式（６）で表される場合を例として説明する。
【００３１】
p(x)=xm+axk+b      （６）
ステップ１０１では、既約３項式のパラメータｍ、ｋ、ａ、ｂ及びワード幅（ビット数）Ｗ（ここでは１６ビット）を入力する。
【００３２】
ステップ１０２では、ｆ（ｘ）の係数をワード幅単位で格納する時の、ｍ次の項及び第１項（ｎ次の項）のワード幅内での位置を示すＲとｙ、及び既約３項式の中間項（ｋ次の項）のワード幅内での位置を示すＫを算出する。Ｒ，ｙ，Ｋは次の式で表される。
【００３３】
Ｒ＝ｍ  ｍｏｄ  Ｗ
ｙ＝（ｎ＋１）  ｍｏｄ  Ｗ
Ｋ＝ｔｒｕｎｃａｔｅ（ｋ／Ｗ）
ここで、ｔｒｕｎｃａｔｅは小数点未満を切り捨てた値を示す。
【００３４】
ステップ１０３では、ｙがＲ以下であるか判定し、ｙがＲ以下であればステップ１０４Ｂに、ｙがＲより大きければステップ１０４Ａに進む。
【００３５】
ステップ１０４Ａ及び１０４Ｂでは、演算に使用する変数ｉの最大値ｍａｘと最小値ｍｉｎを算出する。ｍａｘはステップ１０４Ａと１０４Ｂで異なる。ステップ１０４Ａでは、
ｍａｘ＝ｒｏｕｎｄｕｐ｛（ｎ＋１）／Ｗ｝
ｍｉｎ＝ｒｏｕｎｄｕｐ｛ｍ／Ｗ｝−１
ステップ１０４Ｂでは、
ｍａｘ＝ｒｏｕｎｄｕｐ｛（ｎ＋１）／Ｗ｝−１
ｍｉｎ＝ｒｏｕｎｄｕｐ｛ｍ／Ｗ｝−１
に設定される。ここで、ｒｏｕｎｄｕｐは小数点以下を切り上げた値を示す。
【００３６】
ステップ１０４Ａと１０４Ｂの後はステップ１０５に進む。
【００３７】
ステップ１０５では、要素数がｍａｘの配列Ｈ，Ｌを確保して、ｆ（ｘ）の係数データを配列Ｈ，Ｌに格納する。図３は、第１実施例の計数記憶部３３における係数データの格納方法を説明する図である。
【００３８】
標数３の有限体であるので、係数は０，１，２のいずれかであり、係数データは２ビットで表すことができる。格納用配列は、ワード幅（１６ビット）単位であり、１配列単位は２ビットの上位ビットを格納するＨ（ｉ）と、下位ビットを格納するＬ（ｉ）と、で構成され、このような配列がＨ（０）からＨ（ｍａｘ）まで（およびＬ（０）からＬ（ｍａｘ）まで）確保される。例えば、ｎが１８９で、ｍが９７である場合には、Ｒ＝１、ｙ＝１４、であるからステップ１０４Ｂによりｍａｘ＝１１になり、配列ＨについてはＨ（０）からＨ（１１）までの１２配列単位が確保される。１２配列単位では１２×１６＝１９２ビットを格納可能であり、Ｈ（１１）の上位２ビットには係数データが格納されないことになるので、そこにはゼロを入れる。
【００３９】
ステップ１０６では、変数ｉをｍａｘに設定し、ステップ１０７でｉがｍｉｎより小さいかを判定し、小さければステップ１１０に進むが、それ以外の場合にはステップ１０８に進む。
【００４０】
ステップ１０８では、加減算を行うためにｆ（ｘ）のリダクション対象部分をｐ（ｘ）の中間項及び定数項の位置に合わせるためのデータの生成と対応配列位置の演算を行う。
【００４１】
リダクション演算では、ｆ（ｘ）のリダクション対象部分のあるビットにｐ（ｘ）の第１項を対応させ、中間項及び定数項に対応するビットに対して、ビット値に応じた加減算処理を行う。従って、ｆ（ｘ）のリダクション対象部分の最終ビット、すなわちｐ（ｘ）の次数に対応するビットが、定数項に対応するように、すなわちワード幅の最終ビットに対応するようにシフトすると、ワード幅（１６ビット）単位で演算を行うのに適当である。このシフト量は、Ｗ−Ｒで表される。
【００４２】
リダクション演算は、リダクション対象部分の上位ビットから順番に行う必要があるので、Ｈ（１２）の右側Ｒ個とＨ（１１）の左側Ｗ−Ｒ個のビットデータ列を連結してｔｈとし、Ｌ（１２）の右側Ｒ個とＨ（１１）の左側Ｗ−Ｒ個のビットデータ列を連結してｔｌとし、ワード（１６ビット）幅のデータを作る。このデータに応じて加減算処理が行われるのはｐ（ｘ）の中間項に対応するＨ（ｊ１）と、定数項に対応するＨ（ｊ２）である。ｊ１とｊ２は、次の式で表される。
【００４３】
ｊ１＝ｉ−ｍｉｎ＋Ｋ
ｊ２＝ｉ−ｍｉｎ
ステップ１０９では、生成したｔｈ及びｔｌを、ｆ（ｘ）の対応する配列位置に対して、ｐ（ｘ）のａ及びｂに応じて加減算する。
【００４４】
図４は、この演算処理を示す図である。ここではｐ（ｘ）の中間項の係数ａについて説明するが、定数項の係数ｂについても同様である。
【００４５】
図４の（Ａ）に示すように、この演算は標数３の有限体上での演算であり、ａが１であれば、ｆ（ｘ）の対応するビット値（Ｈ（ｊ１），Ｌ（ｊ１）からの（ｔｈ，ｔｌ）の減算に置き換えることができ、ａが２であれば、ｆ（ｘ）の対応するビット値（Ｈ（ｊ１），Ｌ（ｊ１）への（ｔｈ，ｔｌ）の加算に置き換えることができ、計算結果をｆ（ｘ）に上書きする。この演算は、ワード幅の全ビットに対して並列に行う。
【００４６】
図４の（Ｂ）は、（Ａ）で説明した処理をフロー図で示したものであり、加算関数のｔｈとｔｌが入れ替わっていることに注目する必要がある。
【００４７】
図４の（Ｃ）は、加算関数の実際の処理を示すフロー図であり、ｆ（ｘ）のＨ及びＬレジスタの値、ｔｈ（ｈ）及びｔｌ（ｌ）の値、及びそれらの算出地の間でＯＲ及びＸＯＲを演算することにより、上書きする値を算出することができる。有限体の演算については広く知られているので、説明は省略する。
【００４８】
ステップ１０９では、上記の処理が終了すると、Ｈ（ｉ）及びＬ（ｉ）の全ビットをゼロに設定し、変数ｉを１だけ減少させてステップ１０７に戻る。
【００４９】
以下、演算対象の配列単位を１単位ずつずらしながら、ｐ（ｘ）の第１項の次数に対応する項の処理が終了するまでステップ１０８及び１０９の処理を繰り返し、その項の処理が終了したら、ステップ１０７からステップ１１０に進み、Ｈ（ｉ）及びＬ（ｉ）の左側Ｗ−Ｒ個のビットをゼロにして終了する。
【００５０】
以上、第１実施例の演算処理を説明したが、第１実施例では、既約多項式の中間項の次数がＣＰＵのワード幅の倍数であるので、中間項は定数項と同様にワード幅のＬＳＢに対応しており、中間項と定数項の演算のためのシフト量が同じであり、シフト処理が共通化できるので、演算量を低減できる。
【００５１】
次に、上記の処理を具体的な既約３項式を例として、図５を参照して説明する。
【００５２】
図５は、対象多項式ｆ（ｘ）の次数ｎが１８９で、既約３項式ｐ（ｘ）のパラメータｍ、ｋ、ａ、ｂがそれぞれ９７、１６、１、２である場合、すなわちｐ（ｘ）が次の式で表される場合の例である。
【００５３】
p(x)＝x97+x16+2
図示のように、ｆ（ｘ）の次数ｎが１８９であるから、Ｈ（０）からＨ（１２）までの１３配列単位が確保され、リダクション演算ではｐ（ｘ）の次数９７より小さい次数９６にすればよいので、ｆ（ｘ）の０ビットから９６ビットまでの９７ビット分がリダクション結果の範囲であり、９７ビットから１８９ビットまでの９３ビット分がリダクション対象部分である。
【００５４】
ｆ（ｘ）のリダクション対象部分の最終ビット、すなわちｐ（ｘ）の次数に対応するビットが、定数項に対応するように、すなわちワード幅の最終ビットに対応するようにシフトする。このシフト量は、Ｗ−Ｒで表され、図５では、ｆ（ｘ）の９７ビットが１６ビット幅のＬＳＢになるように１５ビットシフトされる。
【００５５】
リダクション演算は、リダクション対象部分の上位ビットから順番に行う必要があるので、Ｈ（１２）の右側１ビットとＨ（１１）の左側の１５ビットの列を連結してｔｈとし、Ｌ（１２）の右側１ビットとＬ（１１）の左側の１５ビットの列を連結してｔｌとし、ワード（１６ビット）幅のデータを作る。このデータに応じて加減算処理が行われるのはｐ（ｘ）の中間項に対応する６配列単位離れたＨ（６）と、定数項に対応する７配列単位離れたＨ（５）である。このように中間項に対応する配列と定数項に対応する配列は、ワード幅分ずれているので、シフト処理は共通に行える。
【００５６】
加減算処理は上記のように行われる。
【００５７】
加減算処理が終了すると、Ｈ（１２）とＬ（１２）の全ビットをゼロにして、変数ｉを１だけ減じて１１として、同様の動作を繰り返す。
【００５８】
ｉが６になるとリダクション対象部分に対する上記演算処理が終了する。この時、Ｈ（６）の左側Ｗ−Ｒ個（１５）ビットはゼロになっていないので、この部分をゼロにする処理を行って終了する。
【００５９】
ここで、本発明の効果を説明するために、対象多項式ｆ（ｘ）の次数ｎは１８９で図５の例と同じで、既約３項式ｐ（ｘ）のパラメータｍ、ｋ、ａ、ｂがそれぞれ９７、１２、１、２である場合を、図６に示す。すなわち、図６では、ｐ（ｘ）が次の式で表される。
【００６０】
p(x)＝x97+x12+2
図６に示すように、ｐ（ｘ）の中間項に対応する加減算を行うには、ｆ（ｘ）の９７ビットがワード幅内の１２ビットに対応するように１１ビット分シフトする必要がある。そこで、ｆ（ｘ）のＨ（１２）とＨ（１１）でこのようなシフトを行い、ｔｈ及びｔｌを生成し、Ｈ（６）に対して加減算を行う。
【００６１】
この処理が終了すると、ｐ（ｘ）の定数項に対応する加減算を行うために、ｆ（ｘ）の９７ビットがワード幅内の０ビットに対応するように１５ビット分シフトする処理を、ｆ（ｘ）のＨ（１２）とＨ（１１）で行い、ｔｈ及びｔｌを生成し、Ｈ（６）に対して加減算を行う。
【００６２】
次に、Ｈ（１１）とＨ（１０）で１１ビット分のシフト処理を行ってｔｈ及びｔｌを生成し、Ｈ（５）に対して中間項に対応する加減算を行う。そして、Ｈ（１１）とＨ（１０）で１５ビット分のシフト処理を行ってｔｈ及びｔｌを生成し、Ｈ（５）に対して定数項に対応する加減算を行う。
【００６３】
以下、このような処理を繰り返す。
このように、ｍ＝１２の場合、中間項と定数項に対する加減算を行うためのシフト量が異なるので、中間項演算のためのシフト処理と定数項演算のためのシフト処理を別々に行う必要がある。
【００６４】
第１実施例では、ワード幅が１６ビットの場合を例として、既約３項式の中間項の次数がワード幅の倍数の場合を説明したが、同様の効果は、既約３項式の次数がワード幅の倍数である場合や、既約３項式の次数から中間項の次数を減じた値がワード幅の倍数である場合にも得られる。既約多項式の次数がワード幅の倍数である場合には、定数項の加減算のためのシフト処理が不要になる。また既約３項式の次数から中間項の次数を減じた値がＣＰＵの演算処理のワード幅の倍数であれば、中間項の加減算のためのシフト処理は不要になる。
【００６５】
ここで、シフト処理の低減について、より一般化して検討する。
前述の式（１）で表されるｎ次多項式ｆ（ｘ）に対する、式（６）で表されるｍ次既約３項式ｐ（ｘ）によるリダクション演算は、前述の処理であり、プログラムで表せば図７に示す処理となる。この処理を実際に行うには、ワード幅のビット数に等しい個数の係数を同時に処理するため、ｆｏｒループ内の１行目と２行目の処理で、ワード幅内のシフト処理が必要になる。
【００６６】
この処理において、各ｃｉの処理において、中間項ａｘｋに対応する処理ではａ＊ｃｉをｉからｍ−ｋだけ移動した位置の係数ｃi-(m-k)に加算し、定数項ｂに対する処理ではｂ＊ｃｉをｉからｍだけ移動した位置の係数ｃi-mに加算している。
【００６７】
従って、加算先の２つの係数ｃi-(m-k)およびｃi-mの位置の差はｋであるので、ｋ（中間項の次数）がワード幅で割り切れる場合には、第１実施例で述べたとおり中間項と定数項に対応するシフトデータが共通化できる。すなわち、どちらか一方に対応するシフトデータのみを作成すればよい。
【００６８】
これに対して、中間項ａｘｋに対応する処理において、ｃiおよびｃi-(m-k)の位置の差がｍ−ｋであることから、ｍ−ｋ、すなわち既約３項式の次数から中間項の次数を引いた値がワード幅で割り切れる場合は、中間項に対応する処理において、係数が格納されている配列のデータをそのまま用いることができるためシフトデータの作成は不要であり、定数項に対応したシフトデータのみを作成すればよい。
【００６９】
また、定数項ｂに対応する処理では、ｂ＊ｃiをｉからｍだけ移動した位置の係数に加算することから、既約３項式の次数ｍがワード幅のビット数で割り切れる場合は、定数項に対応する処理において、係数が格納されている配列のデータをそのまま使用できるためシフトデータの作成は不要であり、中間項に対応したシフトデータのみを作成すればよい。
【００７０】
上記のいずれの場合においても、第１実施例の中間項の次数がワード幅で割り切れる場合と比較して、作成するシフトデータの量およびリダクション処理全体の計算量は変わらないため、同等の計算量削減効果が得られることになる。
【００７１】
第２実施例として、既約３項式の次数から中間項の次数を減じた値がワード幅の倍数である例を、図８を参照して説明する。
第２実施例では、対象多項式ｆ（ｘ）の次数ｎが１８９で、既約３項式ｐ（ｘ）のパラメータｍ、ｋ、ａ、ｂがそれぞれ９７、８１、２、１である場合、すなわちｐ（ｘ）が次の式で表される場合の例である。
【００７２】
p(x)＝x97+2x81+1
図示のように、ｆ（ｘ）の次数ｎが１８９であるから、第１実施例と同様にＨ（０）からＨ（１２）までの１３配列単位が確保され、リダクション演算ではｐ（ｘ）の次数９７より小さい次数９６にすればよいので、ｆ（ｘ）の０ビットから９６ビットまでの９７ビット分がリダクション結果の範囲であり、９７ビットから１８９ビットまでの９３ビット分がリダクション対象部分である。
【００７３】
ｐ（ｘ）の次数９７と中間項の次数８１の差は１６であるから、係数が格納されている配列のデータをそのまま用いることができ、１ワード（１６ビット）分シフトして−２倍した上で、配列のデータに加算すればよい。
定数項については、第１実施例と同様に、ｆ（ｘ）のリダクション対象部分の最終ビット、すなわちｐ（ｘ）の次数に対応するビットが、定数項に対応するように、すなわちワード幅の最終ビットに対応するようにシフトした上で、−１倍して配列のデータに加算すればよい。加算処理は、第１実施例と同じなので、説明は省略する。
【００７４】
次に、既約３項式を探索する処理について説明する。
図９は、既約３項式を探索する処理を示すフロー図である。ここでは、式（６）で示す前述の既約３項式で、ｋがワード幅の倍数であるものを探索するとする。ｍの値は応用分野に依存するが、ペアリングでは５００以下であれば十分である。また、３項式がひとつ与えられた時、その既約性の判定は、有限体を対象にする数式処理システム（例えばＲｉｓａ／Ａｓｉｒ）を用いれば十分に高速に実行できる。従って、既約３項式を探索するには図７に示すフローに従って行うことができる。
【００７５】
ステップ２０１では、ｍの最大値ｍａｘを入力し、ステップ２０２でｍを１に設定し、ステップ２０３でｍがｍａｘより大きいかを判定し、大きければ終了し、大きくなければステップ２０４に進む。
【００７６】
ステップ２０４ではｋを１に設定し、ステップ２０５でｋがｍと等しいかを判定し、等しければステップ２１０に進んでｍを１だけ増加させてステップ２０３に戻り、等しくなければ（小さければ）ステップ２０６に進む。
【００７７】
ステップ２０６では、その時点のｍとｋで、ａが１、ｂが２である３項式について既約であるか判定して既約であればリストアップし、既約でなければステップ２０７でａが２、ｂが１である３項式について既約であるか判定して既約であればリストアップし、既約でなければステップ２０８でａが２、ｂが２である３項式について既約であるか判定して既約であればリストアップし、既約でなければステップ２０９でｋを１増加させた後ステップ２０５に戻る。
【００７８】
以下、ｋ及びｍを順次増加させて処理を繰り返して既約３項式のリストを作成する。
【００７９】
図１０は、ｍが２５６以下で、ｋが８の倍数である全ての既約３項式をリストアップしたものである。例えば、ｘ１２８＋ｘ８０＋２のような既約３項式の次数および中間項の次数が共に８（または１６）の倍数である既約３項式を使用すれば、ワード幅内でのシフト処理は不要である。
【００８０】
図１０のような既約多項式のリストがある場合に、応用に適した既約多項式を選ぶには、以下のような手順が考えられる。
【００８１】
（１）応用によりｍが決まっており、ｍがｍａｘ以下の場合
この場合、リストで所望のｍの既約多項式が存在するか確認し、存在しなければ既約多項式は選択できない。所望のｍの既約多項式が存在すれば、その中に使用予定のＣＰＵのワード幅（ビット）の倍数であるｋを有するものがあるか確認し、あればそれを選択し、なければワード幅の異なるＣＰＵに交換可能か確認し、交換不能であれば既約３項式は選択できないことになる。ＣＰＵが交換可能であれば、新たに使用予定のＣＰＵのワード幅を変えて同じ処理を行う。
【００８２】
（２）応用によりｍが決まっており、ｍがｍａｘより大きい場合
第１の方法は、図９に示したフローでｍａｘ＝ｍとしてリストを再作成して、（１）の処理を行う。
【００８３】
第２の方法は、図９のフローでｍをｍａｘに固定して、ステップ２０４から２０９を繰り返す処理を行い、ｍ＝ｍａｘである既約多項式をリストアップする。そして、そのリスト中に使用予定のＣＰＵのワード幅（ビット）の倍数であるｋを有するものがあるか確認し、あればそれを選択し、なければワード幅の異なるＣＰＵに交換可能か確認し、交換不能であれば既約３項式は選択できないことになる。ＣＰＵが交換可能であれば、新たに使用予定のＣＰＵのワード幅を変えて同じ処理を行う。
【００８４】
（３）応用でｍが決まっていない場合
ｍが任意に選択できるので、リスト中に使用予定のＣＰＵのワード幅（ビット）の倍数であるｋを有するものがあるか確認し、あればその中から任意の（または追加条件を満たす）ものを選択し、なければワード幅の異なるＣＰＵに交換可能か確認し、交換不能であれば既約３項式は選択できないことになる。ＣＰＵが交換可能であれば、新たに使用予定のＣＰＵのワード幅を変えて同じ処理を行う。
【００８５】
（４）リストを作成せずに見つかった既約３項式を用いる場合（ｍが決まっている）
図９のフローでｍを設定し、更にｋをＣＰＵのワード幅に設定して、ステップ２０５から２０９を行い、所望の既約３項式が見つかったら終了する。なお、既約３項式がなく、ＣＰＵのワード幅が変更可能な時には、ワード幅を変更して同じ処理を行う。
【００８６】
（５）リストを作成せずに見つかった既約３項式を用いる場合（ｍが決まっていない）
ｍを変えて、（４）の処理を行う。
【００８７】
以上説明した実施例では、標数が３の有限体で、既約多項式は３項式である例を説明したが、中間項がＣＰＵのワード幅の倍数であるという本発明の特徴は、標数２などの標数３以外の有限体にも適用可能である。その場合、リダクション対象の多項式の係数は１ビットで表現できる（０又は１）ため、配列にはこの１ビット列を格納すればよい。
【００８８】
また、ｍの値によっては既約３項式が存在しない可能性がある。そのような場合には、既約４項式、既約５項式などに拡張して、本発明を適用することが可能である。
４項以上のｎ項既約多項式を用いる場合には、中間項の数はｎ−２個であるため、各中間項の少なくとも１つの項の次数についてワード幅の倍数であるか、または既約多項式の次数から中間項の次数を引いた値がワード幅の倍数であるか、または中間項の次数の差がワード幅の倍数である既約ｎ項式に拡張して、本発明を適用することが可能である。
【００８９】
本発明は、多項式のリダクションが用いられる場合に全て適用できるが、特に挙げれば以下のような分野に応用が可能である。
【００９０】
本発明が適用可能な代表的な例は、楕円曲線上でのペアリングの計算である。ペアリングは、楕円曲線暗号についての種々の応用に用いられるが、その一例としてＩＤベース暗号が挙げられる。ＩＤベース暗号の例として、通信者のＩＤ情報（ｅメールアドレス、電話番号など通信相手に固有の公開情報）を基に共通鍵を作成・配布する方法があり、ＩＤは任意の値が使用できる。この方法にペアリングを用いることが、非特許文献２に記載されており、ペアリング以外の方法によるＩＤベース暗号に比べて安全性が向上されることが記載されている。非特許文献１に記載されるように、ペアリングの計算にはＧＦ（３m）の乗算を計算する必要があり、ＧＦ（３m）の乗算では既約多項式による剰余演算が必要であり、本発明はこの剰余演算を効率化することができる。
【００９１】
最後に、本発明の効果を説明するため、Ｃ言語のソフトウエア実装で、ｍ＝９７，１６７，１９３，２３９の場合について、最小のｋを選択する従来例の実行時間に対する、本発明に従ってｋを選択した場合の実行時間の比を図１１に示す。図１１で、ｍ＝９７の時にはワード幅は１６ビットで、それ以外が３２ビットである。いずれの場合も、本発明により実行時間が６０％乃至７０％に低減されることが分かる。
以上説明した実施例を含む実施形態に関し、更に以下の付記を開示する。
（付記１）ＣＰＵを使用してソフトウエア制御により有限体の剰余演算を行う有限体演算方法であって、
既約多項式によるリダクション演算を行う時に、既約多項式の次数、中間項の次数および既約多項式の次数から中間項の次数を減じた値の少なくとも１つが、前記ＣＰＵの演算処理のワード幅の倍数である既約多項式を使用することを特徴とする有限体演算方法。（１）（図２、図５）
（付記２）リダクション演算の対象である有限体上の対象多項式の各項の係数を表すビットデータのそれぞれを、連続したビットデータとして記憶し、前記ＣＰＵの演算処理のワード幅に対応するビット数のデータを並列に処理する付記１に記載の有限体演算方法。（２）(図３）
（付記３）前記有限体は標数が３の有限体で、前記既約多項式の項数は３項以上であり、
リダクション演算の対象である有限体上の対象多項式の各項の係数を２ビットのデータで表し、各項の上位ビットと下位ビットをそれぞれ連続したビットデータとして記憶する付記２に記載の有限体演算方法。（３）(図３）
（付記４）前記既約多項式は３項式であり、中間項の次数が前記ＣＰＵの演算処理のワード幅の倍数であり、
リダクション演算の対象である有限体上の対象多項式の各項の係数を表すビットデータのそれぞれを、連続したビットデータとして記憶し、前記ＣＰＵの演算処理のワード幅に対応するビット数のデータを並列に処理し、前記対象多項式の前記既約多項式の次数以上のリダクション対象部分を、上位ビットから順に前記ワード幅単位で、前記既約多項式の次数に対応する項を前記ワード幅内の最小ビットに対応するようにシフトさせるシフト量だけシフトし、シフトしたワード幅単位のデータを、次数が前記既約多項式の第１項と中間項及び定数項との関係にある前記対象多項式の対応する項に加減算する付記１に記載の有限体演算方法。（４）(図５）
（付記５）前記既約多項式は３項式であり、前記既約多項式の次数から中間項の次数を減じた値が前記ＣＰＵの演算処理のワード幅の倍数であることを特徴とする付記１に記載の有限体演算方法。(図８）
（付記６）前記既約多項式は３項式であり、前記既約多項式の次数が前記ＣＰＵの演算処理のワード幅の倍数であることを特徴とする付記１に記載の有限体演算方法。
（付記７）前記既約多項式は４項以上の式であり、前記既約多項式の少なくとも２つの中間項の次数の差が前記ＣＰＵの演算処理のワード幅の倍数であることを特徴とする付記１に記載の有限体演算方法。(図８）
（付記８）ＣＰＵを備え、ソフトウエア制御により有限体の剰余演算を行う有限体演算装置であって、
既約多項式の次数、中間項の次数および既約多項式の次数から中間項の次数を減じた値の少なくとも１つが、前記ＣＰＵの演算処理のワード幅の倍数である既約多項式を使用してリダクション演算を行うリダクション演算手段を備えることを特徴とする有限体演算装置。（５）（図１、図２、図５）
（付記９）前記リダクション演算手段は、リダクション演算の対象である有限体上の対象多項式の各項の係数を表すビットデータのそれぞれを、連続したビットデータとして記憶する係数記憶手段を備え、前記ＣＰＵの演算処理のワード幅に対応するビット数のデータを並列に処理する付記８に記載の有限体演算装置。（６）(図３）
（付記１０）前記有限体は標数が３の有限体で、前記既約多項式の項数は３項以上であり、
前記リダクション演算手段は、リダクション演算の対象である有限体上の対象多項式の各項の係数を２ビットのデータで表し、各項の上位ビットと下位ビットをそれぞれ連続したビットデータとして記憶する係数記憶手段を備える付記８に記載の有限体演算装置。(図３）
（付記１１）前記既約多項式は３項式であり、中間項の次数が前記ＣＰＵの演算処理のワード幅の倍数であり、
前記リダクション演算手段は、
リダクション演算の対象である有限体上の対象多項式の各項の係数を表すビットデータのそれぞれを、連続したビットデータとして記憶する係数記憶手段を備え、
前記ＣＰＵの演算処理のワード幅に対応するビット数のデータを並列に処理し、
前記対象多項式の前記既約多項式の次数以上のリダクション対象部分を、上位ビットから順に前記ワード幅単位で、前記既約多項式の次数に対応する項を前記ワード幅内の最小ビットに対応するようにシフトさせるシフト量だけシフトし、シフトしたワード幅単位のデータを、次数が前記既約多項式の第１項と中間項及び定数項との関係にある前記対象多項式の対応する項に加減算する付記８に記載の有限体演算装置。(図５）
【産業上の利用可能性】
【００９２】
本発明は、有限体（ガロア体）演算で、多項式のリダクションが用いられる場合には、どのような場合にも適用可能である。
【図面の簡単な説明】
【００９３】
【図１】実施例で使用するハードウエアの構成を示す図である。
【図２】第１実施例のリダクション演算フローである。
【図３】第１実施例における係数データの格納方法を示す図である。
【図４】第１実施例における演算処理の説明図である。
【図５】第１実施例におけるシフト処理を説明する図である。
【図６】比較のための従来例におけるシフト処理を説明する図である。
【図７】リダクション演算におけるシフト処理を説明するためのプログラムを示す図である。
【図８】第２実施例におけるシフト処理を説明する図である。
【図９】既約３項式の探索フローである。
【図１０】ｍが２５６以下で、ｋが８の倍数の既約３項式のリストである。
【図１１】本発明と従来例の実行時間の比較結果を示す図である。
【符号の説明】
【００９４】
２１    ＣＰＵ
２２    ＡＬＵ
２４    内部バス
２５    ＲＯＭ
２６    ＲＡＭ
２８    外部バス
【図１】
2008197625.tif 000003
【図２】
2008197625.tif 000004
【図３】
2008197625.tif 000005
【図４】
2008197625.tif 000006
【図５】
2008197625.tif 000007
【図６】
2008197625.tif 000008
【図７】
2008197625.tif 000009
【図８】
2008197625.tif 000010
【図９】
2008197625.tif 000011
【図１０】
2008197625.tif 000012
【図１１】
2008197625.tif 000013