(57)【要約】【課題】  事前計算処理量とテーブルサイズを低減させ，少ない演算回数で計算できるべき乗演算装置を提供する。【解決手段】  入力された２つの整数ｘおよびｅからｘｅを計算するべき乗演算装置において，候補指数格納部４０２に格納されたＬ個の候補指数列｛ｌ＿ｉ｝（０≦ｉ≦Ｌ−１）のそれぞれに対し，事前計算モジュール４０３によりｘ∧｛ｌ＿ｉ｝を事前に計算して事前計算数値格納部４０４に格納しておき，分割モジュール４０５によりｅを候補指数｛ｌ＿ｉ｝のいずれかと一致するか，ｌ＿ｊ±ｌ＿ｋを満たすｊ，ｋが存在するように複数の数値｛ｆ＿ｉ｝（０≦ｉ≦Ｆ−１）に分割し，逐次処理モジュール４０６により，｛ｆ＿ｉ｝について，計算結果格納部４０７に格納された計算結果ｃをｘ∧｛ｌ＿ｉ｝を用いて逐次更新し，全ての｛ｆ＿ｉ｝について更新後の計算結果ｃをｘｅとして出力する。【選択図】  図４
2007034927.tif 000002
【特許請求の範囲】
【請求項１】
２つの整数ｘおよびｅからｘｅを計算するべき乗演算装置において，
２つの整数ｘおよびｅを入力する入力手段と，
ｒビットで表現されるＬ個の候補指数｛ｌ＿ｉ｝（０≦ｉ≦Ｌ−１）を格納する候補指数格納手段と，
前記候補指数格納手段に格納されている候補指数｛ｌ＿ｉ｝のそれぞれに対し，入力された整数ｘからｘ∧｛ｌ＿ｉ｝を事前に計算しておく事前計算手段と，
事前計算された数値ｘ∧｛ｌ＿ｉ｝を格納する事前計算数値格納手段と，
入力された整数ｅを複数の数値｛ｆ＿ｉ｝（０≦ｉ≦Ｆ−１）に分割する分割手段と，
計算結果ｃを格納する計算結果格納手段と，
分割された数値｛ｆ＿ｉ｝（０≦ｉ≦Ｆ−１）について，事前計算された数値ｘ∧｛ｌ＿ｉ｝を用いて計算結果ｃを逐次更新する逐次処理手段と，
全ての前記数値｛ｆ＿ｉ｝について更新後の計算結果ｃをｘｅとして出力する出力手段と
前記候補指数｛ｌ＿ｉ｝は，ｌ＿０＝１からはじまり最終的にｌ＿（L−１）に至る整数の列であり，ｌ＿ｉはそれ以前に現れた数の和（つまりｌ＿ｉ＝ｌ＿ｊ＋ｌ＿ｋ（ｊ，ｋ＜ｉ））を満たし，任意の（２＾ｒ）−１以下の正数ｇに対して，ｇは｛ｌ＿ｉ｝（０≦ｉ≦Ｌ−１）に含まれるか，またはｇ＝ｌ＿ｊ±ｌ＿ｋを満たす０≦ｊ，ｋ≦Ｌ−１が存在することを特徴とするべき乗演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，べき乗剰余演算を行なう，べき乗演算装置に関するものである。
【背景技術】
【０００２】
べき乗剰余演算ｘｅ（ｍｏｄ  Ｎ）は，ＲＳＡ暗号／署名をはじめＥｌＧａｍａｌ暗号，ＤＳＡ署名，Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎ鍵共有方式などで利用されている演算である。ファイルに対する署名や復号などの用途だけではなくＳＳＬなどの通信路のセキュア化においても利用されており，通信要求に対してインタラクティブに演算を行う必要があり，処理効率は暗号処理計算時間に大きく影響する。
【０００３】
べき乗剰余演算はａ）平方剰余演算ｘ２（ｍｏｄ  Ｎ）と，ｂ）乗算剰余演算ｘｕ（ｍｏｄ  Ｎ）とにより構成することができる。与えられたｅに対しｘｅ（ｍｏｄ  Ｎ）を計算するために必要とするａ）およびｂ）の乗算演算の回数を削減することにより，全体の処理時間を高速化する手法がいくつか提案されている。
【０００４】
加算鎖（ａｄｄｉｔｉｏｎ  ｃｈａｉｎ）とは，ａ１＝１からはじまり最終的にａｎ＝ｅに至る整数の列であり，ａｉはそれ以前に現れた数の和（つまりａｉ＝ａｊ＋ａｋ（ｊ，ｋ＜ｉ））を満たす。例えばｅ＝５５のとき｛１，２，３，６，１２，１３，２６，２７，５４，５５｝はその例である。これはｘ→ｘ２→ｘ３→ｘ６→ｘ１２→ｘ１３→ｘ２６→ｘ２７→ｘ５４→ｘ５５のようにａ）およびｂ）の演算を行うことで，ｘ５５が計算できることを表している。これは｛１，２，３，４，…，５２，５３，５４，５５｝のようにｂ）の演算だけを用いるよりも計算量を少なくすることができることを意味している。このように，与えられた指数ｅ（上の例では５５）に対し，より短い加算鎖を見つけるアルゴリズムが有益である。しかし与えられた入力ｅに対し，最短の（最も効率のよい）加算鎖を見つける問題はＮＰ完全問題として知られている。そのため，理論的に最短ではないかもしれないが，計算量をできるだけ下げる様々な手法が提案されている。以下，従来例をいくつか示す。
【０００５】
〔Ｂｉｎａｒｙ  Ｍｅｔｈｏｄ〕
Ｂｉｎａｒｙ  Ｍｅｔｈｏｄはある法則に基づいて構成される加算鎖によりべき乗演算を行うアルゴリズムの一つであり非特許文献１で紹介されている。
【０００６】
Ｂｉｎａｒｙ  Ｍｅｔｈｏｄは，次のような処理を行うアルゴリズムである。与えられた指数ｅ（ｋビット長）をΣｉ−０，…，ｋ−１２ｉ＊ｅ＿ｉ（ｅ＿ｉは０または１）のように２進表現しておく。入力をｘ，ｅ，Ｎとし，出力Ｃはｘｅ（ｍｏｄ  Ｎ）となるアルゴリズムは以下のとおりである。
【０００７】
１）ｉｆ  ｅ＿（ｋ−１）＝１  ｔｈｅｎ  Ｃ：＝ｘ  ｅｌｓｅ  Ｃ：＝１
２）ｆｏｒ  ｉ＝ｋ−２  ｄｏｗｎｔｏ  ０
２−１）Ｃ：＝Ｃ＊Ｃ（ｍｏｄ  Ｎ）
２−２）ｉｆ  ｅ＿ｉ＝１  ｔｈｅｎ  Ｃ  ：＝Ｃ  ＊  ｘ  （ｍｏｄ  Ｎ）
３）ｒｅｔｕｒｎ  Ｃ  
上記において，２）のｆｏｒは変数ｉがｋ−２から０まで１ずつ削減ながら２−１）及び２−２）をループ処理することを表している。図２はｅ＝５５のときＢｉｎａｒｙ  Ｍｅｔｈｏｄを使って上記のようにｘ５５（ｍｏｄ  Ｎ）が計算される過程を表したものである。このときの加算鎖は｛１，２，３，６，１２，１３，２６，２７，５４，５５｝である。
【０００８】
〔ｍ−ａｒｙ  Ｍｅｔｈｏｄ〕
ｍ−ａｒｙ  Ｍｅｔｈｏｄ  はＢｉｎａｒｙ  Ｍｅｔｈｏｄを拡張させたもので，２ビット以上の処理を一度に行う方式である。入力をｘ，ｅ，Ｎとし，出力Ｃはｘｅ（ｍｏｄ  Ｎ）となるアルゴリズムは以下の通りである。ただし，与えられた指数ｅはｋビット長であり，ｅはｓ個のｒ（＝ｌｏｇ２ｍ）ビット列Ｆ＿０，…，Ｆ＿（ｓ−１）（ただしｓはｋ／ｒを超えない整数）に分解されているとする。
【０００９】
０）ｗ＝２，…，ｍ−１についてｘｗ（ｍｏｄ  Ｎ）を事前に計算しておく
１）Ｃ：＝ｘ∧｛Ｆ＿（ｓ−１）｝（ｍｏｄ  Ｎ）とおく。
【００１０】
２）ｆｏｒ  ｉ＝ｓ−２  ｄｏｗｎｔｏ  ０
２−１）Ｃ：＝Ｃｍ  （ｍｏｄ  Ｎ）
２−２）ｉｆ  Ｆ＿ｉ  ≠０  ｔｈｅｎ  Ｃ：＝Ｃ  ＊  ｘ∧｛Ｆ＿ｉ｝  （ｍｏｄ  Ｎ）
３）ｒｅｔｕｒｎ  Ｃ
ｍ−ａｒｙ  Ｍｅｔｈｏｄ  は，ｍ＝４のときＱｕａｔｅｒｎａｒｙ  Ｍｅｔｈｏｄ  と呼ばれる。ｅ＝５５のときのＱｕａｔｅｒｎａｒｙ  Ｍｅｔｈｏｄの処理を図３に示す。ｅを２進数表示すると（１１０１１１）２であるが，これをｒ＝２ビットずつに分解すると，（１１  ０１  １１）２であり，図３に示されている通りに処理される。このときの加算鎖は｛１，２，３，６，１２，１３，２６，５２，５５｝であり，Ｂｉｎａｒｙ  Ｍｅｔｈｏｄに比べて加算鎖の長さが１つ短いため，ｘ５５を計算するための剰余演算が少なくて済むことを意味している。
【００１１】
〔Ｃｏｎｓｔａｎｔ  Ｌｅｎｇｔｈ  Ｎｏｎｚｅｒｏ  Ｗｉｎｄｏｗｓ（登録商標）（ＣＬＮＷ）〕
ｍ−ａｒｙ  Ｍｅｔｈｏｄの拡張のひとつとして，Ｃｏｎｓｔａｎｔ  Ｌｅｎｇｔｈ  Ｎｏｎｚｅｒｏ  Ｗｉｎｄｏｗｓ（登録商標）（ＣＬＮＷ）がある。ＣＬＮＣはＳｌｉｄｉｎｇ  Ｗｉｎｄｏｗｓ（登録商標）  Ｍｅｔｈｏｄｓ／Ｔｅｃｈｎｉｑｕｅｓと呼ばれることもある。本アルゴリズムはＮＷとＺＷという２つのステートを行き交うことで構成され，初期状態はＺＷにおかれるとする。ＮＷは，入力ｅの先頭から１ビットずつチェックし，もし０でない場合にはＺＷにステートが移される。ＺＷでは，あらかじめ定められた固定長のビット数分，入力ｅから入手し，ｍ−ａｒｙ  Ｍｅｔｈｏｄにおけるステップ２と同様の処理を行う。その後，先頭１ビットをチェックして０の場合にはＮＷにステートを移動させ，１の場合にはもう一度同じ処理を行う。
【００１２】
ｍ−ａｒｙ  ＭｅｔｈｏｄのアルゴリズムをベースにＣＬＮＷを説明する。入力ｅに対し，可変長データＦ＿０，…，Ｆ＿（ｓ−１）を，あ）Ｆ＿ｉはすべて０で構成される，い）Ｆ＿ｉはｒビットでＦ＿ｉ＝０ではない，の２条件のいずれかを満たすように分割する。Ｆ＿ｉに対するビット長をＬ（Ｆ＿ｉ）と記載するとき，ＣＬＮＷの処理は以下のように行われる。
【００１３】
０）ｗ＝１，２，…，ｍ−１についてｘｗ（ｍｏｄ  Ｎ）を事前に計算しておく
１）Ｃ：＝ｘ∧｛Ｆ＿（ｓ−１）｝（ｍｏｄ  Ｎ）とおく。
【００１４】
２）ｆｏｒ  ｉ＝ｓ−２  ｄｏｗｎｔｏ  ０
２−１）Ｃ：＝Ｃ∧Ｌ（Ｆ＿ｉ）  （ｍｏｄ  Ｎ）
２−２）ｉｆ  Ｆ＿ｉ  ≠０  ｔｈｅｎ  Ｃ：＝Ｃ  ＊  ｘ∧｛Ｆ＿ｉ｝  （ｍｏｄ  Ｎ）
３）ｒｅｔｕｒｎ  Ｃ
入力ｅ＝（１１１００１０１０００１）２に対しＣＬＮＣを適用した場合（ｒ＝３）には，（１１１  ００  １０１  ０  ００１）２と分割される。ここでｒ＝３のＣＬＮＣでは事前計算として｛３，５，７｝という奇数べきに対する演算結果，つまりＸ＾ｅを計算するためにＸ＾３，Ｘ＾５，Ｘ＾７を事前計算する必要がある。
【００１５】
〔Ｖａｒｉａｂｌｅ  Ｌｅｎｇｔｈ  Ｎｏｎｚｅｒｏ  Ｗｉｎｄｏｗｓ（登録商標）（ＶＬＮＣ）〕
上記で紹介したアルゴリズムにおいては，入力ｅを固定長に分割して逐次処理を行うが，入力ｅを可変長に分割する手法も考えられる。Ｖａｒｉａｂｌｅ  Ｌｅｎｇｔｈ  Ｎｏｎｚｅｒｏ  Ｗｉｎｄｏｗｓ（登録商標）（ＶＬＮＣ）はその一例であり，ｒ（ただしｒ＝ｌｏｇ２ｍ）以下のビット長で奇数のべき，つまり，｛１，３，５，．．．，ｍ−１｝に対してのみ事前計算を行う方式である。入力ｅに対し，可変長データＦ＿０，…，Ｆ＿（ｓ−１）を，あ）Ｆ＿ｉはすべて０で構成される，い）Ｆ＿ｉはｒビット以下で，先頭ビットと最後尾ビットが１である，の２条件のいずれかを満たすように分割する。Ｆ＿ｉに対するビット長をＬ（Ｆ＿ｉ）と記載するとき，ＶＬＮＣ処理は以下のように行われる。
【００１６】
０）ｗ＝１，３，…，ｍ−１についてｘｗ（ｍｏｄ  Ｎ）を事前に計算しておく
１）Ｃ：＝ｘ∧｛Ｆ＿（ｓ−１）｝（ｍｏｄ  Ｎ）とおく。
【００１７】
２）ｆｏｒ  ｉ＝ｓ−２  ｄｏｗｎｔｏ  ０
２−１）Ｃ：＝Ｃ∧Ｌ（Ｆ＿ｉ）  （ｍｏｄ  Ｎ）
２−２）ｉｆ  Ｆ＿ｉ  ≠０  ｔｈｅｎ  Ｃ：＝Ｃ  ＊  ｘ∧｛Ｆ＿ｉ｝  （ｍｏｄ  Ｎ）
３）ｒｅｔｕｒｎ  Ｃ
ｍ−ａｒｙ  Ｍｅｔｈｏｄに比べ事前計算量が少ない（奇数のべきのみ計算するため），ビットが０の箇所をスキップすることができるためステップ２における計算量を削減することができる，というメリットがある。
【００１８】
入力ｅ＝（１１１００１０１０００１）２に対しＶＬＮＣを適用した場合（ｒ＝３）には，（１１１  ００  １０１  ０００  １）２と分割される。
【００１９】
〔Ａｄａｐｔｉｖｅ  ｍ−ａｒｙ  ｍｅｔｈｏｄ〕
非特許文献２では，上記で紹介したアルゴリズムにおける事前計算を入力ｅの解析後に必要なものだけを行う手法が紹介されている。例として入力ｅ＝（０００１０００１０００１０００１）２を考える。このときｒ＝４のｍ−ａｒｙ  ｍｅｔｈｏｄを適用した場合には（０００１  ０００１  ０００１  ０００１）２と分割されるが，Ｍ＾ｅを計算する場合には事前計算であるＭ＾２，Ｍ＾３，・・・，Ｍ＾１５は不要であり無駄な処理となっている。このように入力ｅの形により必要なデータだけを事前計算しておくことで，計算コストを下げる効果がある。
【非特許文献１】Ｄ．Ｅ．Ｋｎｕｔｈ．Ｔｈｅ  Ａｒｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｐｒｏｇｒａｍｍｉｎｇ：Ｓｅｍｉｎｕｍｅｒｉｃａｌ  Ａｌｇｏｒｉｔｈｍｓ，ｖｏｌｕｍｅ  ２，Ｒｅａｄｉｎｇ，ＭＡ：Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ，Ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ，１９８１．
【非特許文献２】Ｈｉｇｈ−Ｓｐｅｅｄ  ＲＳＡ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，ＲＳＡ  Ｌａｂｏｒａｔｏｒｉｅｓ，１９９４．
【発明の開示】
【発明が解決しようとする課題】
【００２０】
上述した従来技術において，Ｂｉｎａｒｙ  Ｍｅｔｈｏｄは事前計算を行う必要がなく，事前計算結果を格納するテーブルを持つ必要がないというメリットを持つ。しかしｅを２進数表示したとき，１が立っているビットの個数が多い場合，計算処理を増大させてしまう欠点がある。ｍ−ａｒｙ  ｍｅｔｈｏｄやＣＬＮＣ，ＶＬＮＣでは，Ｂｉｎａｒｙ  Ｍｅｔｈｏｄにくらべ計算量を少なくする利点があるが，テーブル参照を行うための事前計算処理の計算量が増大するデメリットがある。一方，Ａｄａｐｔｉｖｅ  ｍ−ａｒｙ  ｍｅｔｈｏｄでは，ｍ−ａｒｙ  ｍｅｔｈｏｄ，ＣＬＮＣ，ＶＬＮＣなどのように入力ｅをストリームとして逐次的に処理していく方式とは異なり，いったん入力ｅをすべて走査してから事前計算に必要なデータを生成する必要がある。一般的に，入力ｅに合わせるように分割処理，加算鎖を計算する処理のロジックは複雑であり，事前に入力ｅが判明しておらずｅがダイナミックに変化する場合には不向きである。また計算コスト評価においては，「事前計算に必要なデータ生成」に関わる処理を無視した上で効率性を論じており，実装する場合には理論値と大きな隔たりがあると考えられる。
【課題を解決するための手段】
【００２１】
本発明は，ｍ−ａｒｙ  ｍｅｔｈｏｄ，ＣＬＮＣ，ＶＬＮＣにおいて必要される事前計算処理のすべてを計算するのではなく，その一部分のみの算出を行っておき，入力ｅを走査しながら必要になった箇所を埋めていくという方式を採用する。このハイブリッド方式が本発明において特徴的な点であり，本発明により，事前計算処理量とテーブルサイズの削減と，従来方式に比べて少ない演算回数で計算可能というメリットを持つべき乗計算方式を提供する。また，Ａｄａｐｔｉｖｅ  ｍ−ａｒｙ  ｍｅｔｈｏｄのようにいったん入力ｅをすべて走査してから事前計算に必要なデータを生成する処理や，うまく入力ｅに合わせるように加算鎖を計算する複雑なロジックは不要なため，実装方法が容易であるばかりか，入力ｅがその都度ダイナミックに変化する場合にも適している。
【発明の効果】
【００２２】
以上説明したように本発明によれば，ｅを２進数表示した際のビット列内にある特徴を持つビット列が登場することを想定して，それらのビット列を候補指数として，それらに関してのみ事前計算を行うことで，事前計算処理量を削減し，従来方式に比べて少ない演算回数で計算することができるべき乗計算方式を提供することができる。
【００２３】
また事前計算しておく数値の数が少なくなるので，事前計算数値を記憶するためのテーブルサイズをおさえるメリットもあわせ持ち，テーブル参照のためのメモリ領域を削減することができる。
【発明を実施するための最良の形態】
【００２４】
次に、本発明の詳細を実施例の記述に従って説明する。
【００２５】
以下，図面を参照して，本発明の実施例を説明する。
【実施例１】
【００２６】
本発明は，例えば，図１に示すような情報処理装置（ホストコンピュータ）１００に適用される。本実施例の情報処理装置１００は，パーソナルコンピュータ等のコンピュータを含み，べき乗演算機能を実現する。
【００２７】
すなわち，情報処理装置１００は，図１に示すように，公衆回線等のモデム１１８，表示部としてのモニタ１０２，ＣＰＵ１０３，ＲＯＭ１０４，ＲＡＭ１０５，ＨＤ１０６，ネットワークのネットワーク接続部１０７，ＣＤ１０８，ＦＤ１０９，ＤＶＤ１１０，プリンタ１１５のインターフェース（Ｉ／Ｆ）１１７，及び操作部としてのマウス１１２やキーボード１１３等のインターフェース（Ｉ／Ｆ）１１１が，バス１１６を介して互いに通信可能に接続された構成としている。
【００２８】
マウス１１２及びキーボード１１３は，ユーザが情報処理装置１００に対する各種指示等を入力するための操作部である。この入力情報（操作情報）は，インターフェース１１１を介して情報処理装置１００内に取り込まれる。
【００２９】
情報処理装置１００での各種情報（文字情報や画像情報等）は，プリンタ１１５により印刷出力できるようになされている。
【００３０】
モニタ１０２は，ユーザへの各種指示情報や，文字情報或いは画像情報等の各種情報の表示を行う。
【００３１】
ＣＰＵ１０３は，情報処理装置１００全体の動作制御を司る。すなわち，ＣＰＵ１０３は，ＨＤ（ハードディスク）１０６等から処理プログラム（ソフトウェアプログラム）を読み出して実行することで，情報処理装置１００全体を制御する。特に，本実施形態では，ＣＰＵ１０３は，べき乗演算プログラムを，ＨＤ１０６等から読み出して実行することで，後述する処理を実施する。
【００３２】
ＲＯＭ１０４は，べき乗演算プログラム等の各種処理プログラムや，処理プログラムで利用される各種データ等を記憶する。
【００３３】
ＲＡＭ１０５は，ＣＰＵ１０３での各種処理のために一時的に処理プログラムや処理対象の情報を格納するための作業用エリア等として使用される。
【００３４】
ＨＤ１０６は，大容量記憶装置の一例としての構成要素であり，文字情報や画像情報，或いは各種処理の実行時にＲＡＭ１０５等へ転送される処理プログラム等を保存する。
【００３５】
ＣＤ（ＣＤドライブ）１０８は，外部記憶媒体の一例としてのＣＤ（ＣＤ−Ｒ）に記憶されたデータを読み込み，また，当該ＣＤへデータを書き出す機能を有する。
【００３６】
ＦＤ（フレキシブルディスクドライブ）１０９は，ＣＤ１０８と同様に，外部記憶媒体の一例としてのＦＤに記憶されたデータを読み込み，また，当該ＦＤへデータを書き出す機能を有する。
【００３７】
ＤＶＤ（ディジタルビデオディスクドライブ）１１０は，ＣＤ１０８やＦＤ１０９と同様に，外部記憶媒体の一例としてのＤＶＤに記憶されたデータを読み込み，また，当該ＤＶＤへデータを書き出す機能を有する。
【００３８】
尚，ＣＤ，ＦＤ，ＤＶＤ等の外部記憶媒体に対して，例えば，編集用のプログラム或いはプリンタドライバが記憶されている場合，これらをＨＤ１０６へインストールし，必要に応じてＲＡＭ１０５へ転送するように構成してもよい。
【００３９】
インターフェース（Ｉ／Ｆ）１１１は，マウス１１２やキーボード１１３によるユーザからの入力を受け付けるためのものである。
【００４０】
モデム１１８は，通信モデムであり，インターフェース（Ｉ／Ｆ）１１９を介して，例えば公衆回線等を通じて外部のネットワークに接続される。
【００４１】
ネットワーク接続部１０７は，インターフェース（Ｉ／Ｆ）１１４を介して外部のネットワークに接続される。
【００４２】
図４は，図１の情報処理装置１００において，特徴とする機能（べき乗演算機能）に着目して図示したものである。情報処理装置１００は，図４に示すように，候補指数格納部４０２，事前計算モジュール４０３，事前計算数値格納部４０４，分割モジュール４０５，逐次処理モジュール４０６及び計算結果格納部４０７を有する。各モジュール４０３，４０５，４０６は，ＣＰＵ１０３が所定のプログラムを実行することで実現される機能単位（モジュール）を表わす。各格納部４０２，４０４，４０７はＲＡＭ１０５やＨＤ１０６に格納され必要に応じて読み出し，書き出しがなされる。
【００４３】
情報処理装置１００に対しては，外部から入力値ｘ，Ｎ（４００）及びｅ（４０１）が入力される。情報処理装置１００は，入力値からべき乗剰余演算を行い結果としてｃ＝ｘｅ（ｍｏｄ  Ｎ）（４０８）を出力する装置である。
【００４４】
候補指数格納部４０２には，あらかじめ，パラメータｒ（後述）に対して以下の２条件を満たす数値の列である候補指数列｛ｌ＿ｉ｝（０≦ｉ≦Ｌ−１）が含まれている。
【００４５】
あ）候補指数列｛ｌ＿ｉ｝は加算鎖を構成する（つまり，ｌ＿０＝１からはじまり最終的にｌ＿（L−１）に至る整数の列であり，ｌ＿ｉはそれ以前に現れた数の和（つまりｌ＿ｉ＝ｌ＿ｊ＋ｌ＿ｋ（ｊ，ｋ＜ｉ））を満たす），
い）任意の（２＾ｒ）−１以下の正数ｇに対して，ｇは候補指数列｛ｌ＿ｉ｝（０≦ｉ≦Ｌ−１）に含まれるか，またはｇ＝ｌ＿ｊ＋ｌ＿ｋを満たす０≦ｊ，ｋ≦Ｌ−１が存在する。事前計算モジュール４０３は，入力値（４００）と候補指数格納部４０２から事前計算を行い，事前計算結果を，例えばＨＤ１０６にある，事前計算数値格納部４０４に格納する。ｍ−ａｒｙ  ｍｅｔｈｏｄではｗ∈｛１，２，３，・・・，（２＾ｒ）−１｝に対してｘ＾ｗ（ｍｏｄ  Ｎ）を事前計算しておくが，本実施例ではｗ∈｛ｌ＿ｉ｝（０≦ｉ≦Ｌ−１）に対してｘ＾ｗ（ｍｏｄ  Ｎ）を事前計算しておく。前述した２つの条件  あ）、い）を満たす場合には，ｇが候補指数列｛ｌ＿ｉ｝に含まれない場合でもｇ＝ｌ＿ｊ＋ｌ＿ｋを満たす０≦ｊ，ｋ≦Ｌ−１が存在するため，ｘ＾ｇ＝ｘ＾（ｌ＿ｊ＋ｌ＿ｋ）＝（ｘ＾ｌ＿ｊ）＊（ｘ＾ｌ＿ｋ）という式から1回の乗算でｘ＾ｇを得ることができることがわかる。分割モジュール４０５は，入力値４０１を分割し，入力値４０１および分割された数値を，例えばＨＤ１０６に格納する。逐次処理モジュール４０６は，例えばＨＤ１０６にある計算結果格納部４０７を逐次処理して，計算結果４０８を例えばＨＤ１０６に格納する。計算結果はモニタ１０２，ＦＤ１０９，ネットワークＩ／Ｆ１１４，プリンタ１１５などを通して出力される。
【００４６】
図５は，図４に示した構成を持つ情報処理装置１００におけるべき乗剰余演算の処理手順を説明するためのフローチャートである。例えば，ＣＰＵ１０３は，図３のフローチャートに対応する処理プログラムを読み出して実行する。これにより，情報処理装置１００は次のように動作する。
【００４７】
ステップＳ５００：
入力された入力値ｅ（ｋビット長）をΣｉ−０，…，ｋ−１２ｉ＊ｅ＿ｉ（ｅ＿ｉは０または１）のように２進表現しておく。入力値ｘ，Ｎ，ｅは例えばＨＤ１０６に格納される。
【００４８】
ステップＳ５０１：
入力値ｘ，Ｎから，候補指数格納部４０２にあるＬ個の候補指数列｛ｌ＿ｉ｝（０≦ｉ≦Ｌ−１）のそれぞれに対し，ｘ∧｛ｌ＿ｉ｝を事前に計算し，事前計算数値格納部４０４に格納する。
【００４９】
ステップＳ５０２：
指数ｅ（ビット長ｋ）をビット長ｒの複数の数値｛ｆ＿ｉ｝（０≦ｉ≦Ｆ−１）に分割する。このときｆ＿ｉのビット長をｂ＿ｉとすると，ｋ＝Σｉ−０，…，Ｆ−１ｂ＿ｉとなるように分割しておく。ここでパラメータｒは入力ｅのビット長に依存して変化する整数であり，例えば図１０のようなテーブルから参照される。
【００５０】
ステップＳ５０３：
まず計算結果格納部４０７に，Ｃ：＝ｘ∧ｆ＿０（ｍｏｄ  Ｎ）とおく。このときｆ＿０が候補指数列｛ｌ＿ｉ｝に含まれないならば以下の処理２−１）から２−３）の処理（ただしｉ＝０として扱う）を行う。次にｆ＿ｉ（０≦ｉ≦Ｆ−１）ごとに次のような逐次処理を行う。
【００５１】
ｆｏｒ  ｉ＝１  ｔｏ  Ｆ−１
１）Ｃ：＝  Ｃ∧（２∧ｂ＿ｉ）（ｍｏｄ  Ｎ）
２）ｉｆ  ｆ＿ｉが｛ｌ＿ｉ｝に含まれない  ｔｈｅｎ  
｛
２−１）ｇ＝ｌ＿ｊ＋ｌ＿ｋを満たす０≦ｊ，ｋ≦Ｌ−１を算出
２−２）ｘ∧ｆ＿ｉ＝（ｘ＾ｌ＿ｊ）＊（ｘ＾ｌ＿ｋ）（ｍｏｄ  Ｎ）を算出
２−３）ｘ∧ｆ＿ｉを｛ｌ＿ｉ｝に追加する
｝
３）ｉｆ  ｆ＿ｉ≠０  ｔｈｅｎ  Ｃ：＝Ｃ  ＊  ｘ∧ｆ＿ｉ  （ｍｏｄ  Ｎ）
ステップＳ５０４：
ステップＳ５０３で得られた出力値ｃ＝ｘｅ（ｍｏｄ  Ｎ）を外部に出力する。
【００５２】
ここでステップ５０３処理２−１）では，図６のような，１入力で２つの値を出力する「指数テーブル」を持つことが想定される。この指数テーブルはたとえば候補指数格納部４０２に格納される。例としてｒ＝４，Ｌ＝６，｛ｌ＿ｉ｝＝｛1, 2, 3, 4, 5, 10｝の場合の指数テーブルを示す。ｉｎｐｕｔ＝３の場合のｏｕｔｐｕｔには“ＮＵＬＬ”が格納されているが，これはすでに候補指数列｛ｌ＿ｉ｝に３が含まれｘ＾３が事前計算されていることを示している。またｉｎｐｕｔ＝６の場合のｏｕｔｐｕｔには“１，５”が格納されているが，これは候補指数列｛ｌ＿ｉ｝に６が含まれおらず，ｘ＾１とｘ＾５は事前計算されているため（ｘ＾１）＊（ｘ＾５）（ｍｏｄ Ｎ）という乗算でｘ＾６を得ることができる（処理２−２））ことを示している。処理２−３）では同時に指数テーブルの書き換えが行われる。上記例でｘ＾６を算出した場合には図６をから図７へ書き換えが行われる。図７においてｉｎｐｕｔ＝６の場合のｏｕｔｐｕｔを“ＮＵＬＬ”と変更することで，以降のループでｘ＾６を必要とした際に候補指数列｛ｌ＿ｉ｝から取得することができる。
【００５３】
図８はｅ＝（1010 0110 0001 0110）２  ，ｒ＝４，Ｌ＝６，｛ｌ＿ｉ｝＝｛1, 2, 3, 4, 5, 10｝の場合の適用例である。ｅの先頭からｒビット（ここでは４ビット）を取得しながらｍ−ａｒｙ  ｍｅｔｈｏｄと同様に処理を行っている。まず先頭4ビット（１０１０）２  は候補指数列｛ｌ＿ｉ｝に含まれるためステップ５０３処理２）をスキップし，すでに事前計算されたｘ＾１０を用いてステップ５０３処理３）を行う。次の4ビット（０１１０）２  は候補指数列｛ｌ＿ｉ｝に含まれないため指数テーブルを参照することにより，事前計算された２つの値ｘ＾１，ｘ＾５から（ｘ＾１）＊（ｘ＾５）（ｍｏｄ Ｎ）という乗算からｘ＾６（ｍｏｄ Ｎ）を得て，指数テーブル変更とｘ＾６（ｍｏｄ Ｎ）を候補指数列｛ｌ＿ｉ｝に追加する。その後ステップ５０３処理３）を行う。次の4ビット（０００１）２  ではステップ５０３処理２）をスキップして処理３）が行われる。最後の4ビット（０１１０）２  はすでにｘ＾６が計算されているためステップ５０３処理２）をスキップすることができ処理３）が行われる。ｍ−ａｒｙ  ｍｅｔｈｏｄ（ｒ＝４）ではｘ＾２からｘ＾１５までの１４の事前計算を行う必要があったが，この例では，ｘ＾２，ｘ＾３，ｘ＾４，ｘ＾５，ｘ＾１０の事前計算と，ｘ＾６の中途計算，つまり合計６の事前計算のみでｘ＾ｅの計算を終えていることがわかり，より効率的であることが示された。
【００５４】
図９は指数テーブルと候補指数列｛ｌ＿ｉ｝をひとつのテーブルで記述した例である。入力ｉに対して2つの出力の値を持っており，第２列目は図６，図７のような指数テーブルのｏｕｔｐｕｔと同じ値である2つの整数であり，第３列目はｘ＾ｉの値である。候補指数列への追加を行う場合にこのテーブルを用いることができる。例えば前述した例である「ｘ＾１，ｘ＾５から（ｘ＾１）＊（ｘ＾５）（ｍｏｄ Ｎ）という乗算からｘ＾６を得て，指数テーブル変更とｘ＾６を候補指数列｛ｌ＿ｉ｝に追加する」場合を考えると，第２列目は“ＮＵＬＬ”を格納し，第３列目はｘ＾６（ｍｏｄ Ｎ）を格納する。
【００５５】
前述したように，ｍ−ａｒｙ  ｍｅｔｈｏｄにおいて“一部のみを計算し必要に応じて算出する方式”を採用することで事前処理の無駄を省き，演算処理時間を短縮することができる。
【００５６】
外部から入力値Ｎが入力されない場合にはべき乗演算ｃ＝ｘｅを行うが，これはべき乗剰余演算の特殊な場合と考えられるため，本実施形態では，べき乗剰余演算ｘｅ（ｍｏｄ  Ｎ）を行う装置の説明のみを行った。外部から入力値Ｎが入力されない場合にべき乗演算ｃ＝ｘｅを出力する方式は本発明の実施形態に含まれることはいうまでもない。
【実施例２】
【００５７】
第１の実施例では，ｘ＾ｇ（ｍｏｄ  Ｎ）が事前計算されていない場合には必要なときに随時演算を行っているが，その際には指数テーブルを用いて，初期状態の候補指数列｛ｌ＿ｉ｝（０≦ｉ≦Ｌ−１）においてｇ＝ｌ＿ｊ＋ｌ＿ｋを満たす０≦ｊ，ｋ≦Ｌ−１が存在するようなｌ＿ｊとｌ＿ｋの整数を取得している。これら数値をｇに対する加算予備値と呼び，第１予備値ｌ＿ｊ，第２予備値ｌ＿ｋで構成されているとする。このとき（ｘ＾ｌ＿ｊ）＊（ｘ＾ｌ＿ｋ）（ｍｏｄ  Ｎ）という乗算を行いｘ＾ｇ（ｍｏｄ  Ｎ）を得ているが，乗算演算が２乗演算の場合とそうでない場合によって計算量が異なることが非特許文献２に記載されており，２乗演算は，異なる数値どうしの乗算にくらべ，計算量が少ないことが知られている。そこで指数テーブルにおける予備値において，第１予備値と第２予備値が同じになるように構成することで，ｘ＾ｇの演算における演算量を削減することができる。
【００５８】
例として図６に記載の指数テーブルから図１０のようにできるだけ第１予備値と第２予備値が同じになるように再構成して指数テーブルを示す。図６と図１０では，ｉｎｐｕｔが６と８の箇所で異なっており，それぞれ図１０においては６＝３＋３，８＝４＋４が成り立つことから第１予備値と第２予備値が同じになるように構成されていることがわかる。このように２乗演算による処理の高速化が可能となる。
【００５９】
また，同様にｇが偶数で，ｘ＾ｇ（ｍｏｄ  Ｎ）を算出する場合，指数テーブルにおける予備値を参照して予備値による乗算演算を行うよりも，ｇ／２が候補指数列に含まれているかチェックを行い，存在する場合にはｘ＾（ｇ／２）の２乗演算を行う処理を優先させることで，処理の高速化が可能となる。
【実施例３】
【００６０】
上記実施例では候補指数列として正数のみを扱っていたが，この制限事項をなくし負数も考慮することで演算を行う場合について説明する。実施例１の候補指数はｒ＝４，Ｌ＝６，｛ｌ＿ｉ｝＝｛1, 2, 3, 4, 5, 10｝であった。これらの数値の和は１から１５までの整数を網羅するが，ここに負数を入れた場合には，乗算演算の代わりに逆数演算を行うことで演算量を減らすことができる。例として上記例と同じｒ＝４の場合の指数候補を示す。Ｌ＝７，｛ｌ＿ｉ｝＝｛1, 2, 3, 6, 12, -1, -2｝は負数２つを含む候補指数である。正数だけを抜き出した｛1, 2, 3, 6, 12｝は加算鎖を為しており，負数はその加算鎖のうち絶対値が同じものを選択している。この例における指数テーブルは図１１で示されており，図１２はその模式図である。−１，−２の項目が増加しており，ｏｕｔｐｕｔにはべき数が１０と１１の箇所で利用されていることがわかる。例えばｇ＾１０の演算にはｇ＾（−２）＊ｇ＾１２の乗算を行えばよい。
【００６１】
負数指数の計算には拡張ユークリッド互除法を用い，ｘ＾ｇ（ｍｏｄ  Ｎ）からｘ＾（―ｇ）（ｍｏｄ  Ｎ）の計算を行う。上記例では，ｇ＾（−１）とｇ＾（−２）の計算に用いられる。拡張ユークリッド互除法は乗算演算に比べ非常に計算量が少なくて済むことから本方式は有効である。上記例では指数候補演算において５回の乗算演算と２回の逆数演算を行っているが，図６においては６回の乗算演算が必要であった。
【実施例４】
【００６２】
入力された e の長さ（ここではｋビットとおく）によってパラメータｒを変化させることがある。ｍ−ａｒｙ  ｍｅｔｈｏｄでは総演算量の平均が２＾ｒ−２＋ｋ−ｒ＋（ｋ／ｒ−１）（１−２＾（−ｒ））で算出される。パラメータｋに対してこの値を最小にするパラメータｒを決めることができる。本発明においても同様の手法をとることができるが，以下ｒが３から６の場合の，指数テーブルの例を示す。これらのテーブルは事前演算量を少なくするように設計されている。
【００６３】
ｒ＝３の場合：{1, 2, 3, 4}
ｒ＝４の場合：｛1, 2, 3, 6, 12, -1, -2｝（図１１）
ｒ＝５の場合：｛1, 2, 3, 4, 7, 14, 21, 28, -1, -2｝（図１３）
ｒ＝６の場合：{1, 2, 3, 4, 5, 10, 20, 30, 40, 50, 60, -1,-2,-3,-4}（図１４）
（その他の実施例）
本発明は，複数の機器（例えばホストコンピュータ等）から構成されるシステムの一部として適用しても，一つの機器からなるものの一部に適用してもよい。
【００６４】
また，上述した実施例の機能を実現するべく各種のデバイスを動作させるように，該各種デバイスと接続された装置或いはシステム内のコンピュータに対し，上記実施例の機能を実現するためのソフトウェアのプログラムコードを供給し，そのシステム或いは装置のコンピュータ（ＣＰＵ或いはＭＰＵ）に格納されたプログラムに従って上記各種デバイスを動作させることによって実施したものも，本発明の範疇に含まれる。
【００６５】
また，この場合，上記ソフトウェアのプログラムコード自体が上述した実施例の機能を実現することになり，そのプログラムコード自体は本発明を構成する。そのプログラムコードの伝送媒体としては，プログラム情報を搬送波として伝搬させて供給するためのコンピュータネットワーク（ＬＡＮ，インターネット等のＷＡＮ，無線通信ネットワーク等）システムにおける通信媒体（光ファイバ等の有線回線や無線回線等）を用いることができる。
【００６６】
さらに，上記プログラムコードをコンピュータに供給するための手段，例えばかかるプログラムコードを格納した記録媒体は本発明を構成する。かかるプログラムコードを記憶する記録媒体としては，例えばフレキシブルディスク，ハードディスク，光ディスク，光磁気ディスク，ＣＤ−ＲＯＭ，磁気テープ，不揮発性のメモリカード，ＲＯＭ等を用いることができる。
【００６７】
また，コンピュータが供給されたプログラムコードを実行することにより，上述の実施例の機能が実現されるだけでなく，そのプログラムコードがコンピュータにおいて稼働しているＯＳ（オペレーティングシステム）或いは他のアプリケーションソフト等と共同して上述の実施の形態の機能が実現される場合にもかかるプログラムコードは本発明の実施の形態に含まれることはいうまでもない。
【００６８】
さらに，供給されたプログラムコードがコンピュータの機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに格納された後，そのプログラムコードの指示に基づいてその機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部又は全部を行い，その処理によって上述した実施の形態の機能が実現される場合にも本発明に含まれることはいうまでもない。
【図面の簡単な説明】
【００６９】
【図１】実施形態の情報処理装置の構成を示すブロック図である。
【図２】従来例であるＢｉｎａｒｙ  Ｍｅｔｈｏｄでの処理を表す図である。
【図３】従来例であるｍ−ａｒｙ  Ｍｅｔｈｏｄ（ｍ＝４）での処理を表す図である。
【図４】第１の実施の形態における情報処理装置の機能構成を示すブロック図である。
【図５】第１の実施の形態におけるべき乗剰余演算の処理手順を説明するためのフローチャートである。
【図６】第１の実施の形態における初期状態の指数テーブルを表す図である。
【図７】第１の実施の形態における変更後の指数テーブルを表す図である。
【図８】第１の実施の形態における逐次計算の例を示す図である。
【図９】第１の実施の形態における指数テーブルと候補指数列をひとつのテーブルで記述した例を表す図である。
【図１０】第２の実施の形態における指数テーブルを表す図である。
【図１１】第３の実施の形態における指数テーブルを表す図である。
【図１２】第３の実施の形態における指数テーブルを模式化した図である。
【図１３】第４の実施の形態における指数テーブルを表す図である。
【図１４】第４の実施の形態における指数テーブルを表す図である。
【符号の説明】
【００７０】
１００  情報処理装置
１０２  モニタ
１０３  ＣＰＵ
１０４  ＲＯＭ
１０５  ＲＡＭ
１０６  ＨＤ
１０７  ネットワーク接続部
１０８  ＣＤドライブ
１０９  ＦＤドライブ
１１０  ＤＶＤドライブ
１１１  インターフェース
１１２  マウス
１１３  キーボード
１１４  インターフェース
１１５  プリンタ
１１６  バス
１１７  インターフェース
１１８  モデム
１１９  インターフェース
４００  入力値  ｘ，Ｎ
４０１  入力値  ｅ
４０２  候補指数格納部
４０３  事前計算モジュール
４０４  事前計算数値格納部
４０５  分割モジュール
４０６  逐次処理モジュール
４０７  計算結果格納部
４０８  計算結果  ｃ
【図１】
2007034927.tif 000003
【図２】
2007034927.tif 000004
【図３】
2007034927.tif 000005
【図４】
2007034927.tif 000006
【図５】
2007034927.tif 000007
【図６】
2007034927.tif 000008
【図７】
2007034927.tif 000009
【図８】
2007034927.tif 000010
【図９】
2007034927.tif 000011
【図１０】
2007034927.tif 000012
【図１１】
2007034927.tif 000013
【図１２】
2007034927.tif 000014
【図１３】
2007034927.tif 000015
【図１４】
2007034927.tif 000016