(57)【特許請求の範囲】
【請求項１】
素体ＧＦ（ｐ）をｍ次多項式Ｆ（ｘ）及びｌ次多項式Ｇ（ｘ）により順次拡大して構成された有限体である合成数次拡大体ＧＦ（ｐml）に関し、この合成数次拡大体ＧＦ（ｐml）上の値Ｐ及びべき指数ｋに基づき、べき乗計算を実行して得られた計算結果Ｐkを出力する機能を有し且つ記憶手段を備えた べき乗計算装置であって、
前記値Ｐと、ｔビットの前記べき指数ｋ＝（ｋt-1，ｋt-2，…，ｋi，…，ｋ1，ｋ0）（但し、ｉはｔ−１から０までの整数）とを入力するための入力手段と、
前記入力された値Ｐ及びべき指数ｋを前記記憶手段に書き込む手段と、
前記記憶手段内の値Ｐを途中の計算結果Ｑに代入し、当該計算結果Ｑを当該記憶手段に書き込む手段と、
前記記憶手段内のべき指数ｋにおける処理対象の桁ｉを最上位桁ｔ−１に初期化し、当該処理対象の桁ｉを前記記憶手段に書き込む手段と、
前記ｍ次多項式Ｆ（ｘ）のゼロ以外の項よりもゼロ以外の項が少ない多項式Ｆ’（ｘ）に基づく、Ｑ＝Ｑ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算命令と、前記記憶手段内の途中の計算結果Ｑとを送出する第１計算命令送出手段と、
前記第１計算命令送出手段から受けた計算命令と、途中の計算結果Ｑとに基づいて、Ｑ＝Ｑ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑを送出する第１計算実行手段と、
前記第１計算実行手段から受けた計算結果Ｑにより前記記憶手段内の計算結果Ｑを更新する手段と、
前記記憶手段内の処理対象のｉ桁目の値ｋiが１であるか否かを判定する第１判定手段と、
前記第１判定手段による判定の結果、ｉ桁目の値ｋiが１である場合、Ｑ＝Ｐ×Ｑ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算命令と、前記記憶手段内の途中の計算結果Ｑと、前記記憶手段内の値Ｐとを送出する第２計算命令送出手段と、
前記第２計算命令送出手段から受けた計算命令と、途中の計算結果Ｑと、値Ｐとに基づいて、Ｑ＝Ｐ×Ｑ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑを送出する第２計算実行手段と、
前記第２計算実行手段から受けた計算結果Ｑにより前記記憶手段内の計算結果Ｑを更新する手段と、
前記第１判定手段による判定結果が否の場合、又は前記第２計算実行手段による計算結果Ｑを更新した場合、前記記憶手段内の処理対象の桁ｉが０であるか否かを判定する第２判定手段と、
前記第２判定手段による判定結果が否の場合、前記記憶手段内の処理対象の桁ｉを−１だけ更新し、前記第１計算命令送出手段を再度実行する手段と、
前記第２判定手段による判定の結果、処理対象の桁ｉが０である場合、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算命令と、前記記憶手段内の途中の計算結果Ｑとを送出する第３計算命令送出手段と、
前記第３計算命令送出手段から受けた計算命令と、途中の計算結果Ｑと、値Ｐとに基づいて、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑを送出する第３計算実行手段と、
前記第３計算実行手段による計算結果Ｑにより前記記憶手段内の計算結果Ｑを更新し、更新後の計算結果Ｑを前記べき乗計算の計算結果Ｐkとして出力する手段と、
を備えたことを特徴とする べき乗計算装置。
【請求項２】
請求項１に記載のべき乗計算装置において、
前記ｍ次多項式Ｆ（ｘ）は、ｍ＋１個の項を有し、当該各項の全ての係数が１であるｍ次多項式Ｆ（ｘ）＝ｘm＋ｘm-1＋…＋ｘ＋１であり、
前記多項式Ｆ’（ｘ）は、前記ｍ次多項式Ｆ（ｘ）に（ｘ−１）を乗じて得られる多項式Ｆ’（ｘ）＝ｘm+1−１であることを特徴とする べき乗計算装置。
【請求項３】
素体ＧＦ（ｐ）をｍ次多項式Ｆ（ｘ）及びｌ次多項式Ｇ（ｘ）により順次拡大して構成された有限体である合成数次拡大体ＧＦ（ｐml）に関し、この合成数次拡大体ＧＦ（ｐml）上の値Ｐ及びべき指数ｋに基づき、べき乗計算を実行して得られた計算結果Ｐkを出力する機能を有し且つ記憶手段を備えた べき乗計算装置に用いられるプログラムであって、
前記べき乗計算装置を、
前記値Ｐと、ｔビットの前記べき指数ｋ＝（ｋt-1，ｋt-2，…，ｋi，…，ｋ1，ｋ0）（但し、ｉはｔ−１から０までの整数）とを入力する入力手段、
前記入力された値Ｐ及びべき指数ｋを前記記憶手段に書き込む手段、
前記記憶手段内の値Ｐを途中の計算結果Ｑに代入し、当該計算結果Ｑを当該記憶手段に書き込む手段、
前記記憶手段内のべき指数ｋにおける処理対象の桁ｉを最上位桁ｔ−１に初期化し、当該処理対象の桁ｉを前記記憶手段に書き込む手段、
前記ｍ次多項式Ｆ（ｘ）のゼロ以外の項よりもゼロ以外の項が少ない多項式Ｆ’（ｘ）に基づく、Ｑ＝Ｑ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算命令と、前記記憶手段内の途中の計算結果Ｑとを送出する第１計算命令送出手段、
前記第１計算命令送出手段から受けた計算命令と、途中の計算結果Ｑとに基づいて、Ｑ＝Ｑ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑを送出する第１計算実行手段、
前記第１計算実行手段から受けた計算結果Ｑにより前記記憶手段内の計算結果Ｑを更新する手段、
前記記憶手段内の処理対象のｉ桁目の値ｋiが１であるか否かを判定する第１判定手段、
前記第１判定手段による判定の結果、ｉ桁目の値ｋiが１である場合、Ｑ＝Ｐ×Ｑ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算命令と、前記記憶手段内の途中の計算結果Ｑと、前記記憶手段内の値Ｐとを送出する第２計算命令送出手段、
前記第２計算命令送出手段から受けた計算命令と、途中の計算結果Ｑと、値Ｐとに基づいて、Ｑ＝Ｐ×Ｑ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑを送出する第２計算実行手段、
前記第２計算実行手段から受けた計算結果Ｑにより前記記憶手段内の計算結果Ｑを更新する手段、
前記第１判定手段による判定結果が否の場合、又は前記第２計算実行手段による計算結果Ｑを更新した場合、前記記憶手段内の処理対象の桁ｉが０であるか否かを判定する第２判定手段、
前記第２判定手段による判定結果が否の場合、前記記憶手段内の処理対象の桁ｉを−１だけ更新し、前記第１計算命令送出手段を再度実行する手段、
前記第２判定手段による判定の結果、処理対象の桁ｉが０である場合、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算命令と、前記記憶手段内の途中の計算結果Ｑとを送出する第３計算命令送出手段、
前記第３計算命令送出手段から受けた計算命令と、途中の計算結果Ｑと、値Ｐとに基づいて、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑを送出する第３計算実行手段、
前記第３計算実行手段による計算結果Ｑにより前記記憶手段内の計算結果Ｑを更新し、更新後の計算結果Ｑを前記べき乗計算の計算結果Ｐkとして出力する手段、
として機能させるためのプログラム。
【請求項４】
請求項３に記載のプログラムにおいて、
前記ｍ次多項式Ｆ（ｘ）は、ｍ＋１個の項を有し、当該各項の全ての係数が１であるｍ次多項式Ｆ（ｘ）＝ｘm＋ｘm-1＋…＋ｘ＋１であり、
前記多項式Ｆ’（ｘ）は、前記ｍ次多項式Ｆ（ｘ）に（ｘ−１）を乗じて得られる多項式Ｆ’（ｘ）＝ｘm+1−１であることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、合成数次拡大体におけるべき乗演算を高速に実行し得る べき乗計算装置及びプログラムに関する。
【背景技術】
【０００２】
近年、インターネットなどのオープンなネットワークを介し、文書データや画像データなどのさまざまなデータを送受信したい要望がある。これら送受信したいデータには秘密にしたいデータが多く含まれている。そのため、第三者には分からないようにデータを暗号化した状態で送受信するための暗号化技術が普及している。
【０００３】
この主の暗号化技術の一つとして、有限体上の演算を用いる方法がある。暗号化技術は、一般に暗号や署名を有限体ＧＦ（ｐm）上で定義される演算を用いて実現する。このとき、位数ｐmには素数または素数のべき乗が選択されるが、本明細書では素数ｐのべき乗の場合、特に合成数lm次のべき乗について考える。このような有限体ＧＦ（ｐlm）を本明細書では合成数次拡大体と呼ぶこととする。
【０００４】
このような合成数次拡大体における演算の高速化手法は幾つか提案されている。例えばペアリングと呼ばれる計算を行う場合、合成数次拡大体にて演算を行う。また、ペアリングの高速化手法において、特に言及されないものの、合成数次拡大体を高速化している手法も知られている（例えば、非特許文献１，２を参照。）。
【０００５】
また、一般的な合成数次拡大体について、２次の多項式を用いて逐次拡大して演算を高速化する手法が提案されている（例えば、特許文献１を参照。）。
【０００６】
ここで、これら高速化手法について考察する。  
合成数次拡大体としては、素体ＧＦ（ｐ）を、ｍ次多項式Ｆ（ｘ）を用いて拡大して有限体ＧＦ（ｐm）を構成し、この有限体ＧＦ（ｐm）を、ｌ次多項式Ｇ（ｘ）を用いて更に拡大して有限体ＧＦ（ｐml）を構成している場合を前提とする。
【０００７】
このとき、非特許文献１，２及び特許文献１に記載の高速化手法は、いずれもＧ（ｘ）の演算を高速化する方式である。例えば、非特許文献２記載のアルゴリズム３（Algorithm3）において、今日一般的に求められるセキュリティを満たすためには、ｍ＝１６３を選択する場合が想定される。また、ｍ＝１６３の場合、Ｇ（ｘ）の次数ｌが４となる。なお、このように、Ｆ（ｘ）の次数ｍはＧ（ｘ）の次数ｌよりも大きい場合が多い。非特許文献２では、このような次数の下でＧ（ｘ）の演算の高速化が検討されている。
【０００８】
しかしながら、合成数次拡大体の高速化手法としては、このように小さい次数ｌをもつＧ（ｘ）の演算の高速化に加え、大きい次数ｍをもつＦ（ｘ）の演算を高速化することが必要である。
【０００９】
本明細書では説明を簡単にするため、べき乗演算、特にバイナリ（Binary）法と呼ばれる一般的なべき乗演算を用いて効果を考察する。有限体はＧＦ（ｑ）とし、ｑ＝ｐlmとする。ここで、ｐは素数、ｌ及びｍは整数であり、ｍは多項式Ｆ（ｘ）の次数、ｌは多項式Ｇ（ｘ）の次数であるとする。合成数次拡大体の演算においては、ＧＦ（ｐ）の演算及びＦ（ｘ）を用いてＧＦ（ｐm）上の演算を定義し、更にＧＦ（ｐm）上の演算及びＧ（ｘ）を用いてＧＦ（ｐlm）上の演算を定義しているとする。
【００１０】
このとき、従来のバイナリ法は、図６の左欄に示すように実行される。  
始めに、べき乗演算Ｐkを行うため、合成数次拡大体上の値Ｐ（∈ＧＦ（ｑ）＝ＧＦ（ｐlm））と、べき指数ｋ（＝（ｋt-1，ｋt-2，…，ｋi，…，ｋ1，ｋ0）2）とが入力される。なお、べき指数ｋを表す式ｋ＝（ｋt-1，ｋt-2，…，ｋi，…，ｋ1，ｋ0）2は、べき指数ｋの２進数表記を意味している。ここで、ｋiは、べき指数ｋのｉ桁目の値を表す。ｉは、べき指数ｋの桁を表し、ｔ−１から０までの整数が用いられる。
【００１１】
続いて、途中の計算結果Ｑにべき乗対象のデータＰを代入する（step 1）。さらに、Ｆｏｒ文により、最上位桁ｔ−１から最下位桁０まで桁ｉを減らしながら以下の処理を実行する（step 2）。途中の計算結果ＱをＱ2 ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算結果により更新する（step 3）。次に、べき指数ｋのｉ桁目の値ｋiが１のときには、途中の計算結果ＱをＱ×Ｐ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算結果により更新する（step 4）。計算結果Ｑを出力して演算を終了する（step 5）。
【００１２】
以上の処理のうち、step 3, 4の処理では、多項式Ｆ（ｘ）Ｇ（ｘ）による剰余演算を行う必要がある。剰余演算は、何もテクニックを使わない場合には多項式Ｆ（ｘ），Ｇ（ｘ）の形に依存して複雑になる。具体的には剰余演算は、各々の多項式Ｆ（ｘ），Ｇ（ｘ）における各次数の０以外の係数と、２番目に大きな次数の大きさとに依存して複雑になる。ここで、剰余演算の複雑さを検討するため、単項式Ａ（ｘ）＝ｘ6に対し、次の３つの多項式ｆ1（ｘ）〜ｆ3（ｘ）で剰余演算を行う場合を考える。
【００１３】
ｆ1（ｘ）＝ｘ4＋ａ3ｘ3＋ａ2ｘ2＋ａ1ｘ1＋ａ0 
ｆ2（ｘ）＝ｘ4＋ａ3ｘ3＋ａ0 
ｆ3（ｘ）＝ｘ4＋ａ0 
このような剰余演算は、ｘの４乗以上の項に対し、再帰的にｆ1（ｘ）、ｆ2（ｘ）及びｆ3（ｘ）を用いてそれぞれ実行される。
【数１】
0004724200.tif 000002
【００１４】
このような剰余演算によると、次の事項（ｉ）〜（ｉｉ）が分かる。  
（ｉ）２番目の次数が３次のｆ1（ｘ）及びｆ2（ｘ）は、剰余演算を３回実行するのに対し、２番目の次数が０次のｆ3（ｘ）は剰余演算を１回実行するだけで済む。
【００１５】
（ｉｉ）多項式の全ての項が存在するｆ1（ｘ）と、３次の項と０次の項のみ存在するｆ2（ｘ）との剰余演算結果を比較した結果、同じ回数だけ剰余演算を実行するにも関わらず、ｆ1（ｘ）による剰余演算結果の方が複雑な多項式になっている。
【００１６】
これらの事項から次の性質（Ｉ）〜（ＩＩ）が分かる。
【００１７】
（Ｉ）剰余演算において、法となる多項式は、２番目に高い次数が低い方が良い。
【００１８】
（ＩＩ）剰余演算において、法となる多項式は、ゼロ以外の項が少ない方が良い。
【００１９】
しかし、従来の剰余演算においては、これらの性質（Ｉ）〜（ＩＩ）を満たす多項式Ｆ（ｘ）を選択したに過ぎず、Ｆ（ｘ）による剰余演算自体を高速化してはいない。
【非特許文献１】Masaaki Shirase, Tsuyoshi Takagi, Eiji Okamoto, ”Some Efficient Algorithms for the Final Exponentiation of ηT Pairing”, Cryptology ePrint Archive: Report 2006/431，2006, http://eprint.iacr.org/2006/431
【非特許文献２】Paulo S.L.M.Barreto, Steven Galbraith, Colm O hEigeartaigh, Michael Scott, ”Efficient Pairing Computation on Supersingular Abelian Varieties”, ePrint. Archive, Report 2004/375, 2004. http://eprint.iacr.org/2004/375
【特許文献１】特開２００１−５１５９８号公報
【発明の開示】
【発明が解決しようとする課題】
【００２０】
以上説明したように、従来の合成数次拡大体の高速化手法では、有限体を２番目に拡大する際に用いるｌ次多項式Ｇ（ｘ）の演算を高速化している。
【００２１】
しかしながら、ｍ次多項式Ｆ（ｘ）及びｌ次多項式Ｇ（ｘ）における各次数ｍ，ｌの関係は、ｍ＞ｌである場合が多いので、低い次数ｌの多項式Ｇ（ｘ）の演算を高速化しても、全体の演算が高速化されない不都合がある。
【００２２】
従って、合成数次拡大体の高速化手法においては、有限体を最初に拡大する際に用いる高い次数ｍの多項式Ｆ（ｘ）の演算を高速化できることが望まれる。
【００２３】
また、より一般的に、有限体を複数回（２回以上）拡大して構成される合成数次拡大体の場合にも、最初の方で拡大する際に用いる多項式の演算を高速化する手法が望まれる。
【００２４】
本発明は上記実情を考慮してなされたもので、各多項式により有限体を拡大してなる合成数次拡大体上でべき乗計算を行う際に、最初に拡大に用いた多項式による剰余演算を高速に実行し得る べき乗計算装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２５】
本発明の一つの局面は、素体ＧＦ（ｐ）をｍ次多項式Ｆ（ｘ）及びｌ次多項式Ｇ（ｘ）により順次拡大して構成された有限体である合成数次拡大体ＧＦ（ｐml）に関し、この合成数次拡大体ＧＦ（ｐml）上の値Ｐ及びべき指数ｋに基づき、べき乗計算を実行して得られた計算結果Ｐkを出力する機能を有し且つ記憶手段を備えた べき乗計算装置であって、前記値Ｐと、ｔビットの前記べき指数ｋ＝（ｋt-1，ｋt-2，…，ｋi，…，ｋ1，ｋ0）（但し、ｉはｔ−１から０までの整数）とを入力するための入力手段と、前記入力された値Ｐ及びべき指数ｋを前記記憶手段に書き込む手段と、前記記憶手段内の値Ｐを途中の計算結果Ｑに代入し、当該計算結果Ｑを当該記憶手段に書き込む手段と、前記記憶手段内のべき指数ｋにおける処理対象の桁ｉを最上位桁ｔ−１に初期化し、当該処理対象の桁ｉを前記記憶手段に書き込む手段と、前記ｍ次多項式Ｆ（ｘ）のゼロ以外の項よりもゼロ以外の項が少ない多項式Ｆ’（ｘ）に基づく、Ｑ＝Ｑ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算命令と、前記記憶手段内の途中の計算結果Ｑとを送出する第１計算命令送出手段と、前記第１計算命令送出手段から受けた計算命令と、途中の計算結果Ｑとに基づいて、Ｑ＝Ｑ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑを送出する第１計算実行手段と、前記第１計算実行手段から受けた計算結果Ｑにより前記記憶手段内の計算結果Ｑを更新する手段と、前記記憶手段内の処理対象のｉ桁目の値ｋiが１であるか否かを判定する第１判定手段と、前記第１判定手段による判定の結果、ｉ桁目の値ｋiが１である場合、Ｑ＝Ｐ×Ｑ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算命令と、前記記憶手段内の途中の計算結果Ｑと、前記記憶手段内の値Ｐとを送出する第２計算命令送出手段と、前記第２計算命令送出手段から受けた計算命令と、途中の計算結果Ｑと、値Ｐとに基づいて、Ｑ＝Ｐ×Ｑ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑを送出する第２計算実行手段と、前記第２計算実行手段から受けた計算結果Ｑにより前記記憶手段内の計算結果Ｑを更新する手段と、前記第１判定手段による判定結果が否の場合、又は前記第２計算実行手段による計算結果Ｑを更新した場合、前記記憶手段内の処理対象の桁ｉが０であるか否かを判定する第２判定手段と、前記第２判定手段による判定結果が否の場合、前記記憶手段内の処理対象の桁ｉを−１だけ更新し、前記第１計算命令送出手段を再度実行する手段と、前記第２判定手段による判定の結果、処理対象の桁ｉが０である場合、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算命令と、前記記憶手段内の途中の計算結果Ｑとを送出する第３計算命令送出手段と、前記第３計算命令送出手段から受けた計算命令と、途中の計算結果Ｑと、値Ｐとに基づいて、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑを送出する第３計算実行手段と、前記第３計算実行手段による計算結果Ｑにより前記記憶手段内の計算結果Ｑを更新し、更新後の計算結果Ｑを前記べき乗計算の計算結果Ｐkとして出力する手段とを備えた べき乗計算装置である。
【００２６】
なお、上記一つの局面は、装置として表現したが、装置に限らず、方法、プログラム、プログラムを記憶したコンピュータ読取り可能な記憶媒体、として表現してもよい。
【００２７】
（作用）
本発明の一つの局面によれば、素体ＧＦ（ｐ）をｍ次多項式Ｆ（ｘ）及びｌ次多項式Ｇ（ｘ）により順次拡大して構成された有限体である合成数次拡大体ＧＦ（ｐml）に関し、ｍ次多項式Ｆ（ｘ）のゼロ以外の項よりもゼロ以外の項が少ない多項式Ｆ’（ｘ）に基づく、Ｑ＝Ｑ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）及びＱ＝Ｐ×Ｑ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算を実行し、最後に、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算を実行する。
【００２８】
このように、本来のＦ（ｘ）よりも少ない項の多項式Ｆ’（ｘ）に基づき、途中の剰余演算を高速に実行し、最後に、本来のＦ（ｘ）に基づき、剰余演算を実行する構成により、各多項式により有限体を拡大してなる合成数次拡大体上でべき乗計算を行う際に、最初に拡大に用いた多項式による剰余演算を高速に実行することができる。
【発明の効果】
【００２９】
以上説明したように本発明によれば、各多項式により有限体を拡大してなる合成数次拡大体上でべき乗計算を行う際に、最初に拡大に用いた多項式による剰余演算を高速に実行できる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の各実施形態について図面を用いて説明するが、その前に各実施形態の概要を述べる。
【００３１】
（第１の実施形態の概要）
第１の実施形態では、合成数次拡大体において、ＡＯＰ（All One Polynomial）と呼ばれる多項式をＦ（ｘ）に用いることにより、剰余演算の高速化を図っている。
【００３２】
ＡＯＰは、次式に示すように、ｍ＋１個の項を有し、当該各項の全ての係数が１であるｍ次多項式である。
【００３３】
ｆ（ｘ）＝ｘm＋ｘm-1＋…＋ｘ＋１
この多項式ｆ（ｘ）に（ｘ−１）を乗じると、次に示す多項式ｘm+1−１が得られる。
【００３４】
（ｘ−１）ｆ（ｘ）＝ｘm+1−１
これにより、ｍ＋１次の項を式（ｘ−１）ｆ（ｘ）で剰余演算した場合、次式に示すように、ｍ＋１次の項が１に置換されることになる。
【００３５】
ｘm+1 ｍｏｄ （ｘ−１）ｆ（ｘ）＝１
従って、剰余演算を非常に高速に実行可能である。
【００３６】
例えば、バイナリ法のように途中計算が多く含まれる場合に、以下に示すように、剰余演算を高速に実行可能である。
【００３７】
素体ＧＦ（Ｐ）を、ｍ次多項式Ｆ（ｘ）を用いて拡大して有限体ＧＦ（Ｐm）を構成し、さらに有限体ＧＦ（Ｐm）を、ｌ次多項式Ｇ（ｘ）を用いてさらに拡大して有限体ＧＦ（Ｐml）を構成しているが、本実施形態においてＧＦ（Ｐm）上の演算はｍ次多項式Ｆ（ｘ）だけではなく、（ｘ−１）Ｆ（ｘ）を用いた演算も定義しているとする。
【００３８】
このとき、第１の実施形態のバイナリ法は図６の中央欄に示すように実行される。
【００３９】
始めに、前述した通り、合成数次拡大体上の値Ｐ（∈ＧＦ（ｑ）＝ＧＦ（ｐlm））と、べき指数ｋ（＝（ｋt-1，ｋt-2，…，ｋi，…，ｋ1，ｋ0）2）とが入力される。
【００４０】
また同様に、途中の計算結果Ｑにべき乗対象のデータＰを代入する（step 1）。さらに、Ｆｏｒ文により、最上位桁ｔ−１から最下位桁０まで桁ｉを減らしながら以下の処理を実行する（step 2）。途中の計算結果ＱをＱ2 ｍｏｄ （ｘ−１）Ｆ（ｘ）Ｇ（ｘ）の計算結果により更新する（step 3）。ここで、ＧＦ（ｐm）上の演算としては、（ｘ−１）Ｆ（ｘ）を用いて定義された演算を用いる。従って、step 3の処理の出力は（ｘ−１）Ｆ（ｘ）Ｇ（ｘ）を用いて定義された計算結果となる。
【００４１】
次に、べき指数ｋのｉ桁目の値ｋiが１のときには、途中の計算結果ＱをＱ×Ｐ ｍｏｄ （ｘ−１）Ｆ（ｘ）Ｇ（ｘ）の計算結果により更新する（step 4）。ここで、ＧＦ（ｐlm）上の演算としては、（ｘ−１）Ｆ（ｘ）を用いて定義された演算を用いる。従って、step 4の処理の出力も（ｘ−１）Ｆ（ｘ）Ｇ（ｘ）を用いて定義された計算結果となる。
【００４２】
Ｆｏｒ文による計算結果ＱをＱ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算結果により更新する（step 5）。ここでは、Ｆｏｒ文で計算された環の出力結果に対し、Ｆ（ｘ）を用いて定義された演算を用いて剰余演算を行い、計算結果を求めている。更新後の計算結果Ｑを出力して演算を終了する（step 6）。
【００４３】
ここで、実際の値を用い、第１の実施形態の効果の概要を述べる。
【００４４】
従来法及び第１の実施形態において、べき指数ｋを２００ビットとし（ｔ＝２００）、２００ビットのべき指数ｋのうち、１を示すビット（step４の処理を行う回数）が確率的に１００個あるとする。
【００４５】
従来法において、有限体ＧＦ（ｐm）上でＦ（ｘ）に基づく剰余演算（式の置き換え）の回数を３回と仮定する。なお、この仮定は［背景技術］で述べた事項（ｉ）に対応している。また、多項式Ｇ（ｘ）の次数ｌを４とし、多項式Ｆ（ｘ）Ｇ（ｘ）により２００次元の体を構成したとする（従って、Ｆ（ｘ）の次数ｍは５０となる。）。
【００４６】
一方、第１の実施形態も同様に次数ｍ，ｌを設定し、また、有限体ＧＦ（ｐm）上で（ｘ−１）Ｆ（ｘ）に基づく剰余演算の回数を１回とする。
【００４７】
また、従来法及び第１の実施形態において、多項式Ｇ（ｘ）に基づく剰余演算の回数をＴ回とする。なお、従来法及び第１の本実施形態において、回数Ｔは同一であるとする。
【００４８】
第１の実施形態において、step５のＦ（ｘ）Ｇ（ｘ）に基づく剰余演算は、（ｘ−１）の乗算によって１次元高くなった多項式（ｘ−１）Ｆ（ｘ）Ｇ（ｘ）に対し、１次元低い本来の多項式Ｆ（ｘ）Ｇ（ｘ）で剰余をとるので、剰余演算回数を１回とする。
【００４９】
以上のとき、従来法と第１の実施形態の剰余演算の回数は次のようになる。次式中、２００はstep 3のＱ2の実行回数であり、１００はstep 4のＱ×Ｐの実行回数である。
【００５０】
従来法…２００＊Ｔ＊３＋１００＊Ｔ＊３＝９００Ｔ回
本実施形態…２００＊Ｔ＊１＋１００＊Ｔ＊１＋１＝３００Ｔ＋１回
以上のように第１の実施形態によれば、ＡＯＰ（All One Polynomial）と呼ばれる多項式をＦ（ｘ）に用い、途中の剰余演算をｍｏｄ （ｘ−１）Ｆ（ｘ）により実行し、最後の剰余演算をｍｏｄ Ｆ（ｘ）により実行する構成により、ＧＦ（ｐm）上の剰余演算回数を大幅に削減可能であることが分かる。
【００５１】
また、第１の実施形態は、バイナリ法に適用した場合を例に挙げて説明したが、これに限らず、一般的なべき乗計算方法に適用しても、同様に剰余演算回数を大幅に削減でき、剰余演算を高速に実行することができる。
【００５２】
（第２の実施形態の概要）
第２の実施形態では、第１の実施形態をより一般的に構成したものであり、第１の実施形態のＡＯＰ（＝ｆ（ｘ）＝Ｆ（ｘ））及び（ｘ−１）Ｆ（ｘ）に代えて、より一般的な多項式Ｆ（ｘ）及びＦ’（ｘ）を用いている。換言すると、第２の実施形態の一つの具体例が第１の実施形態となっている。
【００５３】
第２の実施形態の多項式Ｆ（ｘ），Ｆ’（ｘ）としては、例えば、ある多項式ｆ（ｘ）に基づいてＦ’（ｘ）＝Ｆ（ｘ）ｆ（ｘ）と表したとき、多項式Ｆ’（ｘ）のゼロ以外の項が、Ｆ（ｘ）のゼロ以外の項よりも少ないという関係があればよい。なお、この関係に伴い、多項式Ｆ’（ｘ）に基づく剰余演算ｍｏｄ Ｆ’（ｘ）は、多項式Ｆ（ｘ）に基づく剰余演算ｍｏｄ Ｆ（ｘ）よりも高速に実行可能となっている。
【００５４】
また、第２の実施形態のバイナリ法は図６の右欄に示すように実行される。すなわち、第２の実施形態は、第１の実施形態の多項式Ｆ（ｘ）（＝ＡＯＰ）及び（ｘ−１）Ｆ（ｘ）に代えて、より一般的な多項式Ｆ（ｘ）及びＦ’（ｘ）を用いて実行される。
【００５５】
具体的には、値Ｐ及びべき指数ｋの入力からstep 1の処理までは前述同様に実行される。続いて、Ｆｏｒ文により、最上位桁ｔ−１から最下位桁０まで桁ｉを減らしながら以下の処理を実行する（step 2）。途中の計算結果ＱをＱ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算結果により更新する（step 3）。ここで、ＧＦ（ｐm）上の演算としては、Ｆ’（ｘ）を用いて定義された演算を用いる。従って、step 3の処理の出力はＦ’（ｘ）Ｇ（ｘ）を用いて定義された計算結果となる。
【００５６】
次に、べき指数ｋのｉ桁目の値ｋiが１のときには、途中の計算結果ＱをＱ×Ｐ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算結果により更新する（step 4）。ここで、ＧＦ（ｐlm）上の演算としては、Ｆ’（ｘ）を用いて定義された演算を用いる。従って、step 4の処理の出力もＦ’（ｘ）Ｇ（ｘ）を用いて定義された計算結果となる。
【００５７】
Ｆｏｒ文による計算結果ＱをＱ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算結果により更新する（step 5）。ここでは、Ｆｏｒ文で計算された環の出力結果に対し、Ｆ（ｘ）を用いて定義された演算を用いて剰余演算を行い、計算結果を求めている。更新後の計算結果Ｑを出力して演算を終了する（step 6）。
【００５８】
以上のように第２の実施形態によれば、より一般的な多項式Ｆ（ｘ）について、この多項式Ｆ（ｘ）よりも少ない項の多項式Ｆ’（ｘ）を用い、途中の剰余演算をｍｏｄ Ｆ’（ｘ）により実行し、最後の剰余演算をｍｏｄ Ｆ（ｘ）により実行する構成により、第１の実施形態と同様に、ＧＦ（ｐm）上の剰余演算回数を大幅に削減でき、剰余演算を高速に実行することができる。
【００５９】
また、第２の実施形態は、バイナリ法に適用した場合を例に挙げて説明したが、これに限らず、一般的なべき乗計算方法に適用しても、同様に剰余演算回数を大幅に削減でき、剰余演算を高速に実行することができる。
【００６０】
以上が各実施形態の概要である。次に、本発明の各実施形態を具体的に説明する。
【００６１】
（第１の実施形態の具体的な構成）
図１は本発明の第１の実施形態に係るべき乗計算装置の構成を示す模式図であり、図２は同装置が演算可能な有限体を示す模式図である。このべき乗計算装置１００は、入出力部１０、べき乗計算制御部２０、メモリ３０、ＧＦ（ｐlm）計算部４０、ＧＦ（ｐm）計算部５０及びＧＦ（ｐ）計算部６０を備えている。なお、各計算部４０〜６０は、図２に示す如き、各有限体ＧＦ（ｐlm），ＧＦ（ｐm），ＧＦ（ｐ）上の計算を担当している。
【００６２】
ここで、入出力部１０は、合成数次拡大体上の値Ｐ（∈ＧＦ（ｑ）＝ＧＦ（ｐlm））と、べき指数ｋ（＝（ｋt-1，ｋt-2，…，ｋ1，ｋ0）2）とが入力されると、値Ｐ及びべき指数ｋをべき乗計算制御部２０に送出する機能と、べき乗計算制御部２０から受けた計算結果Ｐkを出力する機能とをもっている。
【００６３】
べき乗計算制御部２０は、入出力部１０から入力された値Ｐ及びべき指数ｋをメモリ３０に書き込む機能と、メモリ３０内の値Ｐを途中の計算結果Ｑに代入し、当該計算結果Ｑをメモリ３０に書き込む機能と、メモリ３０内のべき指数ｋの最上位桁ｔ−１から最下位桁０までの各桁ｉに対し、Ｑ＝Ｑ2 ｍｏｄ （ｘ−１）Ｆ（ｘ）Ｇ（ｘ）の計算命令と、メモリ３０内の途中の計算結果ＱとをＧＦ（ｐlm）計算部４０に送出し、折り返し、ＧＦ（ｐlm）計算部４０から受けた計算結果Ｑによりメモリ３０内の計算結果Ｑを更新する機能と、メモリ３０内のべき指数ｋのｉ桁目の値ｋiが１のときには、Ｑ＝Ｑ×Ｐ ｍｏｄ （ｘ−１）Ｆ（ｘ）Ｇ（ｘ）の計算命令と、メモリ３０内の途中の計算結果Ｑ及び入力された値ＰとをＧＦ（ｐlm）計算部４０に送出し、折り返し、ＧＦ（ｐlm）計算部４０から受けた計算結果Ｑによりメモリ３０内の計算結果Ｑを更新する機能と、メモリ３０内のべき指数ｋの最下位桁０に対する計算の終了後、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算命令と、メモリ３０内の途中の計算結果ＱとをＧＦ（ｐlm）計算部４０に送出し、折り返し、ＧＦ（ｐlm）計算部４０から受けた計算結果Ｑによりメモリ３０内の計算結果Ｑを更新する機能と、更新後の計算結果Ｑを入出力部１０に出力して処理を終了する機能とをもっている。
【００６４】
メモリ３０は、各部２０，４０〜６０から読出／書込可能な記憶装置である。
【００６５】
ＧＦ（ｐlm）計算部４０は、ＧＦ（ｐlm）演算制御部４１、ＧＦ（ｐlm）基本演算実行部４２及びＧ（ｘ）剰余演算実行部４３を備えている。
【００６６】
ＧＦ（ｐlm）演算制御部４１は、べき乗計算制御部２０から受けた計算命令及び途中の計算結果Ｑに基づいて、各演算実行部４２，４３及びＧＦ（ｐm）計算部５０を制御する機能と、この制御により得られた新たな計算結果Ｑをべき乗計算制御部２０に送出する機能とをもっている。
【００６７】
ＧＦ（ｐlm）基本演算実行部４２は、ＧＦ（ｐlm）演算制御部４１に制御され、適宜メモリ３０を参照しつつ、有限体ＧＦ（ｐlm）上の基本演算を実行し、実行結果をＧＦ（ｐlm）演算制御部４１に送出する機能をもっている。
【００６８】
Ｇ（ｘ）剰余演算実行部４３は、ＧＦ（ｐlm）演算制御部４１に制御され、適宜メモリ３０を参照しつつ、有限体ＧＦ（ｐlm）上で多項式Ｇ（ｘ）による剰余演算を実行し、実行結果をＧＦ（ｐlm）演算制御部４１に送出する機能をもっている。
【００６９】
ＧＦ（ｐm）計算部５０は、ＧＦ（ｐm）演算制御部５１、ＧＦ（ｐm）基本演算実行部５２、Ｆ（ｘ）剰余演算実行部５３及び（ｘ−１）Ｆ（ｘ）剰余演算実行部５４を備えている。
【００７０】
ＧＦ（ｐm）演算制御部５１は、ＧＦ（ｐlm）演算制御部４１に制御され、各演算実行部５２〜５４及びＧＦ（ｐ）計算部６０を制御する機能と、この制御により得られた計算結果をＧＦ（ｐlm）演算制御部４１に送出する機能とをもっている。
【００７１】
ＧＦ（ｐm）基本演算実行部５２は、ＧＦ（ｐm）演算制御部５１に制御され、適宜メモリ３０を参照しつつ、有限体ＧＦ（ｐm）上の基本演算を実行し、実行結果をＧＦ（ｐm）演算制御部５１に送出する機能をもっている。
【００７２】
Ｆ（ｘ）剰余演算実行部５３は、ＧＦ（ｐm）演算制御部５１に制御され、適宜メモリ３０を参照しつつ、有限体ＧＦ（ｐm）上で多項式Ｆ（ｘ）による剰余演算を実行し、実行結果をＧＦ（ｐm）演算制御部５１に送出する機能をもっている。
【００７３】
（ｘ−１）Ｆ（ｘ）剰余演算実行部５４は、ＧＦ（ｐm）演算制御部５１に制御され、適宜メモリ３０を参照しつつ、有限体ＧＦ（ｐm）上で多項式（ｘ−１）Ｆ（ｘ）による剰余演算を実行し、実行結果をＧＦ（ｐm）演算制御部５１に送出する機能をもっている。
【００７４】
ＧＦ（ｐ）計算部６０は、ＧＦ（ｐ）演算制御部６１、ＧＦ（ｐ）基本演算実行部６２及びｐ剰余演算実行部６３を備えている。
【００７５】
ＧＦ（ｐ）演算制御部６１は、ＧＦ（ｐm）演算制御部５１に制御され、各演算実行部６２，６３を制御する機能と、この制御により得られた計算結果をＧＦ（ｐm）演算制御部５１に送出する機能とをもっている。
【００７６】
ＧＦ（ｐ）基本演算実行部５２は、ＧＦ（ｐ）演算制御部６１に制御され、適宜メモリ３０を参照しつつ、有限体ＧＦ（ｐ）上の基本演算を実行し、実行結果をＧＦ（ｐ）演算制御部６１に送出する機能をもっている。
【００７７】
ｐ剰余演算実行部５３は、ＧＦ（ｐ）演算制御部６１に制御され、適宜メモリ３０を参照しつつ、有限体ＧＦ（ｐ）上で素数ｐによる剰余演算を実行し、実行結果をＧＦ（ｐ）演算制御部６１に送出する機能をもっている。
【００７８】
なお、以上のような べき乗計算装置１００は、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体からべき乗計算装置のコンピュータにインストールされ、べき乗計算装置の機能を実現させるためのプログラムが用いられる。このようにべき乗計算装置１００がハードウェア構成又はプログラムを用いた構成で実施可能なことは、以下の各実施形態でも同様である。
【００７９】
次に、以上のように構成された べき乗計算装置の動作について図３のフローチャートを用いて説明する。
【００８０】
（ＳＴ１１）  べき乗計算装置１００においては、入出力部１０により、合成数次拡大体上の値Ｐと、べき指数ｋとがべき乗計算制御部２０に入力される。べき乗計算制御部２０は、この値Ｐ及びべき指数ｋをメモリ３０に書き込む。
【００８１】
（ＳＴ１２）  べき乗計算制御部２０は、メモリ３０内の値Ｐを途中の計算結果Ｑに代入し、当該計算結果Ｑをメモリ３０に書き込む。
【００８２】
（ＳＴ１３）  べき乗計算制御部２０は、メモリ３０内のべき指数ｋにおける処理対象の桁ｉを最上位桁ｔ−１に初期化し、当該処理対象の桁ｉ（＝ｔ−１）をメモリ３０に書き込む。
【００８３】
（ＳＴ１４）  べき乗計算制御部２０は、Ｑ＝Ｑ2 ｍｏｄ （ｘ−１）Ｆ（ｘ）Ｇ（ｘ）の計算命令と、メモリ３０内の途中の計算結果ＱとをＧＦ（ｐlm）計算部４０に送出する。ＧＦ（ｐlm）計算部４０では、計算命令と、途中の計算結果Ｑとに基づいて、他の計算部５０，６０を用いつつ、Ｑ＝Ｑ2 ｍｏｄ （ｘ−１）Ｆ（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑをべき乗計算制御部２０に送出する。
【００８４】
べき乗計算制御部２０は、ＧＦ（ｐlm）計算部４０から受けた計算結果Ｑによりメモリ３０内の計算結果Ｑを更新する。
【００８５】
（ＳＴ１５）  べき乗計算制御部２０は、処理対象のｉ桁目の値ｋiが１であるか否かを判定する。
【００８６】
（ＳＴ１６）  べき乗計算制御部２０は、ステップＳＴ１５の判定の結果、ｉ桁目の値ｋiが１である場合（ｋi＝１）、Ｑ＝Ｐ×Ｑ ｍｏｄ （ｘ−１）Ｆ（ｘ）Ｇ（ｘ）の計算命令と、メモリ３０内の途中の計算結果Ｑと、メモリ３０内の値ＰとをＧＦ（ｐlm）計算部４０に送出する。ＧＦ（ｐlm）計算部４０では、計算命令と、途中の計算結果Ｑと、値Ｐとに基づいて、他の計算部５０，６０を用いつつ、Ｑ＝Ｐ×Ｑ ｍｏｄ （ｘ−１）Ｆ（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑをべき乗計算制御部２０に送出する。
【００８７】
べき乗計算制御部２０は、ＧＦ（ｐlm）計算部４０から受けた計算結果Ｑによりメモリ３０内の計算結果Ｑを更新する。
【００８８】
（ＳＴ１７）  べき乗計算制御部２０は、ステップＳＴ１５の判定結果が否の場合（ｋi≠１、すなわちｋi＝０の場合）、又はステップＳＴ１６を終了した場合、メモリ３０内の処理対象の桁ｉが０であるか否かを判定する。
【００８９】
（ＳＴ１８）  べき乗計算制御部２０は、ステップＳＴ１７の判定結果が否の場合（ｉ≠０）、メモリ３０内の処理対象の桁ｉを−１だけ更新し、ステップＳＴ１４に戻ってＳＴ１４を再度実行する。
【００９０】
（ＳＴ１９）  べき乗計算制御部２０は、ステップＳＴ１７の判定の結果、処理対象の桁ｉが０である場合（ｉ＝０）、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算命令と、メモリ３０内の途中の計算結果ＱとをＧＦ（ｐlm）計算部４０に送出する。ＧＦ（ｐlm）計算部４０では、計算命令と、途中の計算結果Ｑと、値Ｐとに基づいて、他の計算部５０，６０を用いつつ、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑをべき乗計算制御部２０に送出する。なお、このＱ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算結果Ｑは、Ｐkの計算結果に相当している。すなわち、この計算結果はＱ＝Ｐkである。
【００９１】
べき乗計算制御部２０は、この計算結果Ｑによりメモリ３０内の計算結果Ｑを更新し、更新後の計算結果Ｑを入出力部２０に送出する。
【００９２】
（ＳＴ２０）  べき乗計算装置１００は、この計算結果Ｑ（＝Ｐk）を入出力部２０により出力し、処理を終了する。
【００９３】
上述したように本実施形態によれば、素体ＧＦ（ｐ）をｍ次多項式Ｆ（ｘ）及びｌ次多項式Ｇ（ｘ）により順次拡大して構成された有限体である合成数次拡大体ＧＦ（ｐml）に関し、ｍ次多項式Ｆ（ｘ）（＝ｘm＋ｘm-1＋…＋ｘ＋１）のゼロ以外の項よりもゼロ以外の項が少ない多項式（ｘ−１）Ｆ（ｘ）（＝ｘm+1＋１）に基づく、Ｑ＝Ｑ2 ｍｏｄ （ｘ−１）Ｆ（ｘ）Ｇ（ｘ）及びＱ＝Ｐ×Ｑ ｍｏｄ （ｘ−１）Ｆ（ｘ）Ｇ（ｘ）の計算を実行し、最後に、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算を実行する。
【００９４】
このように、本来のＦ（ｘ）よりも少ない項の多項式（ｘ−１）Ｆ（ｘ）に基づき、途中の剰余演算を高速に実行し、最後に、本来のＦ（ｘ）に基づき、剰余演算を実行する構成により、各多項式により有限体を拡大してなる合成数次拡大体上でべき乗計算を行う際に、最初に拡大に用いた多項式による剰余演算を高速に実行することができる。
【００９５】
（第２の実施形態の具体的な構成）
図４は本発明の第２の実施形態に係る べき乗計算装置の構成を示す模式図であり、図１と同一機能部については同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。
【００９６】
すなわち、第２の実施形態は、前述したように、第１の実施形態のＡＯＰ（＝ｆ（ｘ）＝Ｆ（ｘ））及び（ｘ−１）Ｆ（ｘ）に代えて、より一般的な多項式Ｆ（ｘ）及びＦ’（ｘ）を用いている。
【００９７】
これに伴い、べき乗計算装置１００は、図１に示したＦ（ｘ）剰余演算実行部５３及び（ｘ−１）Ｆ（ｘ）剰余演算実行部５４に代えて、図４に示すように、Ｆ（ｘ）剰余演算実行部５３’及びＦ’（ｘ）剰余演算実行部５４’を備えた構成となっている。
【００９８】
Ｆ（ｘ）剰余演算実行部５３’は、ＧＦ（ｐm）演算制御部５１に制御され、適宜メモリ３０を参照しつつ、有限体ＧＦ（ｐm）上で、より一般的な多項式Ｆ（ｘ）による剰余演算を実行し、実行結果をＧＦ（ｐm）演算制御部５１に送出する機能をもっている。
【００９９】
Ｆ’（ｘ）剰余演算実行部５４は、ＧＦ（ｐm）演算制御部５１に制御され、適宜メモリ３０を参照しつつ、有限体ＧＦ（ｐm）上で、より一般的な多項式Ｆ’（ｘ）による剰余演算を実行し、実行結果をＧＦ（ｐm）演算制御部５１に送出する機能をもっている。
【０１００】
次に、以上のように構成された べき乗計算装置の動作について図５のフローチャートを用いて説明する。
【０１０１】
（ＳＴ１１〜ＳＴ１３）  べき乗計算装置１００は、前述した通り、ステップＳＴ１１〜ＳＴ１３を実行する。
【０１０２】
（ＳＴ１４’）  べき乗計算制御部２０は、Ｑ＝Ｑ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算命令と、メモリ３０内の途中の計算結果ＱとをＧＦ（ｐlm）計算部４０に送出する。ＧＦ（ｐlm）計算部４０では、計算命令と、途中の計算結果Ｑとに基づいて、他の計算部５０，６０を用いつつ、Ｑ＝Ｑ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑをべき乗計算制御部２０に送出する。
【０１０３】
べき乗計算制御部２０は、ＧＦ（ｐlm）計算部４０から受けた計算結果Ｑによりメモリ３０内の計算結果Ｑを更新する。
【０１０４】
（ＳＴ１５）  べき乗計算制御部２０は、前述した通り、ステップＳＴ１５を実行する。
【０１０５】
（ＳＴ１６’）  べき乗計算制御部２０は、ステップＳＴ１５の判定の結果、ｉ桁目の値ｋiが１である場合（ｋi＝１）、Ｑ＝Ｐ×Ｑ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算命令と、メモリ３０内の途中の計算結果Ｑと、メモリ３０内の値ＰとをＧＦ（ｐlm）計算部４０に送出する。ＧＦ（ｐlm）計算部４０では、計算命令と、途中の計算結果Ｑと、値Ｐとに基づいて、他の計算部５０，６０を用いつつ、Ｑ＝Ｐ×Ｑ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑをべき乗計算制御部２０に送出する。
【０１０６】
べき乗計算制御部２０は、ＧＦ（ｐlm）計算部４０から受けた計算結果Ｑによりメモリ３０内の計算結果Ｑを更新する。
【０１０７】
（ＳＴ１７〜ＳＴ１８）  べき乗計算制御部２０は、前述した通り、ステップＳＴ１７〜ＳＴ１８を実行する。
【０１０８】
（ＳＴ１９）  べき乗計算制御部２０は、ステップＳＴ１７の判定の結果、処理対象の桁ｉが０である場合（ｉ＝０）、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算命令と、メモリ３０内の途中の計算結果ＱとをＧＦ（ｐlm）計算部４０に送出する。ＧＦ（ｐlm）計算部４０では、計算命令と、途中の計算結果Ｑと、値Ｐとに基づいて、他の計算部５０，６０を用いつつ、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算を実行し、得られた計算結果Ｑをべき乗計算制御部２０に送出する。この計算結果ＱはＰkに相当する（Ｑ＝Ｐk）。
【０１０９】
べき乗計算制御部２０は、この計算結果Ｑによりメモリ３０内の計算結果Ｑを更新し、更新後の計算結果Ｑを入出力部２０に送出する。
【０１１０】
（ＳＴ２０）  べき乗計算装置１００は、前述した通り、ステップＳＴ２０を実行し、処理を終了する。
【０１１１】
上述したように本実施形態によれば、素体ＧＦ（ｐ）をｍ次多項式Ｆ（ｘ）及びｌ次多項式Ｇ（ｘ）により順次拡大して構成された有限体である合成数次拡大体ＧＦ（ｐml）に関し、ｍ次多項式Ｆ（ｘ）のゼロ以外の項よりもゼロ以外の項が少ない多項式Ｆ’（ｘ）に基づく、Ｑ＝Ｑ2 ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）及びＱ＝Ｐ×Ｑ ｍｏｄ Ｆ’（ｘ）Ｇ（ｘ）の計算を実行し、最後に、Ｑ＝Ｑ ｍｏｄ Ｆ（ｘ）Ｇ（ｘ）の計算を実行する。
【０１１２】
このように、本来のＦ（ｘ）よりも少ない項の多項式Ｆ’（ｘ）に基づき、途中の剰余演算を高速に実行し、最後に、本来のＦ（ｘ）に基づき、剰余演算を実行する構成により、各多項式により有限体を拡大してなる合成数次拡大体上でべき乗計算を行う際に、最初に拡大に用いた多項式による剰余演算を高速に実行することができる。
【０１１３】
すなわち、第２の実施形態によれば、第１の実施形態をより一般的に構成し、Ｆ（ｘ）よりも高速に剰余演算を実行できるＦ’（ｘ）を用いて途中計算を行うことにより、全体の計算を高速化することができる。
【０１１４】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１１５】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１１６】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１１７】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１１８】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１１９】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１２０】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１２１】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１２２】
【図１】本発明の第１の実施形態に係るべき乗計算装置の全体構成を示すブロック図である。
【図２】同実施形態における有限体を示す模式図である。
【図３】同実施形態における動作を説明するためのフローチャートである。
【図４】本発明の第２の実施形態に係るべき乗計算装置の全体構成を示すブロック図である。
【図５】同実施形態における動作を説明するためのフローチャートである。
【図６】各実施形態のアルゴリズムを従来と比較して示す図である。
【符号の説明】
【０１２３】
１００…べき乗計算装置、１０…入出力部、２０…べき乗計算制御部、３０…メモリ、４０…ＧＦ（ｐlm）計算部、４１…ＧＦ（ｐlm）演算制御部、４２…ＧＦ（ｐlm）基本演算実行部、４３…Ｇ（ｘ）剰余演算実行部、５０…ＧＦ（ｐm）計算部、５１…ＧＦ（ｐm）演算制御部、５２…ＧＦ（ｐm）基本演算実行部、５３，５３’…Ｆ（ｘ）剰余演算実行部、５４…（ｘ−１）Ｆ（ｘ）剰余演算実行部、５４’…Ｆ’（ｘ）剰余演算実行部、６０…ＧＦ（ｐ）計算部、６１…ＧＦ（ｐ）演算制御部、６２…ＧＦ（ｐ）基本演算実行部、６３…ｐ剰余演算実行部。
【図１】
0004724200.tif 000003
【図２】
0004724200.tif 000004
【図３】
0004724200.tif 000005
【図４】
0004724200.tif 000006
【図５】
0004724200.tif 000007
【図６】
0004724200.tif 000008