楕円曲線上の点のスカラ倍演算を行う情報処理装置であって、スカラ正の整数を入力し、前記スカラを符号付き二進法の、負数を含む数値に変換する変換手段と、前記数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割する分割手段と、前記複数の数値から特定の数値を選択する選択手段と、前記選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得する取得手段と、前記複数の数値の絶対値のうち前記数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割する再分割手段と、前記数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出する算出手段と、前記分割された複数の数値、前記再分割された複数の数値、および、前記倍算テーブルを用いて前記スカラ倍演算を行う第一の演算手段とを有することを特徴とする情報処理装置。前記閾値は、NAFSウィンドウ法における倍算テーブルの候補の数であることを特徴とする請求項1に記載された情報処理装置。前記候補の数は2ww31から計算されることを特徴とする請求項2に記載された情報処理装置。前記第一の演算手段は、前記楕円曲線上の点を2λ倍λは1≦λ≦wの整数する倍算演算と、前記楕円曲線上の点と前記倍算テーブルの加算演算または減算演算を、前記数値の最上位ビットから最下位ビットまで繰り返して、前記楕円曲線上の点の前記スカラ倍を演算することを特徴とする請求項1から請求項3の何れか一項に記載された情報処理装置。前記取得手段は、所定のアルゴリズムにより前記数列を計算することを特徴とする請求項1から請求項4の何れか一項に記載された情報処理装置。さらに、前記項の総数が前記閾値よりも少ない条件を満たす複数の数列を格納する格納手段を有し、前記取得手段は、前記格納手段に格納された複数の数列から、前記選択された数値の絶対値を含み、前記項の総数が最小の数列を選択することを特徴とする請求項1から請求項4の何れか一項に記載された情報処理装置。さらに、前記第一の演算手段とは異なる方法により、前記スカラ倍演算を行う第二の演算手段と、前記分割された複数の数値、前記再分割された複数の数値および前記数列に基づき、前記第一の演算手段の総スカラ倍演算回数N1および前記第二の演算手段の総スカラ倍演算回数N2を計算する計算手段と、前記総スカラ倍演算回数N1とN2を用いて、前記第一の演算手段による前記スカラ倍演算、および、前記第二の演算手段による前記スカラ倍演算を選択的に制御する制御手段とを有することを特徴とする請求項1から請求項6の何れか一項に記載された情報処理装置。変換手段、分割手段、選択手段、取得手段、再分割手段、算出手段、演算手段を有し、楕円曲線上の点のスカラ倍演算を行う情報処理装置の情報処理方法であって、前記変換手段が、スカラ正の整数を入力し、前記スカラを符号付き二進法の、負数を含む数値に変換し、前記分割手段が、前記数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割し、前記選択手段が、前記複数の数値から特定の数値を選択し、前記取得手段が、前記選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得し、前記再分割手段が、前記複数の数値の絶対値のうち前記数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割し、前記算出手段が、前記数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出し、前記演算手段が、前記分割された複数の数値、前記再分割された複数の数値、および、前記倍算テーブルを用いて前記スカラ倍演算を行うことを特徴とする情報処理方法。コンピュータを請求項1から請求項7の何れか一項に記載された情報処理装置の各手段として機能させるためのプログラム。本発明は、NAFSウィンドウ法に必要な倍算テーブルの総数よりも少ない倍算テーブル数でスカラ倍演算を行うことを目的とする。本発明は、前記の目的を達成する一手段として、以下の構成を備える。本発明にかかる情報処理は、楕円曲線上の点のスカラ倍演算を行う情報処理であって、スカラ正の整数を入力し、前記スカラを符号付き二進法の、負数を含む数値に変換し、前記数値を1ビットから最大分割ビット長wの範囲の複数の数値に分割し、前記複数の数値から特定の数値を選択し、前記選択された数値の絶対値を含み、項の総数が前記最大分割ビット長wの関数である閾値よりも少ない数列を取得し、前記複数の数値の絶対値のうち前記数列に含まれない数値を1ビットから前記最大分割ビット長wの範囲の複数の数値に再分割し、前記数列に含まれる2以上の各項をスカラに含む倍算テーブルを算出し、前記分割された複数の数値、前記再分割された複数の数値、および、前記倍算テーブルを用いて前記スカラ倍演算を行うことを特徴とする。本発明によれば、NAFSウィンドウ法に必要な倍算テーブルの総数よりも少ない倍算テーブル数でスカラ倍演算を行うように、スカラを再分割することができる。その結果、倍算テーブルを計算するための処理時間や倍算テーブルを格納するメモリ領域を削減することができ、NAFSウィンドウ法よりも高速かつ省メモリでスカラ倍演算を行うことができる。以下、本発明にかかる実施例の情報処理を図面を参照して詳細に説明する。[装置の構成]図2のブロック図により本実施例の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示す。情報処理装置は、例えばCPU、ハードディスクドライブのような記憶装置、ROM、RAMのようなメモリなどのハードウェアを備える。そして、CPUが記憶装置やメモリに格納されたプログラムを実行することによりスカラ倍演算などの情報処理を行うコンピュータ装置である。変換部11は、記憶装置などに格納された数値x正の整数を読み出し、数値xを符号付き二進法の、負数を含む数値yに変換する。数値xは、例えば公開鍵暗号における公開鍵や秘密鍵に該当する。公開鍵や秘密鍵は、予め記憶装置などに格納されたものを用いてもよいし、情報処理装置を扱うユーザが情報処理装置のユーザインタフェイスなどを介して入力してもよい。符号付き二進法の数値への変換方法は、例えば、最下位ビットから最上位ビットに亘って変換を行うNAFアルゴリズムや、特許文献1に示される最上位ビットから最下位ビットに亘って変換を行うMOFアルゴリズムなどがある。なお、MOFはmutualoppositeformの略語である。図3によりスカラの分割を説明する。図3は数値x11957708941720303968251にNAFアルゴリズムを適用して得られる符号付き二進法の数値yを示す。初期分割部12は、変換部11が出力する符号付き二進法の数値yを入力し、1から最大分割ビット長wビットの範囲で符号付き二進法の数値yを分割する。分割処理には、例えば非特許文献2の1718頁に記載された方法を適用する。当該文献は、決定されたビット長固定で分割するconstantlengthnonzerowindows、可変長かつ指定されたビット長を最大の分割長とするvariablelengthnonzerowindowsを記載する。上述したNAFSウィンドウ法ではVLNWを使用する。図3は、図3に示す符号付き二進法の数値yをVLNWビット長5を用いて分割した例を示す。以下では、図3においてアポストロフィで括り、下線を施した数値を符号付き二進法の各数値yiとして説明する。選択部13は、初期分割部12が分割した各数値yiのうち、特定の数値yxを選択する。数列算出部14は、選択部13の選択結果に基づき、yxを含む数列Fkyx⊂Fk:k12...mを算出する。再分割部15は、初期分割部12から分割結果yiを、数列算出部14から数列Fkを入力して、数列Fkに含まれない数値yiについて、1から最大分割ビット長wビットの範囲で複数の数値yjyj⊂Fk:j12...に再分割する。なお、再分割後の各数値yjは、必ず数列Fkに含まれる。倍算テーブル算出部16は、数列算出部14から入力した数列Fkに基づき、数列FkのF2からFmまでの各項つまり、2以上の項をスカラに含む倍算テーブルFkPを算出する。スカラ倍演算部17は、再分割部15から分割結果yiと再分割結果yjを、倍算テーブル算出部16から倍算テーブルFkPを入力して、点Pのスカラ倍QxPを演算する。スカラ倍演算は、楕円曲線上の点Qnを2λ倍する倍算演算Qn12λ×Qnと、楕円曲線上の点Qn1と倍算テーブルFkPの加算演算または減算演算Qn2Qn1±FkPを繰り返し実行する。[スカラ倍演算処理]図4のフローチャートによりスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明する。変換部11は、スカラ倍演算のスカラxを入力する。スカラxは、上述したように、例えば256ビット長の秘密鍵である。変換部11は、スカラxを符号付き二進法の、負数を含む数値yに変換する。ここでは図3に示す符号付き二進法の数値yが得られたとする。次に、初期分割部12は、1から最大分割ビット長wビットの範囲で数値yを数値yiに分割する。ここでは図3に示す分割結果が得られたとする。なお、分割ビット長の範囲は、情報処理装置が実行するプログラムによって指定される場合、情報処理装置を扱うユーザが情報処理装置のユーザインタフェイスなどを介して指定する場合などがある。次に、選択部13は、初期分割部12によって分割された各数値yiから特定の数値yxを選択する。例えば、最も出現頻度が高い数値を選択する。図3の例においては5の出現頻度三回が最も高い。なお、数値の選択は、二番目に出現頻度の高い数値を選択する、情報処理装置が実行するプログラムによって指定された特定の値を選択するなど、任意の方法でよい。次に、数列算出部14は、選択部13が選択した数値の絶対値yxを含む数列Fkyx⊂Fk:k12...mを算出する。ここでいう数列は、上述した加算減算鎖を指す。数列の算出には所定のアルゴリズムを用いる。非特許文献2の22頁、26頁には、binarymethodバイナリ法、octalmethodオクタル法、factormethodファクタ法、boothalgorithmブースアルゴリズムなどが記載されている。例えば、数値の絶対値yx5にオクタル法を適用した場合、5を含む数列Fkとして12345が算出される。次に、数列算出部14は、算出した数列Fkの項の総数mが最大分割ビット長wの関数である閾値2ww31未満か否かを判定する。上述の数列Fkの場合、項の総数mは5である。図3の例は分割長が1から5ビット、つまりw5であり、閾値2553112になる。項の総数m<閾値の場合は算出した数列Fkが再分割部15、倍算テーブル算出部16に出力する。一方、項の総数m≧閾値の場合は、処理をステップS45に戻し、他の数列算出方式により数列Fkを算出する。再分割部15は、数列Fkを入力すると、初期分割部12から入力される各数値yiが数列Fkに含まれるか否かを判定する。数列Fkに含まれない数値yiが存在する場合、再分割部15は、当該数値yiを1からw1ビットの範囲で複数の数値yjyj⊂Fk:j12...に再分割する。例えば、図3に示す例では10017、1010121、10019が数列Fk12345に含まれない。そこで、当該数値yiを、分割長の上限をw1ビットにしてVLNWを用いて再分割し、処理をステップS47に戻す。ステップS47とS48を繰り返すと、最終的に、図3に示す分割結果が得られる。各数値yiは、それぞれ1、3、5の何れかであり、yi⊂Fkを満たす。次に、倍算テーブル算出部16は、数列算出部14が算出した数列Fkに基づき、数列FkのF2からFmまでの各項をスカラに含む倍算テーブルFkPを算出する。なお、算出された各FkPはメモリに格納される。図5により本実施例のスカラ倍演算の過程を説明する。図5は数列Fk12345Fk:k12345:F11F22F33F44F55から倍算テーブルFkPを算出する過程事前演算処理を示す。加算減算鎖の性質、つまりaiaj±akjk<iにより、倍算テーブルの数値FiPは、それ以前に算出した数値の加減算FjP±FkPにより演算可能である。なお、数列の種類によらず、必ずF11とF22は存在するが、1PPであるため、Pの計算とメモリは必要としない。スカラ倍演算部17は、再分割部15から入力した分割結果yiと再分割結果yj、および、メモリに格納された倍算テーブルFkPを用いてスカラ倍演算を行う。分割結果Wnyiyj⊂Wnは、図3のように表現されるものとする。入力をP、Wn、FkPとし、出力QがxPになるアルゴリズムは以下のとおりである。Q∞;無限遠点forifQ2L×Q;処理31ifQ2L×Q;処理31QQ±FkP処理32ここで、LはWiのビット長。図5はスカラx11957708941720303968251の場合に、実施例の処理により11957708941720303968251PWn:n0...26を演算する過程実演算処理を示す。NAFSウィンドウ法は、2ww31個数列1、2を含むの倍算テーブルFkPの候補をとる。一方、本実施例は、2ww31個よりも少ない倍算テーブルFkPの候補によりスカラ倍演算を行うために、スカラを再分割する。従って、本実施例のスカラ倍演算においては、NAFSウィンドウ法に比べて、倍算テーブルFkPの候補を計算するための処理時間やメモリ領域を削減して、NAFSウィンドウ法よりも高速かつ省メモリでスカラ倍演算を行うことができる。また、削減した処理時間を有効活用するために、初期分割ビット長1からwビットの範囲を長くとることで、スカラ倍演算に必要な点の加算回数を低減することができる。これにより、全体のスカラ倍演算処理時間の削減が可能になる。なお、上述した処理工程のうち、ステップS49とS50を除く各ステップは、スカラ倍演算のスカラxのみで処理可能である。上述したように、スカラxは、通常、公開鍵や秘密鍵であり、暗号処理中に鍵生成鍵交換が必要な場合を除き、事前に取得することができる情報である。言い替えれば、スカラ倍演算の処理時間に影響を与えることなく、ステップS41からS48までの処理が実行可能である。以下、本発明にかかる実施例2の情報処理を説明する。なお、実施例2において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。[装置の構成]図6のブロック図により実施例2の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示す。実施例2の情報処理装置は、実施例1の数列Fkを算出する数列算出部14の代わりに、複数の数列Fkを予め格納する数列格納部21を有する。さらに、選択部13から入力した数値を含む数列Fkを数列格納部21に格納された数列から選択する数列選択部22を有する。数列格納部21は、数列FkFk:k12...mを複数格納する。なお、格納する数列Fkは、上述した加算減算鎖であり、項の総数mが2ww31個よりも少ない条件を満たす。数列選択部22は、選択部13から入力した選択結果数値yxに基づき、数列格納部21に格納された複数の数列Fkから、yxを含む数列Fkyx⊂Fkを選択し、選択した数列Fkを再分割部15、倍算テーブル算出部16に出力する。[スカラ倍演算処理]図7のフローチャートにより実施例2のスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明する。なお、ステップS41からS44、S47からS50の処理は、実施例1と同様の処理であり、その詳細説明を割愛する。数列選択部22は、選択部103から入力した選択結果数値yxに基づき、数列格納部21に格納された複数の数列Fkから、yxを含む、項の総数が最小の数列Fkyx⊂Fkを選択する。実施例1と同様に、図3の符号付き二進法の数値yiから、数値yxとして5が選択されたものとする。数列選択部22は、数列格納部21に格納された複数の数列Fkから、5を含む数列として1235を選択したとものとする。なお、上述したように、数列Fk1235は項の総数は4であり、2553112最大分割長5ビットよりも少ない条件を満す。数列選択部22が選択する数列Fk1235は、実施例1においてオクタル法を用いて算出される数列Fk12345よりも項数が少ない。図5に示す演算を考えると、図5に示す実演算処理にかかる演算コストは実施例1と同様であり、図5に示す事前演算処理における倍算テーブルFkPを求める演算コストは、4Pの演算が不要な分、低下する。つまり、実施例2によれば、数列Fkの選択における柔軟性が向上し、選択した数列Fkによって、倍算テーブルFkPを計算する事前演算処理の時間やメモリ領域を削減することができる。以下、本発明にかかる実施例3の情報処理を説明する。なお、実施例3において、実施例1、2と略同様の構成については、同一符号を付して、その詳細説明を省略する。[装置の構成]図8のブロック図により実施例3の楕円曲線上のスカラ倍演算を実行する情報処理装置の構成例を示す。実施例3の情報処理装置は、演算方式が異なる二つのスカラ倍演算方式それぞれの総スカラ倍演算回数を計算する演算回数計算部31と、計算結果に応じて、スカラ倍演算回数がより少ないスカラ倍演算方式を選択的に実行する演算方式制御部32を有する。演算回数計算部31は、再分割部15から分割結果yi、yjを入力し、数列算出部204から数列Fkを入力する。そして、入力した分割結果yi、yjおよび数列Fkに基づき、本実施例のスカラ倍演算による総スカラ倍演算回数と、例えばNAFSウィンドウ法を用いるスカラ倍演算による総スカラ倍演算回数を計算する。演算方式制御部32は、演算回数計算部31の計算結果に基づき、スカラ倍演算回数がより少ないスカラ倍演算方式を選択するとともに、数列算出部204に新たな数列Fkを算出させ、スカラの分割処理をやり直す。第一の演算部であるスカラ倍演算部17は本実施例のスカラ倍演算を実行し、第二の演算部であるスカラ倍演算部33はNAFSウィンドウ法を用いるスカラ倍演算を実行する。なお、第二のスカラ倍演算部33が実行するスカラ倍演算は、NAFSウィンドウ法に限らず、本実施例のスカラ倍演算の方法と異なるスカラ倍演算を行えばよい。[スカラ倍演算処理]図9のフローチャートにより実施例3のスカラの分割、数列の選択、数列に基づく倍算テーブルの生成、スカラ倍演算までの一連の流れを説明する。なお、ステップS41からS48の処理は、実施例1と同様の処理であり、その詳細説明を割愛する。演算回数計算部208は、再分割部15から入力した分割結果yi、yj、および、数列算出部14から入力した数列Fkに基づき、第一のスカラ倍演算部17の総スカラ倍演算回数N1を計算する。そして、第二のスカラ倍演算部33の総スカラ倍演算回数N2を計算する。総スカラ倍演算回数の計算は、倍算テーブル算出部16、第一のスカラ倍演算部17と同じアルゴリズムについて、実際の演算を行わずに、アルゴリズムにおけるスカラ倍演算の総数をカウントすることで実現する。例えば、11957708941720303968251P、数列Fk1235の場合、スカラ倍演算倍算と加算または減算の総数はN189になる。また、例えば、11957708941720303968251PにNAFSウィンドウ法をウィンドウ長5ビットで適用した場合、スカラ倍演算の総数はN293になる。次に、演算方法制御部32は、総スカラ倍演算回数N1とN2を比較する。第一のスカラ倍演算部17の総スカラ倍演算回数の方が少ないN1<N2場合、実施例1と同様に、倍算テーブル算出部17による事前演算処理と、第一のスカラ倍演算部17による実演算処理が実行される。なお、ステップS94とS95の処理は、図4に示すステップS49とS50の処理と同様であり、その詳細説明を省略する。一方、N1≧N2の場合、演算方法制御部32は、算出可能なすべての数列候補Fkを算出したか否かを数列算出部14に問い合わせる。未算出の数列候補Fkがある場合は、処理をステップS45に戻して、数列算出部14に別の数列算出方法を用いて新たな数列Fkを算出させる。算出可能なすべての数列候補Fkが算出されると、第二のスカラ倍演算部33は、スカラ倍演算を実行する。このように、本実施例のスカラ倍演算の演算コストと他の方式のスカラ倍演算の演算コストを比較してN1≧N2場合は、新たな数列を算出して処理をやり直す。ステップS95からS92の処理を繰り返し、算出可能なすべての数列候補Fkを算出しても、N1≧N2の場合は他の方式のスカラ倍演算を実行する。言い替えれば、スカラ倍演算に必要な総演算コストを、他の方式のスカラ倍演算を適用する場合にかかる総演算コスト以下に抑えることが可能である。上記の説明においては、実施例1の構成に演算回数計算部31と演算方法制御部32を追加する例を説明したが、実施例2の構成に演算回数計算部31と演算方法制御部32を追加する構成も実現可能である。その場合、ステップS96の処理は、数列選択部22に、数列格納部21に格納されたすべての数列Fkを選択したか否かを問い合わせることになる。[変形例]●数列Fkの選択方法上記では、数値yxを含む数列Fkyx⊂Fkの選択を説明したが、数値yxは複数あってもよい。例えば、図3に示す例では、5だけでなく71001も含む数列Fk例えば12357を選択するようにすれば、より効率的に数列Fkを選択する処理になる。●スカラxの分割処理方法上記では、スカラxをVLNWで分割または再分割する例を説明した。分割または再分割に用いる分割アルゴリズムは毎回異なってもよい。例えば、ウィンドウ長4ビットで、選択した数値が9、選択した数列Fkが124510119の場合を考える。NAFアルゴリズムでウィンドウ長4ビットの場合、分割された各数値は9から9の範囲に収まる。上述した実施例では、1からwビットの範囲で再分割を行うため、数値1110101は、5101と11に再分割される。しかし、上記の数列Fkは11を含み、数値11のまま演算を行えばスカラ倍演算回数を一回削減することができる。つまり、ウィンドウ長を4ビットから5ビットに拡張すれば、再分割を行わなくてもよい。このように、数列Fkに適応して分割アルゴリズムを変えることにより、スカラ倍演算回数の削減が可能になる。[その他の実施例]また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェアプログラムを、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ又はCPUやMPU等がプログラムを読み出して実行する処理である。