べき指数を1ビットからビット長wの範囲で分割して複数のワードにする分割手段と、前記複数のワードから所定のワードを選択する選択手段と、前記選択されたワードを含み、項の総数が2w1以下の条件を満たす数列を生成する生成手段と、前記複数のワードのうち、前記数列に含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割する再分割手段と、前記数列の各項をべき指数に含む乗算剰余テーブルを算出する算出手段と、前記分割されたワード、前記再分割されたワード、および、前記乗算剰余テーブルを用いて前記べき指数に対するべき乗剰余演算を行う第一の演算手段とを有することを特徴とする情報処理装置。前記生成手段は、前記条件を満たす複数の数列から、前記選択されたワードを含む数列を選択することを特徴とする請求項1に記載された情報処理装置。前記再分割手段は、前記再分割したワードのうち、前記数列に含まれないワードを前回の分割よりも1ビット少ない範囲で再分割することを特徴とする請求項1または請求項2に記載された情報処理装置。前記算出手段は、前記数列が含む値が1の項を除く各項をべき指数に含む前記乗算剰余テーブルを算出することを特徴とする請求項1から請求項3の何れか一項に記載された情報処理装置。さらに、前記第一の演算手段とは異なる方法により、前記分割されたワードおよび前記再分割されたワードを用いて前記べき指数に対するべき乗剰余演算を行う第二の演算手段と、前記数列、前記分割されたワードおよび前記再分割されたワードから、前記算出手段と前記第一の演算手段の乗算剰余演算回数S1、および、前記第二の演算手段の乗算剰余演算回数S2を計算する計算手段と、前記乗算剰余演算回数S1とS2を用いて、前記算出手段と前記第一の演算手段による前記べき乗剰余演算、および、前記第二の演算手段による前記べき乗剰余演算を選択的に制御する制御手段とを有することを特徴とする請求項1から請求項4の何れか一項に記載された情報処理装置。前記制御手段は、S1≧S2の場合、前記生成手段に前記数列を再生成させることを特徴とする請求項5に記載された情報処理装置。前記制御手段は、S1<S2の場合は前記算出手段と前記第一の演算手段に前記べき乗剰余演算を実行させ、S1≧S2かつ前記生成手段が再生成可能な数列がない場合は前記第二の演算手段に前記べき乗剰余演算を実行させることを特徴とする請求項6に記載された情報処理装置。分割手段、選択手段、生成手段、再分割手段、算出手段、演算手段を有する情報処理装置の情報処理方法であって、前記分割手段が、べき指数を1ビットからビット長wの範囲で分割して複数のワードにし、前記選択手段が、前記複数のワードから所定のワードを選択し、前記生成手段が、前記選択されたワードを含み、項の総数が2w1以下の条件を満たす数列を生成し、前記再分割手段が、前記複数のワードのうち、前記数列に含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割し、前記算出手段が、前記数列の各項をべき指数に含む乗算剰余テーブルを算出し、前記演算手段が、前記分割されたワード、前記再分割されたワード、および、前記乗算剰余テーブルを用いて、前記べき指数に対するべき乗剰余演算を行うことを特徴とする情報処理方法。コンピュータ装置を請求項1から請求項7の何れか一項に記載された情報処理装置の各手段として機能させることを特徴とするプログラム。本発明は、乗算剰余テーブルのエントリ数を低減して、べき乗剰余を演算することを目的とする。本発明は、前記の目的を達成する一手段として、以下の構成を備える。本発明にかかる情報処理は、べき指数を1ビットからビット長wの範囲で分割して複数のワードにし、前記複数のワードから所定のワードを選択し、前記選択されたワードを含み、項の総数が2w1以下の条件を満たす数列を生成し、前記複数のワードのうち、前記数列に含まれないワードを前回の分割における範囲よりも1ビット少ない範囲で再分割し、前記数列の各項をべき指数に含む乗算剰余テーブルを算出し、前記分割されたワード、前記再分割されたワード、および、前記乗算剰余テーブルを用いて、前記べき指数に対するべき乗剰余演算を行うことを特徴とする。本発明によれば、乗算剰余テーブルのエントリ数を低減して、べき乗剰余を演算することができる。以下、本発明にかかる実施例の情報処理を図面を参照して詳細に説明する。[装置の構成]図2のブロック図により実施例の情報処理装置の構成例を説明する。入力部11は、ハードディスク、メモリカード、光ディスクなどの記憶メディアに格納された数値eを入力する。数値eは、例えば公開鍵暗号における公開鍵や秘密鍵に相当する。また、数値eは、情報処理装置のユーザインタフェイスを介して、ユーザが指定または入力することもできる。初期分割部12は、入力された数値eを1ビットから最大分割ビット長wの範囲で分割する。この分割処理には、例えば非特許文献1の17頁から18頁に記載された方法を適用する。当該文献は、決定されたビット長固定で分割するconstantlengthnonzerowindows、可変長かつ指定されたビット長を最大の分割長とするvariablelengthnonzerowindowsを記載する。例えばCLNWでは、状態ZWとNWを遷移しながらビット分割を行う。CLNWは最下位ビットから順に最上位ビットまでビット探索を行う。CLNWのアルゴリズムは以下のとおりである。状態ZW:次のビットが‘0’ならば状態ZWに、‘0’でなければ状態NWに遷移する。状態NW:予め指定されたビット長まで状態NWを維持し、次のビットが‘0’ならば状態ZWに、‘0’でなければ状態NWに遷移する。図3によりビットの分割例を説明する。図3は、e12405733をCLNW最大分割ビット長w4で分割した例を示す。図3においてアポストロフィで囲んだ二進数値eiを以後ワードとして説明する。分割結果eiは、選択部13および再分割部15に供給される。選択部13は、詳細は後述するが、初期分割部12によって分割された各ワードeiから所定のワードexを選択し、選択結果を数列生成部14に供給する。数列生成部14は、詳細は後述するが、選択部13の選択結果に基づき、exを含む数列Fkex⊂Fk:k12...mを生成し、数列Fkを再分割部15および乗算剰余テーブル算出部16に供給する。再分割部15は、詳細は後述するが、分割結果eiのうち数列Fkに含まれないワードを、前回の分割における範囲よりも1ビット少ない範囲例えば、1ビットからw1ビットで複数の数値ejej⊂Fk:j12...に再分割する。そして、分割結果eiおよび再分割結果ejをべき乗剰余演算部17に供給する。乗算剰余テーブル算出部16は、詳細は後述するが、数列Fkに基づき、数列Fkの値が1の項を除くF2からFmまでの各項をべき指数に含む乗算剰余テーブルMFkを算出する。そして、乗算剰余テーブルMFkをべき乗剰余演算部17に供給する。べき乗剰余演算部17は、分割結果ei、再分割結果ejおよび乗算剰余テーブルMFkを用いて、べき乗剰余CMemodNを演算する。出力部18は、べき乗剰余演算部17が演算したべき乗剰余Cを公開鍵暗号の暗号化部、復号部例えばCODECなどに供給する。なお、図2に示す情報処理装置は、専用のハードウェアとして実現してもよい。あるいは、例えばコンピュータ機器にCODECのプログラムの一部として、べき乗剰余の演算プログラムを供給し、コンピュータ機器のCPUがRAMをワークメモリとして当該演算プログラムを実行することで、実施例の情報処理装置の機能が実現される。[演算処理]図4のフローチャートによりべき乗剰余の演算処理を説明する。なお、図4に示す処理は、図2に示す情報処理装置が行う処理である。入力部11は数値eを入力する。数値eは、例えば1024ビット長の公開鍵である。ここでは、説明を簡単にするために、図3に示すe12405733を入力したとする。次に、初期分割部12は、数値eを1ビットから最大分割ビット長wの範囲でワードeiに分割する。なお、最大分割ビット長wは、情報処理装置が実行するプログラムに指定されたものを用いてもよいし、ユーザが指定するものを用いてもよい。例えば図3に示すように、数値eは1、0、1111、0101、0、0101、1111、0、0101に分割される次に、選択部13は、分割された各ワードeiから所定のワードexを選択する。ここでは、説明を簡単にするため、出現頻度が最も高いワードを選択することにする。図3に示す分割例の場合は最も出現頻度が高い0101が選択される。なお、ワードexの選択方法は、出現頻度が二番目に高いワードを選択する、情報処理装置が実行するプログラムに指定された特定の値を選択するなど、任意の方法を用いることができる。次に、数列生成部14は、ワードexを含む数列Fkを生成する。この数列は、加算鎖に相当し、例えば非特許文献1の22頁に記載された、バイナリ法、オクタル法、ファクタ法などの方法によって数列を生成する。ワードex0101に対してオクタル法を適用すると、5を含む数列Fkとして12345が算出される。次に、数列生成部14は、生成した数列Fkの項数mと2w1を比較して、m>2w1の場合は処理をステップS14に戻し、他の数列生成方法を適用する。上記の例ではFk12345の項数mは5、図3に示すように最大分割ビット長wは4であり、m<24115である。m≦2w1の場合は、数列Fkを再分割部15と乗算剰余テーブル算出部16に供給し、処理をステップS16に進める。次に、再分割部15は、ワードeiが数列Fkに含まれるか否かを判定し、ワードeiのすべてが数列Fkに含まれる場合は処理をステップS18へ進める。一方、数列Fkに含まれないワードeiが存在する場合、再分割部15は、数列Fkに含まれないeiを前回の分割における範囲よりも1ビット少ない範囲で複数の数値ejに再分割し、処理をステップS16に戻す。図3において、e21111は数列Fk12345に含まれない。そこで、分割長を1ビットから3ビットとしてCLNWにより1111を再分割する。この再分割により、図3に示すように、数値eは1、0、1、111、0101、0、0101、1、111、0、0101に分割される。上記再分割によって得られるe2111は数列Fk12345に含まれない。そこで、分割長を1ビットから2ビットとしてCLNWにより111を再分割する。この再分割により、図3に示すように、数値eは1、0、1、1、11、0101、0、0101、1、1、11、0、0101に分割される。この再分割によれば、ワードei、ejは1、11、0101の何れかになり、つまりeiej⊂Fkになる。次に、乗算剰余テーブル算出部16は、数列Fkに基づき、F1=1を除くF2からFmまでの各項をべき指数に含む乗算剰余テーブルMFkを算出して、MFkをメモリに格納する。図5によりべき乗剰余を演算する過程を説明する。図5は、数列Fk12345から乗算剰余テーブルMFkを算出する過程を示す。式に示した加算鎖の性質により、各MFiは、それ以前に算出した数値MFj×MFkにより演算可能である。なお、数列の種類によらず必ずF11、F22になるが、M1MmodNであり、M1の計算とメモリは不要である。次に、べき乗剰余演算部17は、分割結果ei、ejおよび乗算剰余テーブルMFkを用いて、べき乗剰余CMemodNを演算する。図3が分割結果Wnであるとする。入力をM、Wn、N、MFkとすると、べき乗剰余Cを演算するアルゴリズムは下のようになる。C1;forifCC×C;処理31ifCCpow2×MFWi;処理32returnC;...ここで、LはWiのビット長、pow2は2のx乗。図5はべき乗剰余CM12405733modNを演算する過程を示す。べき乗剰余Cの演算が終了すると、出力部18は、べき乗剰余Cを出力する。このように、MFkのFkとして奇数すべての候補を取るSウィンドウ法と比べ、MFkを計算するための時間やメモリの無駄を削減することができる。例えば、図5に示す乗算剰余テーブルMFkは四つのエントリF1を除くを有する。ウィンドウ幅w4のSウィンドウ法によれば、乗算剰余テーブルMFkのエントリ数は2418になる。また、図5において、実演算処理に使用されないエントリはM4だけであり、四つのエントリのうち無駄は一つだけである。また、削減した処理時間を有効活用するために、初期分割における分割長1ビットからwビットの範囲を広くとれば、MemodNで必要になる乗算剰余演算回数を少なくすることができる。従って、べき乗剰余演算の全体の処理時間を削減することが可能になる。上述した演算処理において、ステップS18、S19を除く各ステップは、べき乗剰余演算における指数eのみの処理である。べき指数eは、通常、公開鍵や秘密鍵であり、暗号処理中に鍵生成、鍵交換が必要な場合を除き、事前に取得することができる。言い換えれば、ステップS11からS17までの処理は、予め、べき乗剰余演算の処理時間に影響を与えることなく実行可能である。以下、本発明にかかる実施例2の情報処理を説明する。なお、実施例2において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。[装置の構成]図6のブロック図により実施例2の情報処理装置の構成例を説明する。実施例2の情報処理装置は、数列Fkを複数、予め格納する数列格納部21を有する。数列格納部21が格納する数列Fkは、項の総数mが2w1以下の条件を満たす。数列生成部14は、数列格納部21に格納された数列Fkから、選択部13が出力するワードexを含む数列Fkex⊂Fkを選択し、選択した数列Fkを再分割部15、乗算剰余テーブル算出部16に供給する。[演算処理]図7のフローチャートにより実施例2のべき乗剰余の演算処理を説明する。なお、図7に示す処理は、図6に示す情報処理装置が行う処理である。ステップS11からS13、S16からS19は実施例1と同様の処理であり、それらの詳細説明を省略する。数列生成部14は、選択部13の選択結果ワードexを含む数列を、数列格納部21が格納する数列Fkから選択する。ここでは、説明を簡単にするために、実施例1と同様に0101が選択されたことにする。そして、数列生成部14が0101を含む数列としてFk1235を選択したことにする。なお、数列Fk1235の項の総数mは4であり、24115以下の条件を満たす。実施例2において選択される数列Fk1235は、実施例1において算出される数列Fk12345よりも項数が少ない。実施例1と同様にCM12405733modNを演算する場合、実演算処理にかかるコストは実施例1と同様だが、乗算剰余テーブルMFkの算出コストはM4が不要な分、低減される。以下、本発明にかかる実施例3の情報処理を説明する。なお、実施例3において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。実施例3では、実施例1に示したべき乗剰余演算以下、再分割法の乗算剰余演算回数と、Sウィンドウ法などの他のべき乗剰余演算方法の乗算剰余演算回数を計算する。そして、それらの計算結果から、再分割法の実行、数列生成部14による数列Fkの再算出を含む再分割法の実行、および、Sウィンドウ法などの他のべき乗剰余演算方法以下、他の演算法の実行を選択的に制御する演算処理を説明する。[装置の構成]図8のブロック図により実施例3の情報処理装置の構成例を説明する。演算回数計算部31は、再分割部15の分割結果ei、ejおよび数列生成部14が算出した数列Fkから、再分割法における乗算剰余演算回数S1、並びに、他の演算法を用いる場合の乗算剰余演算回数S2を計算する。演算方法制御部32は、演算回数計算部31の計算結果に基づき、数列生成部14に新たな数列Fkを算出させて数値eの分割をやり直したり、再分割法および他の演算法を選択的に制御する。第一の演算部であるべき乗剰余演算部17は、再分割法によりべき乗剰余演算を行う。また、第二の演算部であるべき乗剰余演算部33は、他の演算法によりべき乗剰余演算を行う。[演算処理]図9のフローチャートにより実施例3のべき乗剰余の演算処理を説明する。なお、図9に示す処理は、図8に示す情報処理装置が行う処理である。ステップS11からS19は実施例1と同様の処理であり、それらの詳細説明を省略する。演算回数計算部31は、再分割部15の分割結果ei、ejおよび数列生成部14が算出した数列Fkを入力して、第一のべき乗剰余演算部17の乗算剰余演算回数S1と、第二のべき乗剰余演算部33の乗算剰余演算回数S2を計算する。この計算は、実際の演算を行わずに、乗算剰余テーブル算出部16およびべき乗剰余演算部17の処理と同じアルゴリズムにおける乗算剰余演算の総数をカウントすることにより実現することができる。例えば、M12405733modN、数列Fk1235の場合、乗算剰余演算回数は12である。また、例えば、Sウィンドウ法をM12405733modNにウィンドウ長4ビットを適用すると、乗算剰余演算回数は13になる。演算方法制御部32は、乗算剰余演算回数S1とS2を比較して、S1<S2であれば処理をステップS18に進める。つまり、乗算剰余テーブル算出部16の処理および第一のべき乗剰余演算部17の処理が実行される。また、S1≧S2の場合、演算方法制御部32は、生成可能なすべての数列Fkを生成したか否かを数列生成部14に問い合わせる。そして、生成可能な数列Fkが残っている場合は、処理をステップS14に戻して、数列生成部14に数列Fkの再生成を行わせる。つまり、ステップS14からS32の処理が繰り返される。また、生成可能な数列Fkが残っていない場合、演算方法制御部32は、処理をステップS34に進める。つまり、S1≧S2かつ数列生成部14が再生成可能な数列がない場合は第二のべき乗剰余演算部33の処理が実行される。このように、再分割法によるべき乗剰余演算の演算コストが他の演算法よりも高い場合は、新たな数列により処理をやり直す、または、他の演算法を適用して、べき乗剰余演算の演算コストを極力抑えることができる。なお、図8には、実施例1の情報処理装置の構成に演算回数計算部31、演算方法制御部32、第二のべき乗剰余演算部33を加える構成を示した。しかし、実施例2の情報処理装置の構成に演算回数計算部31、演算方法制御部32、第二のべき乗剰余演算部33を加える構成としてもよい。そのような構成によれば、演算方法制御部32は、S1≧S2の場合、選択可能なすべての数列Fkを選択したか否かを数列生成部14に問い合わせる。そして、選択可能な数列Fkが残っている場合は、処理をステップS21に戻して、数列生成部14に数列Fkの再選択を行わせる。[変形例]●数列Fkの選択方法実施例2、3では、ワードexを含む数列Fkex⊂Fkの選択を説明したが、ワードexは複数あってもよい。つまり、図3に示す例の場合、0101だけでなく、1111を含む数列Fk例えば12351015を選択すれば、より効率的に数列Fkの選択処理を行うことが可能になる。●べき指数eの分割処理方法上述した実施例では、べき指数eをCLNWで分割または再分割する例を説明した。分割または再分割に用いる分割アルゴリズムは、毎回、異なってもよい。図3に示す例の場合、1111はCLNWによって最終的に図3に示すように1、1、11に分割される。しかし、数列Fk1235を適用する場合、11、11に分割すれば乗算剰余演算回数を一回削減することができる。つまり、数列Fkに適応して分割アルゴリズムを変更すれば、乗算剰余演算回数の削減が可能になる。[その他の実施例]また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェアプログラムを、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ又はCPUやMPU等がプログラムを読み出して実行する処理である。